Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Discussion :
[Graphe] Obtenir la meilleur combinaison d'arrete afin de passer par tous les sommets
Bonjour bonjour,
voila mon problème j'ai un graphe pondéré complet de N sommets.
Je recherche a calculer la somme des arêtes tel que chaque sommet n'apparaisse que dans une seule arête, et que cette somme soit la plus faible possible.
Est ce que vous savez s'il existe des algo permettant ceci, ou si je dois faire le mien ?
J'avais pour idée de lancer un meilleur chemin, en obligeant l'algo a passer par tous les sommets, mais je ne sais pas si c'est possible
Bonjour,
- une arète étant composée de deux sommets, je ne vois pas comment tu peux faire en sorte qu'un sommet n'apparaisse qu'une seule fois.
- ce que tu veux faire c'est tout simplement résoudre un problème de voyageur de commerce. Donc renseigne toi là dessus, mais sache que c'est un problème NP-Complet et que par conséquent il n'y a pas de solution miracle.
Consignes aux jeunes padawans : une image vaut 1000 mots !
- Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
- Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
-ton poste tu dois marquer quand la bonne réponse tu as obtenu.
En fait si on a par exemple le graphe suivant
A -- B
| \ / |
| / \ |
C -- D
Le voyageur de commerce devrait mrhé en effet (un peu à la ramasse de ne pas y avoir penser désolé) mais il va me donner, par exemple :
A -- B -- C -- D
Hors, la liaison entre B et C je m'en fous en fait. L'avoir n'est pas faux, c'est juste que son calcule ne m'apporte rien.
Peut être ce lien peut t'aider : http://fr.wikipedia.org/wiki/Arbre_couvrant
Merci bien ^^
Je pense avoir trouvé un algo, j'espère qu'il va convenir, et que je n'aurais pas de mauvaise surprise.
L'idée est la suivante :
Je prend l'arête ayant le poids le plus fort. Si les deux sommets de cette arête ont aux moins 1 autre sommet, alors je met mon arête dans une pile, et je la supprime du graphe.
Par contre si jamais l'un des sommet de cet arete n'est lié qu'à celle ci (donc si je venais à supprimer mon arête, j'isolerais mon sommet), alors je la laisse ou elle est.
Je boucle ainsi jusqu'à avoir supprimer n/2 arêtes.
Ensuite, si jamais il me reste n/2 arête à parcourir dans mon graphe, alors que je n'ai pas encore supprimer n/2 arêtes, je prend l'arete en tête de pile (donc la dernière supprimée), je la remet dans mon graphe, et je reprend mon algo cette fois en ne la supprimant pas.
Et si je me goure pas, à la fin j'ai supprimer toutes les plus mauvaises arêtes, et tous les sommets n'appartiennent qu'à une seule arête ^^
Répondre avec citation
Partager