Discussion :

[strunkfresser]

Bonjour !

Je suis confronté au problème suivant :

J'ai N sommets numérotés de 1 à N, on associe à chaque couple de sommets un coût, c'est le coût du chemin les reliant. L'objectif est de trouver le chemin de longueur N passant par N sommets distincts tel que ce chemin soit le moins coûteux possible.
Jusque là il me semble -je suis novice en informatique- que plusieurs algorithmes permettent de répondre au problème, par exemple l'algorithme de Bellman-Ford
Sauf que j'ai une contrainte supplémentaire :
A chaque étape d'un chemin de longueur N on a un certain nombre de sommets accessibles et une fois qu'on a choisi un sommet alors celui-ci n'est plus accessible pour la suite puisqu'on veut passer par N sommets distincts. En fait c'est comme si le graphe évoluait pendant la simulation

Par exemple, pour N=5, on peut imaginer la liste suivante : [[1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 4, 5], [2, 3, 4, 5], [3, 4, 5]] donnant, pour chaque étape, la liste des sommets disponibles (pour l'étape 1 on ne peut choisir que parmi les sommets 1,2,3 , pour l'étape 2 on choisit parmi 1,2,3,4 en enlevant le sommet choisi à l'étape 1 et ainsi de suite...)

Pour résoudre ça, je vous avoue que je suis légèrement à court d'idées
Je pense que mon problème n'est pas non plus très original donc j'aimerais savoir si il existe des algorithmes pouvant le résoudre (sans énumérer toutes les solutions bien sûr). Ou alors, est-il possible d'adapter l'algorithme de Bellman-Ford à mon problème ?
Je suis également preneur de la moindre idée

Merci beaucoup pour votre aide !

[nono_31]

Bonjour,

Je vous suggère de vous renseigner sur les graphes hamiltoniens.

Cordialement.

[strunkfresser]

Bonjour, merci pour le lien je vais aller voir de ce côté là !
Je me suis également pas mal renseigné sur le problème du voyageur de commerce, j'ai vu qu'il pouvait être approché par des algorithmes génétiques, j'ai essayé d'écrire un tel algorithme hier. Le souci c'est que, à part pour les cas où on peut dénombrer toutes les solutions, je ne vois pas comment évaluer la performance de l'algorithme. Certes il sort un résultat mais comment estimer à quel point ce résultat est proche de l'optimum ?

[nono_31]

Bonjour,

Pour évaluer, une solution, il faut calculer une borne inférieure.

Vous trouverez diverses ressources sur ce problème ici.

Cordialement

[dourouc05]

La meilleure estimation de la distance à l'optimum reste toujours de calculer cette solution optimale, ce qui est très souvent à portée avec des techniques d'optimisation mathématique ou de programmation par contraintes (pas vraiment triviales pour de gros problèmes).

Sinon, pour la question d'origine, non, Bellman-Ford ne permet pas de résoudre ce type de problème : c'est bien un voyageur de commerce complet (pas le meilleur chemin entre deux points, mais le meilleur cycle dans le graphe). Je ne suis pas bien sûr de comprendre ta contrainte supplémentaire : tu veux bien dire que (pour prendre les noms utilisés pour le TSP) tu dois passer une et une seule fois dans chaque ville ? C'est justement le principe du TSP .

Si tu ne veux pas trop coder, regarde du côté de Concorde. Sinon, http://laurent-ott.developpez.com/tu...el-vba-tome-3/ est une bonne introduction au domaine "avec les mains".

[strunkfresser]

Oui je dois passer une seule et unique fois par chaque ville et par exemple, sur le cas que j'ai donné dans mon premier message, la ville n°1 ne peut être visitée qu'à la première, à la deuxième ou à la troisième étape. Le chemin 2-3-4-5-1 est par exemple impossible puisque la ville n°1 est visitée à la 5e étape. J'ai donc moins de solutions possibles que pour le TSP mais ça reste ingérable par dénombrement
Merci pour les liens !