Bonjour la commu'

J'ai un projet : Ce projet consiste à trouver la façon de faire circuler x boules d'un point A à un point B en le moins d'étapes possibles à partir d'un graph'. J'ai comme condition le fait qu'il ne peut y avoir qu'une boulle par noeud excepté le noeud de départ et celui d'arrivé. Du coup il me faut trouver les chemins les plus optimisés pour arriver à mes fins en le moins d'étapes possibles.

Aujourd'hui j'ai un problème, je ne vois pas trop comment le regler, je m'explique :

J'ai comme but de trouver N chemins les plus court d'un point de départ à un point d'arrivé sans qu'a aucun moment les chemin ne passent par le même noeud. J'ai été voir du côté de l'algorithme de Dijkstra et j'ai pu donc determiner (à l'aide de sa méthodologie) tous les chemins possible d'un point A à un point B. Ces derniers sont stockés quelque part et j'enleve de ce stockage tous les chemins qui ne vont pas à la fin. Il me reste donc une multitude de chemins et parfois certains s'entrecroisent (il ont un noeud commun) mon but est d'enlever les chemins en trop (qui font conflit du coup) en gardant le maximum de chemin possible d'un point A à un point B le plus court possible. Je m'explique en image (désolé pour la qualité mais j'ai pas l'habitude de gimp)

Donc dans ce graph : On part du noeud 1 pour arriver au noeud 8 : On peut voir les chemins suivants :

1-2-3-4-5-6-7-8

1-2-10-8

1-9-10-2-3-4-5-6-7-8

1-9-10-8

1-11-12-13-8

Donc de ces chemins on peut voir que le dernier ne rentre en conflit avec aucun autre car il n'a aucun noeud commun avec les autres (excepté le point de départ et d'arrive mais en même temps c'est normal) donc celui là je le garde.

Après j'ai les deux chemins qui partent depuis 9 et les deux autre qui partent depuis 2

Je vois que le chemin le plus court rentre en conflit avec les deux autres possible partant de 9, donc je me dis celui là je ne le prend pas car sinon je ne peux rien faire arriver depuis 9 et du coup un chemin de l'arrivé ne sera pas utilisé. Donc je me dis. Prend le 1-9-10-8 car il est plus court que l'autre partant de 9 et donc j'ai mon deuxieme chemin.

Comme j'ai écarté le chemin le plus court partant de 2 il ne m'en reste plus qu'un et c'est le plus long. Et la je me dis voilà j'ai mes chemins. Cependant ce choix est fait d'une premiere part humainement et vois la chose comme étant bonne. Sauf que s'il y à entre 1 et 3 boules il est préférable d'utiliser le chemin 1-2-10-8

entre 4et 7 boules il est préférables d'utiliser 1-2-10-8 et 1-11-12-13-8, au dela les chemins les plus optimisés seront 1-9-10-8, 1-11-12-13-8 et 1-2-3-4-5-6-7-8.

Et du coup je me pose la question suivante. Ne serais-ce pas mieux de garder tous les chemins possibles vers la sortie. Et d'emprunter les chemins adéquat en fonction du nombre de boules que j'ai à faire traverser. Si c'est le cas (au moment ou j'écris ce message je me demande si c'est pas justement le mieux à faire)

Alors je n'ai aucune idée le la démarche à suivre pour creer un algorithme autours de ça. Je vous poste ce message en éspérant que vous pourriez maider et bien sur je suis en train de me pencher sur le sujet en ce moment même.

Merci;

Bien à vous,

Nicolas Wadel

Edit : Je viens de voir en fait qu'il y a autant de temps de parcours entre les deux PATH les plus courts. Du coup en fait il faudrais imaginer une etape de plus sur 1-9-10 pour montrer ce que je veux dire.

-
Edité par Nicolas Wadel 15 avril 2016 à 21:07:41

Bonjour,

Dans tes élucubrations, tu sembles oublier une chose : la solution optimale — si tu la trouves ­— dépend du nombre de boules que tu auras au départ.

Imaginons un graph simple, où tu n'aurais que deux chemins possibles entre le point de départ et l'arrivée, le premier aurait une longueur de 3 (départ + nœud intermédiaire + arrivée), le second de 10, sans croisement. En n'utilisant que le chemin le plus court, pour X boules, tu peux résoudre le problème en X+1 étapes. Tant que tu auras 8 boules ou moins, il s'agira de la solution optimale. Mais à partir de 8, il te deviendra préférable d'utiliser les deux chemins en parallèle.

Un algorithme de Dijkstra te permettra de trouver le plus court chemin, mais ne tiendra pas compte des contraintes. Itérer sur l'ensemble des solutions possibles pour ne garder que l'optimale serait bien trop lourd en terme de complexité. Mais ça semble tout adapté pour un algorithme de ce genre : https://fr.wikipedia.org/wiki/Algorithme_de_colonies_de_fourmis

Bon après quelques temps de recherche j'ai trouver un algo maison. Merci cependant de m'avoir éclairer sur le sujet =) ! A voir ce que ça donne du coup !