Algorithme Christofides (à la main)
On février 1, 2021 by adminJe suis cet exemple dalgorithme: https://en.wikipedia.org/wiki/Christofides_algorithm#example
The graph:
[! [entrez la description de limage ici] [1]] [1]
Calculate minimum spanning tree T:
[! [Entrez la description de limage ici] [2]] [2]
Calculate the set of vertices O with odd degree in T
Identique à « the arbre couvrant minimum T « car le degré de tous les sommets est impair.
Form the subgraph of G using only the vertices of O
(comme tous étaient impairs, cela devrait nous donner le graphe original) [! [ entrez la description de limage ici] [1]] [1]
Construct a minimum-weight perfect matching M in this subgraph
( Je ne sais pas si je a bien fait ) [! [entrez la description de limage ici] [3]] [3]
Unite matching and spanning tree T ∪ M to form an Eulerian multigraph
[! [entrez la description de limage ici] [4]] [4]
Ce nest certainement pas correct.
Quest-ce qui ne va pas?
Commentaires
- Remarque: toutes les images du message semblent avoir disparu. Lauteur a-t-il les originaux?
Réponse
En fait, vous avez toujours eu raison . Cependant, vous navez pas encore terminé lalgorithme Christofides.
La prochaine étape est « Calculer le tour dEuler ».
Dans la dernière image , vous avez obtenu un multigraphe dont tous les sommets ont des degrés pairs. Il doit donc avoir un chemin eulérien. Par exemple, sélectionnons le chemin eulérien A -> F -> A -> C -> B -> D -> E -> D -> A.
La dernière étape est « Supprimer les sommets répétés , donnant lalgorithme « s output ».
En supprimant le deuxième A et le deuxième D sur ce chemin ci-dessus, nous obtenons une sortie souhaitée, A -> F -> C -> B -> D -> E -> A . Terminé.
Veuillez noter quil nest pas très significatif dappliquer lalgorithme Christofides sur le graphe donné.
« Lalgorithme Christofides est un algorithme permettant de trouver des solutions approximatives à le problème du voyageur de commerce , sur des instances où les distances forment un espace métrique (elles sont symétriques et obéissent à linégalité triangulaire « . Les distances données nobéissent pas à linégalité triangulaire, puisque d (B, D) + d (D, E) = 1 + 4 < 6 = d (B , E). De plus, la distance (directe) entre A et B nest pas donnée, ce qui soulève le doute quant à savoir sil sagit dun problème de voyageur de commerce.
Commentaires
- Je suis nouveau dans ce domaine, alors merci pour les notes daccompagnement! Jai quelques questions: 1. Est-ce que chaque sommet doit être connecté lun à lautre pour que ce soit un TSP valide? Je veux dire quil est toujours possible de créer une route " TSP " même avec cette route manquante, donc je dirais quelle est valide – mais Jai eu tort avant. 2. Pensez-vous (ou savez-vous) sil est possible daugmenter les poids de certains des sommets de mon graphe de manière à ce quil obéisse à linégalité triangulaire ? Je pense que des graphiques plus désordonnés sont meilleurs pour représenter des scénarios de carte du monde réel, cest ' pourquoi je lai créé tel quel.
- 1. Vous pouvez le traiter comme un TSP si vous supposez, par exemple, que toutes les distances directes manquantes entre les villes sont suffisamment grandes ou simplement infinies. De cette façon, ces distances manquantes naffecteront pas la solution. Cependant, ce nest pas encore un espace métrique. 2. Pour respecter linégalité triangulaire, vous pouvez simplement ajouter 10 à chaque distance que vous avez spécifiée et laisser toutes les distances manquantes être égales à 20.
- Ce nest pas vrai: " Dans la dernière image , vous avez obtenu un multigraphe dont tous les sommets ont des degrés pairs. " – Les sommets E, D, A et F ont un degré impair.
- " Vous avez obtenu un multigraph ", un graphe qui est autorisé à avoir plusieurs arêtes, cest-à-dire des arêtes qui ont les mêmes nœuds dextrémité. Il y a deux arêtes entre D et E. Il y a deux arêtes entre A et F.
- Vous pouvez également consulter lexemple sur Wikipedia . " Ce nest pas un chemin eulérien car vous visitez un sommet plus dune fois dans ce chemin ". Le chemin eulérien consiste à visiter chaque arête une seule fois. Vous parlez de chemin hamiltonien.
Laisser un commentaire