TryAlgo in Paris

In [10]:
from paris import read_graph, closest_node, display

N, paris_graph, weight, distance, visited, paris_coords = read_graph()

Géolocalisation de NUMA

In [11]:
from geopy.geocoders import Nominatim

geocoder = Nominatim()
start = geocoder.geocode("NUMA, Paris")
start.longitude, start.latitude
Out[11]:
(2.34958019131168, 48.8676206)
In [6]:
numa = closest_node(paris_coords, start)
numa
Out[6]:
11253
In [7]:
from tryalgo.dijkstra import dijkstra

def paris_cross(start_node, f):
    N, paris_graph, weight, distance, visited, paris_coords = read_graph()
    node = start_node
    path = []
    elapsed_time = 0
    score = 0
    while elapsed_time < 3600:  # While there is still time
        path.append(node)
        new_neighbors = list(filter(lambda neighbor: not visited[node][neighbor], paris_graph[node]))
        if new_neighbors:
            new_neighbors.sort(key=lambda neighbor: f(path, neighbor))
            chosen_neighbor = new_neighbors[-1]
            elapsed_time += weight[node][chosen_neighbor]
            score += distance[node][chosen_neighbor]
            visited[node][chosen_neighbor] = True
            visited[chosen_neighbor][node] = True
        else:
            stuck_node = node
            dist, prec = dijkstra(paris_graph, weight, stuck_node)
            for jump_time, node in sorted((dist[u], u) for u in range(N)):
                if any(not visited[node][neighbor] for neighbor in paris_graph[node]):
                    chosen_neighbor = node
                    elapsed_time += jump_time
                    break
            extra_path = []
            node = prec[chosen_neighbor]
            while node != stuck_node:
                extra_path.append(node)
                node = prec[node]
            path.extend(extra_path)
        node = chosen_neighbor
    print('Score:', score, 'in', elapsed_time, 'seconds')
    return path

Première balade : marche aléatoire

In [15]:
from random import randint

def random_walk(path, neighbor):
    return randint(1, 100)

path = paris_cross(numa, random_walk)
Score: 26044 in 3732 seconds
In [16]:
display(paris_coords, path)
Out[16]:

Deuxième balade : la route la plus longue

In [17]:
def longest_road(path, neighbor):
    return distance[path[-1]][neighbor]

path = paris_cross(numa, longest_road)
Score: 29197 in 3612 seconds
In [18]:
display(paris_coords, path)
Out[18]:

Troisième balade : la route ayant le plus grand rapport longueur / temps

In [19]:
def best_road(path, neighbor):
    return distance[path[-1]][neighbor] / weight[path[-1]][neighbor]

path = paris_cross(numa, best_road)
Score: 26824 in 3627 seconds
In [20]:
display(paris_coords, path)
Out[20]:
In [ ]: