Salut a tous !
Je viens ici chercher de l'aide pour mon algorithme du chemin le plus court PAR TOUTES LES ETAPES.
Je grossis volontairement étapes car il ne s'agit pas ici d'un algorithme de pathfinder pur et dur comme A* ou autre.
Non mon problème est le suivant (je vais l'expliquer avec des noms de ville)
Rentrons dans le contexte :
Je suis un livreur et j'ai 20 colis à déposer chez 20 clients. Un colis pas client.
Je veux, par l'intermédiaire d'un algo, que celui-ci me sorte le chemin le plus court pour déposer les colis et ensuite revenir à mon point de départ (normal).
J'avais une idée : L'algorithme doit prendre le trajet le plus court entre chaque point.
Mais mon problème est le suivant : il se pourra que mon algo fasse "un retour sur les pas".
Un petit schéma s'impose (sous Paint, désoler ^^) :
Voilà ce que mon algorithme donnerait (en prenant le trajet le plus court)
On peut voir ici qu'en utilisant le chemin le plus court, mon algorithme fait "n'importe quoi" et les chemins commence a se croiser...
Maintenant voilà ce que devrait faire l'algorithme pour avoir quelque chose d'optimisé :
Donc j'ai eu plusieurs idées mais à chaque fois (en testant 3-4 fois avec différente configuration) j'arrivais à un problème de NON optimisation.
Si vous avez des idées, je prends, je prends toutes les idées que vous pourrez me fournir !
Merci !
Partager