Recherche du chemin le moins coûteux avec contraintes particulières

[invitefee2e751]

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...)

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 !
-----

[invite5c4e9cf8]

Bonjour,

L'algorithme de Bellman-Ford permet de trouver le plus court chemin entre 2 sommets. Il est neammoins plus lent que l'algorithme de Dijkstra qui fait la même chose.L'intérêt de Bellman-Ford même si il est plus lent c'est qu'il peut être distribué au lieu d'être centralisé et gérer des coûts négatifs, mais il me semble que ça ne concerne pas ton problème donc si tu veux calculer le plus court chemin entre 2 sommets l'algorithme de Dijkstra est conseillé.

Mais ton problème est plus complexe que simplement un plus court chemin. Je te conseille de te documenter sur le Traveling Salesman Problem (TSP) il me semble que c'est assez similaire à ton problème, voire même exactement le même problème formulé autrement. C'est un peu le Saint-Graal des problèmes en informatique y a énormément de solutions qui sont proposées, mais toutes sont exponentielles car c'est un problème NP-Complete.

Une méthode assez intéressante que je peux te proposer c'est le Genetic Algorithm, qui a été appliqué dans ce genre de cas NP-complete, mais c'est juste une idée, il n'existe pas de solution polynomiale.

[invitefee2e751]

Merci pour ta réponse, je ne connaissais pas l'algorithme de Dijkstra (que de nom) et effectivement il a l'air plus adapté à mon problème.
Le TSP est très similaire aussi. Dans les deux cas, le seul truc qui coince est ma contrainte que seuls certains sommets sont accessibles à chaque étape. Je vais pour l'instant essayer d'adapter l'algorithme de Dijkstra et si je n'y arrive pas j'irai voir du côté des algorithmes génétiques (ils m'ont l'air plus complexes à comprendre et à mettre en oeuvre)

Je suis bien sûr preneur de toute proposition

[Dlzlogic]

Bonjour,
A mon avis pour résoudre facilement et économiquement votre problème, ce n'est qu'une question de gestion et organisation des données.
Personnellement, j'ai fait un truc de ce genre, il s'agissait de trouver le meilleur chemin suivant certaines conditions (contexte trajet de véhicules de secours).
L'élément de base était le sommet. C'est un objet qui comporte plusieurs attributs : les différents sommets auxquels ils sont directement connectés et pour chaque connexion, des paramètres.
Il suffit de rajouter un paramètre "détruit". Une fois activé, l'objet "sommet" correspondant n'est plus adressable. Mais aucune information initiale n'est perdue, c'est à dire qu'on peut réactiver les sommets.
L'algorithme de Dijkstra est très efficace.

[A voir en vidéo sur Futura]

[invite9dc7b526]

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

le graphe n'évolue pas mais tu cherches un chemin hamiltonien.

[invite6c250b59]

Je pense que mon problème n'est pas non plus très original

Est-ce qu'il n'y a pas des cas où ton problème est identique ? Par exemple supposons que le plus court chemin trouvé soit 51234. A priori cela ne respecte pas ton critère que le premier est dans [1, 2, 3]. Sauf que 51234 semble la même chose que 12345 qui est valide, donc la solution n'est-elle pas valable quand même?

Une fois que ce point sera éclairci il sera plus clair si tu peux ou non utiliser une procédure simple telle que remplacer certains sommets ou certaines distances entre sommets avant de lancer l'algorithme de ton choix.