.. _mlrueparisparcoursrst: ===================================== 2A.algo - Parcourir les rues de Paris ===================================== .. only:: html **Links:** :download:`notebook `, :downloadlink:`html `, :download:`python `, :downloadlink:`slides `, :githublink:`GitHub|_doc/notebooks/expose/ml_rue_paris_parcours.ipynb|*` Algorithme de plus courts chemins dans un graphe. Calcul d’un chemin comparé au calcul de tous les chemins les plus courts. .. code:: ipython3 %matplotlib inline .. parsed-literal:: Populating the interactive namespace from numpy and matplotlib Cette idée vient d’une soirée Google Code initiée par Google et à laquelle des élèves de l’ENSAE ont participé. On dispose de la description des rues de Paris (qu’on considèrera comme des lignes droites). On veut déterminer le trajet de huit voitures de telle sorte qu’elles parcourent la ville le plus rapidement possible. On supposera deux cas : - Les voitures peuvent être placées n’importe où dans la ville. - Les voitures démarrent et reviennent au même point de départ, le même pour toutes. Ce notebook décrit comment récupérer les données et propose une solution. Ce problème est plus connu sous le nom du `problème du postier chinois `__ ou `Route inspection problem `__ pour lequel il existe un algorithme optimal à coût polynomial. Le problème n’est donc pas `NP complet `__. .. code:: ipython3 from jyquickhelper import add_notebook_menu add_notebook_menu() .. contents:: :local: Une versions de ce problème est proposée sous forme de challenge : `City Tour `__. Les données ----------- On récupère les données sur Internet. .. code:: ipython3 import pyensae.datasource data = pyensae.datasource.download_data("paris_54000.zip") data .. parsed-literal:: downloading of http://www.xavierdupre.fr/enseignement/complements/paris_54000.zip to paris_54000.zip unzipped paris_54000.txt to .\paris_54000.txt .. parsed-literal:: ['.\\paris_54000.txt'] On extrait du fichier l’ensemble des carrefours (vertices) et des rues ou segment de rues (edges). .. code:: ipython3 name = data[0] with open(name, "r") as f : lines = f.readlines() vertices = [] edges = [ ] for i,line in enumerate(lines) : spl = line.strip("\n\r").split(" ") if len(spl) == 2 : vertices.append ( (float(spl[0]), float(spl[1]) ) ) elif len(spl) == 5 and i > 0: v1,v2 = int(spl[0]),int(spl[1]) ways = int(spl[2]) # dans les deux sens ou pas p1 = vertices[v1] p2 = vertices[v2] edges.append ( (v1,v2,ways,p1,p2) ) elif i > 0 : raise Exception("unable to interpret line {0}: ".format(i) + line) print("#E=",len(edges), "#V=",len(vertices), ">",max (max( _[0] for _ in edges), max( _[1] for _ in edges))) .. parsed-literal:: #E= 17958 #V= 11348 > 11347 On trace sur un graphique un échantillon des carrefours. On suppose la ville de Paris suffisamment petite et loin des pôles pour considérer les coordonnées comme cartésiennes (et non comme longitude/latitude). .. code:: ipython3 import matplotlib.pyplot as plt import random sample = [ vertices[random.randint(0,len(vertices)-1)] for i in range(0,1000)] plt.plot( [_[0] for _ in sample], [_[1] for _ in sample], ".") .. parsed-literal:: [] .. image:: ml_rue_paris_parcours_10_1.png Puis on dessine également un échantillon des rues. .. code:: ipython3 sample = [ edges[random.randint(0,len(edges)-1)] for i in range(0,1000)] for edge in sample: plt.plot( [_[0] for _ in edge[-2:]], [_[1] for _ in edge[-2:]], "b-") .. image:: ml_rue_paris_parcours_12_0.png Petite remarque : il n’y a pas de rues reliant le même carrefour : .. code:: ipython3 len ( list(e for e in edges if e[0]==e[1] )) .. parsed-literal:: 0 Une première solution au premier problème ----------------------------------------- Ce problème est très similaire à celui du `portier chinois `__. La solution qui suit n’est pas nécessaire la meilleure mais elle donne une idée de ce que peut-être une recherche un peu expérimentale sur le sujet. Chaque noeud représente un carrefour et chaque rue est un arc reliant des deux carrefours. L’objectif est de parcourir tous les arcs du graphe avec 8 voitures. Premiere remarque, l’énoncé ne dit pas qu’il faut parcourir toutes les rues une seule fois. On conçoit aisément que ce serait l’idéal mais on ne sait pas si ce serait possible. Néanmoins, si une telle solution (un chemin passant une et une seule fois par toutes les rues) existe, elle est forcément optimale. Deuxième remarque, les sens interdits rendent le problème plus complexe. On va dans un premier temps ne pas en tenir compte. On verra comment ajouter la contrainte par la suite et il y a aussi le problème des impasses. On peut néanmoins les contourner en les supprimant du graphe : il faut nécessairement faire demi-tour et il n’y a pas de meilleure solution. Ces deux remarques étant faite, ce problème rappelle un peu le problème des sept ponts de `Konigsberg `__ : comment traverser passer par les sept de la ville une et une seule fois. Le mathématicien `Euler `__ a répondu à cette question : c’est simple, il suffit que chaque noeud du graphe soit rejoint par un nombre pair de d’arc (= ponts) sauf au plus 2 (les noeuds de départ et d’arrivée). De cette façon, à chaque qu’on rejoint un noeud, il y a toujours une façon de repartir. .. code:: ipython3 import networkx as nx g = nx.Graph() for i,j in [(1,2),(1,3),(1,4),(2,3),(3,4),(4,5),(5,2),(2,4) ]: g.add_edge( i,j ) import matplotlib.pyplot as plt f, ax = plt.subplots(figsize=(6,3)) nx.draw(g, ax = ax) .. image:: ml_rue_paris_parcours_16_0.png On ne peut pas trouver une chemin qui parcourt tous les arcs du graphe précédent une et une seule fois. Qu’en est-il du graphe de la ville de Paris ? On compte les noeuds qui ont un nombre pairs et impairs d’arcs les rejoignant (on appelle cela le `degré `__). .. code:: ipython3 nb_edge = { } for edge in edges : v1,v2 = edge[:2] nb_edge[v1] = nb_edge.get(v1,0)+1 nb_edge[v2] = nb_edge.get(v2,0)+1 parite = { } for k,v in nb_edge.items(): parite[v] = parite.get(v,0) + 1 [ sorted(parite.items()) ] .. parsed-literal:: [[(2, 1337), (3, 7103), (4, 2657), (5, 209), (6, 35), (7, 6), (8, 1)]] On remarque que la plupart des carrefours sont le départ de 3 rues. Qu’à cela ne tienne, pourquoi ne pas ajouter des arcs entre des noeuds de degré impair jusqu’à ce qu’il n’y en ait plus que 2. De cette façon, il sera facile de construire un seul chemin parcourant toutes les rues. Comment ajouter ces arcs ? Cela va se faire en deux étapes : - On utilise l’algorithme de `Bellman-Ford `__ pour construire une matrice des plus courts chemins entre tous les noeuds. - On s’inspire de l’algorithme de poids minimal `Kruskal `__. On trie les arcs par ordre croissant de distance. On ajoute ceux qui réduisent le nombre de noeuds de degré impairs en les prenant dans cet ordre. **Quelques justifications :** le meilleur parcours ne pourra pas descendre en deça de la somme des distances des rues puisqu’il faut toutes les parcourir. De plus, s’il existe un chemin qui parcourt toutes les rues, en dédoublant toutes celles parcourues plus d’une fois, il est facile de rendre ce chemin *eulérien* dans un graphe légèrement modifié par rapport au graphe initial. Etape 1 : la matrice Bellman ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Je ne détaillerai pas trop, la page Wikipedia est assez claire. Dans un premier temps on calcule la longueur de chaque arc (de façon cartésienne). Une autre distance (`Haversine `__) ne changerait pas le raisonnement. .. code:: ipython3 def distance(p1,p2): return ((p1[0]-p2[0])**2+(p1[1]-p2[1])**2)**0.5 edges = [ edge + (distance( edge[-2],edge[-1]),) for edge in edges] Ensuite, on implémente l’algorithme de `Bellman-Ford `__. .. code:: ipython3 import datetime init = { (e[0],e[1]) : e[-1] for e in edges } init.update ( { (e[1],e[0]) : e[-1] for e in edges } ) edges_from = { } for e in edges : if e[0] not in edges_from : edges_from[e[0]] = [] if e[1] not in edges_from : edges_from[e[1]] = [] edges_from[e[0]].append(e) edges_from[e[1]].append( (e[1], e[0], e[2], e[4], e[3], e[5] ) ) modif = 1 total_possible_edges = len(edges_from)**2 it = 0 while modif > 0 : modif = 0 initc = init.copy() # to avoid RuntimeError: dictionary changed size during iteration s = 0 for i,d in initc.items() : fromi2 = edges_from[i[1]] s += d for e in fromi2 : if i[0] == e[1] : # on fait attention à ne pas ajouter de boucle sur le même noeud continue new_e = i[0], e[1] new_d = d + e[-1] if new_e not in init or init[new_e] > new_d : init[new_e] = new_d modif += 1 print(datetime.datetime.now(), "iteration ", it, " modif ", modif, " # ", len(initc),"/",total_possible_edges,"=", "%1.2f" %(len(initc)*100 / total_possible_edges) + "%") it += 1 if it > 6 : break .. parsed-literal:: 2015-04-12 01:16:40.590690 iteration 0 modif 72870 # 35916 / 128777104 = 0.03% 2015-04-12 01:16:41.340550 iteration 1 modif 120368 # 104842 / 128777104 = 0.08% 2015-04-12 01:16:42.887810 iteration 2 modif 180646 # 213826 / 128777104 = 0.17% 2015-04-12 01:16:45.510596 iteration 3 modif 255702 # 368960 / 128777104 = 0.29% 2015-04-12 01:16:49.759326 iteration 4 modif 347092 # 576106 / 128777104 = 0.45% 2015-04-12 01:16:55.781000 iteration 5 modif 455899 # 839276 / 128777104 = 0.65% 2015-04-12 01:17:04.276258 iteration 6 modif 584263 # 1162870 / 128777104 = 0.90% On s’aperçoit vite que cela va être très très long. On décide alors de ne considérer que les paires de noeuds pour lesquelles la distance à vol d’oiseau est inférieure au plus grand segment de rue ou inférieure à cette distance multipliée par un coefficient. .. code:: ipython3 max_segment = max( e[-1] for e in edges ) max_segment .. parsed-literal:: 0.017418989861067814 On calcule les arcs admissibles (en espérant que les noeuds de degré impairs seront bien dedans). Cette étape prend quelques minutes : .. code:: ipython3 possibles = { (e[0],e[1]) : e[-1] for e in edges } possibles.update ( { (e[1],e[0]) : e[-1] for e in edges } ) initial = possibles.copy() for i1,v1 in enumerate(vertices) : for i2 in range(i1+1,len(vertices)): v2 = vertices[i2] d = distance(v1,v2) if d < max_segment / 2 : # on ajuste le seuil possibles [ i1,i2 ] = d possibles [ i2,i1 ] = d print("original",len(initial),"/",total_possible_edges,"=", len(initial)/total_possible_edges) print("addition",len(possibles)-len(initial),"/",total_possible_edges,"=", (len(possibles)-len(initial))/total_possible_edges) .. parsed-literal:: original 35916 / 128777104 = 0.000278900510140374 addition 2875586 / 128777104 = 0.022329947721141486 On vérifie que les noeuds de degré impairs font tous partie de l’ensemble des noeuds recevant de nouveaux arcs. La matrice de Bellman envisagera au pire 2.2% de toutes les distances possibles. .. code:: ipython3 allv = { p[0]:True for p in possibles if p not in initial } # possibles est symétrique for v,p in nb_edge.items() : if p % 2 == 1 and v not in allv : raise Exception("problème pour le noeud: {0}".format(v)) print("si vous voyez cette ligne, c'est que tout est bon") .. parsed-literal:: si vous voyez cette ligne, c'est que tout est bon On continue avec l’algorithme de `Bellman-Ford `__ modifié : .. code:: ipython3 import datetime init = { (e[0],e[1]) : e[-1] for e in edges } init.update ( { (e[1],e[0]) : e[-1] for e in edges } ) edges_from = { } for e in edges : if e[0] not in edges_from : edges_from[e[0]] = [] if e[1] not in edges_from : edges_from[e[1]] = [] edges_from[e[0]].append(e) edges_from[e[1]].append( (e[1], e[0], e[2], e[4], e[3], e[5] ) ) modif = 1 total_possible_edges = len(edges_from)**2 it = 0 while modif > 0 : modif = 0 initc = init.copy() # to avoid RuntimeError: dictionary changed size during iteration s = 0 for i,d in initc.items() : if i not in possibles : continue # we skip undesired edges ------------------- addition fromi2 = edges_from[i[1]] s += d for e in fromi2 : if i[0] == e[1] : # on fait attention à ne pas ajouter de boucle sur le même noeud continue new_e = i[0], e[1] new_d = d + e[-1] if new_e not in init or init[new_e] > new_d : init[new_e] = new_d modif += 1 print(datetime.datetime.now(), "iteration ", it, " modif ", modif, " # ", len(initc),"/",total_possible_edges,"=", "%1.2f" %(len(initc)*100 / total_possible_edges) + "%") it += 1 if it > 20 : break .. parsed-literal:: 2015-04-12 01:18:45.389333 iteration 0 modif 72870 # 35916 / 128777104 = 0.03% 2015-04-12 01:18:46.179293 iteration 1 modif 119604 # 104842 / 128777104 = 0.08% 2015-04-12 01:18:47.853483 iteration 2 modif 178033 # 213086 / 128777104 = 0.17% 2015-04-12 01:18:50.790772 iteration 3 modif 248648 # 365751 / 128777104 = 0.28% 2015-04-12 01:18:55.302585 iteration 4 modif 330443 # 566457 / 128777104 = 0.44% 2015-04-12 01:19:02.002318 iteration 5 modif 419549 # 815211 / 128777104 = 0.63% 2015-04-12 01:19:11.623367 iteration 6 modif 508807 # 1109019 / 128777104 = 0.86% 2015-04-12 01:19:23.579840 iteration 7 modif 585973 # 1438040 / 128777104 = 1.12% 2015-04-12 01:19:38.370350 iteration 8 modif 639491 # 1785232 / 128777104 = 1.39% 2015-04-12 01:19:56.035255 iteration 9 modif 656961 # 2127675 / 128777104 = 1.65% 2015-04-12 01:20:16.436453 iteration 10 modif 638987 # 2441604 / 128777104 = 1.90% 2015-04-12 01:20:39.075644 iteration 11 modif 591284 # 2711201 / 128777104 = 2.11% 2015-04-12 01:21:04.245760 iteration 12 modif 519515 # 2928527 / 128777104 = 2.27% 2015-04-12 01:21:33.496050 iteration 13 modif 434787 # 3091667 / 128777104 = 2.40% 2015-04-12 01:22:02.419568 iteration 14 modif 346204 # 3205671 / 128777104 = 2.49% 2015-04-12 01:22:29.389913 iteration 15 modif 263229 # 3279078 / 128777104 = 2.55% 2015-04-12 01:22:55.394012 iteration 16 modif 191482 # 3323381 / 128777104 = 2.58% 2015-04-12 01:23:22.033884 iteration 17 modif 133738 # 3348569 / 128777104 = 2.60% 2015-04-12 01:23:49.684842 iteration 18 modif 90442 # 3362160 / 128777104 = 2.61% 2015-04-12 01:24:17.267404 iteration 19 modif 59686 # 3369505 / 128777104 = 2.62% 2015-04-12 01:24:46.839139 iteration 20 modif 38936 # 3373640 / 128777104 = 2.62% L’algorithme consiste à regarder les chemins :math:`a \rightarrow b \rightarrow c` et à comparer s’il est plus rapide que :math:`a \rightarrow c`. 2.6% > 2.2% parce que le filtre est appliqué seulement sur :math:`a \rightarrow b`. Finalement, on considère les arcs ajoutés puis on retire les arcs originaux. .. code:: ipython3 original = { (e[0],e[1]) : e[-1] for e in edges } original.update ( { (e[1],e[0]) : e[-1] for e in edges } ) additions = { k:v for k,v in init.items() if k not in original } additions.update( { (k[1],k[0]):v for k,v in additions.items() } ) Kruskall ~~~~~~~~ On trie les arcs par distance croissante, on enlève les arcs qui ne relient pas des noeuds de degré impair puis on les ajoute un par jusqu’à ce qu’il n’y ait plus d’arc de degré impair. .. code:: ipython3 degre = { } for k,v in original.items() : # original est symétrique degre[k[0]] = degre.get(k[0],0) + 1 tri = [ (v,k) for k,v in additions.items() if degre[k[0]] %2 == 1 and degre[k[1]] %2 == 1 ] tri.extend( [ (v,k) for k,v in original.items() if degre[k[0]] %2 == 1 and degre[k[1]] %2 == 1 ] ) tri.sort() impairs = sum ( v%2 for k,v in degre.items() ) added_edges = [] for v,a in tri : if degre[a[0]] % 2 == 1 and degre[a[1]] % 2 == 1 : # il faut refaire le test car degre peut changer à chaque itération degre[a[0]] += 1 degre[a[1]] += 1 added_edges.append ( a + (v,) ) impairs -= 2 if impairs <= 0 : break # on vérifie print("nb degré impairs",impairs, "nombre d'arcs ajoutés",len(added_edges)) print("longueur ajoutée ", sum( v for a,b,v in added_edges )) print("longueur initiale ", sum( e[-1] for e in edges )) .. parsed-literal:: nb degré impairs 22 nombre d'arcs ajoutés 3648 longueur ajoutée 3.5423464430662346 longueur initiale 17.418504406203844 Le nombre de noeuds impairs obtenus à la fin doit être inférieur à 2 pour être sûr de trouver un chemin (mais on choisira 0 pour avoir un circuit eulérien). Mon premier essai n’a pas donné satisfaction (92 noeuds impairs restant) car j’avais choisi un seuil (max_segment / 4) trop petit lors de la sélection des arcs à ajouter. J’ai augmenté le seuil par la suite mais il reste encore 22 noeuds de degré impairs. On a le choix entre augmenter ce seuil mais l’algorithme est déjà long ou chercher dans une autre direction comme laisser l’algorithme de Bellman explorer les noeuds de degré impairs. Ca ne veut pas forcément dire qu’il manque des arcs mais que peut-être ils sont mal choisis. Si l’arc :math:`i \rightarrow j` est choisi, l’arc :math:`j \rightarrow k` ne le sera pas car :math:`j` aura un degré pair. Mais dans ce cas, si l’arc :math:`j \rightarrow k` était le dernier arc disponible pour combler :math:`k`, on est coincé. On peut augmenter le seuil encore mais cela risquee de prendre du temps et puis cela ne fonctionnerait pas toujours sur tous les jeux de données. On pourait alors écrire une sorte d’algorithme itératif qui exécute l’algorithme de Bellman, puis lance celui qui ajoute les arcs. Puis on revient au premier en ajoutant plus d’arcs autour des noeuds problèmatique lors de la seconde étape. L’ensemble est un peu long pour tenir dans un notebook mais le code est celui de la fonction `eulerien_extension `__. Je conseille également la lecture de cet article : `Efficient Algorithms for Eulerian Extension `__ (voir également `On Making Directed Graphs Eulerian `__). L’exécution qui suit prend une vingtaine de minutes. .. code:: ipython3 from ensae_teaching_cs.special.rues_paris import eulerien_extension, distance_paris,get_data print("data") edges = get_data() print("start, nb edges", len(edges)) added = eulerien_extension(edges, distance=distance_paris) print("end, nb added", len(added)) .. parsed-literal:: data start, nb edges 17958 possible_edges original 17958 / 64382878.0 = 0.00027892508936925745 addition 1312214 / 64382878.0 = 0.020381412586122666 next iteration 0 modif 72876 # 17958 / 64382878 = 0.03% iteration 1 modif 119544 # 52421 / 64382878 = 0.08% iteration 2 modif 177609 # 106511 / 64382878 = 0.17% iteration 3 modif 247689 # 182680 / 64382878 = 0.28% iteration 4 modif 327843 # 282626 / 64382878 = 0.44% iteration 5 modif 413418 # 405980 / 64382878 = 0.63% iteration 6 modif 496069 # 550546 / 64382878 = 0.86% iteration 7 modif 561366 # 710517 / 64382878 = 1.10% iteration 8 modif 598700 # 875788 / 64382878 = 1.36% iteration 9 modif 600000 # 1034325 / 64382878 = 1.61% iteration 10 modif 567801 # 1175548 / 64382878 = 1.83% iteration 11 modif 510076 # 1292961 / 64382878 = 2.01% iteration 12 modif 433796 # 1384196 / 64382878 = 2.15% iteration 13 modif 349510 # 1449682 / 64382878 = 2.25% iteration 14 modif 267371 # 1493038 / 64382878 = 2.32% iteration 15 modif 194659 # 1519796 / 64382878 = 2.36% iteration 16 modif 135778 # 1535222 / 64382878 = 2.38% iteration 17 modif 90864 # 1543743 / 64382878 = 2.40% iteration 18 modif 58784 # 1548367 / 64382878 = 2.40% iteration 19 modif 37306 # 1550830 / 64382878 = 2.41% iteration 20 modif 23232 # 1552160 / 64382878 = 2.41% nb odd degrees 7318 nb added edges 0 nb odd degrees 28 nb added edges 3645 added length 312.732395725235 initial length 1511.8818424919855 degrees [444, 833, 1112, 1672, 2080, 2218, 2428, 2595, 2767, 2772] ------- nb odd vertices 28 iteration 0 iteration 0 modif 18055 # 1552928 / 64382878 = 2.41% iteration 1 modif 11117 # 1555011 / 64382878 = 2.42% iteration 2 modif 8346 # 1556008 / 64382878 = 2.42% iteration 3 modif 6811 # 1557026 / 64382878 = 2.42% iteration 4 modif 6056 # 1558080 / 64382878 = 2.42% iteration 5 modif 5889 # 1559203 / 64382878 = 2.42% iteration 6 modif 6182 # 1560422 / 64382878 = 2.42% iteration 7 modif 6606 # 1561720 / 64382878 = 2.43% iteration 8 modif 7245 # 1563108 / 64382878 = 2.43% iteration 9 modif 8000 # 1564601 / 64382878 = 2.43% iteration 10 modif 8813 # 1566180 / 64382878 = 2.43% iteration 11 modif 9947 # 1567891 / 64382878 = 2.44% iteration 12 modif 11220 # 1569765 / 64382878 = 2.44% iteration 13 modif 12595 # 1571750 / 64382878 = 2.44% iteration 14 modif 14231 # 1573865 / 64382878 = 2.44% iteration 15 modif 15907 # 1576113 / 64382878 = 2.45% iteration 16 modif 17720 # 1578466 / 64382878 = 2.45% iteration 17 modif 19396 # 1580917 / 64382878 = 2.46% iteration 18 modif 21385 # 1583422 / 64382878 = 2.46% iteration 19 modif 23468 # 1586072 / 64382878 = 2.46% iteration 20 modif 25721 # 1588844 / 64382878 = 2.47% nb odd degrees 7318 nb added edges 0 nb odd degrees 0 nb added edges 3659 added length 341.68448700406753 initial length 1511.8818424919855 degrees [] end, nb added 3659 On enregistre le résultat où on souhaite recommencer à partir de ce moment-là plus tard. .. code:: ipython3 with open("added.txt","w") as f : f.write(str(added)) Et si vous voulez le retrouver : .. code:: ipython3 from ensae_teaching_cs.data import added data = added() .. code:: ipython3 from ensae_teaching_cs.special.rues_paris import eulerien_extension, distance_paris, get_data edges = get_data() with open(data, "r") as f: text = f.read() added_edges = eval(text) Chemin Eulérien ~~~~~~~~~~~~~~~ A cet instant, on n’a pas vraiment besoin de connaître la longueur du chemin eulérien passant par tous les arcs. Il s’agit de la somme des arcs initiaux et ajoutés (soit environ 334 + 1511). On suppose qu’il n’y qu’une composante connexe. Construire le chemin eulérien fait apparaître quelques difficultés comme la suivante : on parcourt le graphe dans un sens mais on peut laisser de côté une partie du chemin et créer une seconde composante connexe. .. code:: ipython3 from pyquickhelper.helpgen import NbImage NbImage("euler.png") .. image:: ml_rue_paris_parcours_44_0.png Quelques algorithmes sont disponibles sur cette page `Eulerian_path `__. L’algorithme de Hierholzer consiste à commencer un chemin eulérien qui peut revenir au premier avant d’avoir tout parcouru. Dans ce cas, on parcourt les noeuds du graphe pour trouver un noeud qui repart ailleurs et qui revient au même noeud. On insert cette boucle dans le chemin initial. Tout d’abord, on construit une structure qui pour chaque noeud associe les noeuds suivant. La fonction `euler_path `__ .. code:: ipython3 from ensae_teaching_cs.special.rues_paris import euler_path path = euler_path(edges, added_edges) path[:5] .. parsed-literal:: [(2121, ['street', 3, 2121, 0.049532522902426074]), (10363, ['street', 2121, 10363, 0.1474817976215633]), (3517, ['street', 3517, 10363, 0.10602477572757586]), (2829, ['street', 2829, 3517, 0.03409802890007801]), (3515, ['street', 3515, 2829, 0.060836636019222866])] Le label ``street`` signifie que l’arête provient de l’ensemble des rues, le label ``jump`` signifie que c’est une arête ajoutée. Pour couper le parcours en 8 (8 voitures), il suffit de couper le chemin en 8 parts presque égales en trouvant 8 arêtes ``jump`` presque également réparties le long du chemin eulérien. On peut bien évidemment couper à une arête ``street`` mais celle-là devra faire partie d’un des deux ensembles pas l’arête ``jump`` qui peut être jetée. On peut envisager une approche dichotomique. Couper en deux, recouper en deux chaque intervalle et minimiser sur la meilleur arête ``jump`` du début. Il reste maintenant à prendre en compte les sens interdits. Cette modification peut intervenir à deux endroits : - Soit le nombre de sens interdit est faible et on peut s’en dépatouiller en parcourant le plus possible des rues dans le bon sens, en choisissant le plus les arcs dans le bon sens lors de la création du chemin eulérien. - Soit on crée un graphe eulérien orienté (pour chaque noeud, les nombres d’arêtes sortantes et entrantes sont égaux, voir `Euler Circuit in a Directed Graph `__). Dans le cas où on souhaite que les voitures partent toutes du même point et reviennent à ce même point, la solution précédente fournira une borne supérieure (il suffit d’ajouter des arêtes ``jump`` pour amener et ramener les voitures). Algorithme optimal ------------------ La variante de l’algorithme de `Kruskal `__ propose une solution approchée pour apparier les noeuds de degré impair. On cherche à minimiser la somme des distances entre les noeuds apparier. Il existe un algorithme optimal pour résoudre ce problème : l’\ `algorithme d’Edmonds pour les couplages `__. Variantes --------- Sens interdit et gaphe orienté ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Si la ville contient des sens interdits, c’est comme si le graphe était orienté. Chaque arc ne peut être parcouru que dans un sens. Il faut alors distinguer les degrés entrants et sortants de chaque noeud. Il faut s’assurer pour chaque noeud que le nombre d’arc entrant et sortant sont identiques. Si ce n’est pas le cas, on se sert de l’algorithme d’appariement pour recréer des arcs. Windy postman problem ~~~~~~~~~~~~~~~~~~~~~ C’est une variante pour laquelle le coût d’un arc n’est pas le même selon qu’on le parcourt dans un sens ou dans l’autre (à contre sens). Ce problème est `NP complet `__.