Algorithme de chemin le plus court en passant par des étapes

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)

Pièce jointe 157551

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é :

Pièce jointe 157552

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 !

Je ne comprends pas : tu recherche le chemin le plus court et tu considère que si celui-ci amène à un croisement, ce chemin est moins "optimisé" qu'un autre plus long sans croisement ? Si oui, tu as oublié cette contrainte de 'non-croismeent' dans ton énoncé.

Sinon, sauf erreur de ma part (et sans prendre en compte ton problème de croisement), c'est le problème du <voyageur de commerce> (Travelling salesman problem en anglais). Juste avec ces 3/4 mots(problème voyageur de commerce / travelling salesman problem), tu vas trouver pas mal de ressources sur ce sujet.

Salut !

Je ne dirais pas que le problème viens du croisement mais plutôt du fait que je fais des très long trajet pour rien.

Si on regarde le premier schéma le trajet J a D et de F a départ est une perte de temps. C'est donc pour cela que je cherche une autre solutions pour mon algorithme.

Je vais regarder ce que tu m'a dis, merci !

Cette facon de faire me plait énormément, vous en pensez quoi ?

Pièce jointe 157585

Citation:

---

Envoyé par Naografix

je cherche une autre solutions pour mon algorithme.

---

Citation:

---

Envoyé par Naografix

Salut !
Cette facon de faire me plait énormément, vous en pensez quoi ?

---

Si je comprends bien, tu choisis les segments à parcourir en prenant à chaque fois le moins long parmi tous les segments possibles à partir du point où tu te situes.
On appelle cela un algorithme "glouton". C'est une approche heuristique qui peut se justifier, puisque par définition aucun algorithme exact ne peut être développé actuellement (le problème du voyageur de commerce est NP-hard).

Il existe d'autres heuristiques plus compliquées spécifiques au voyageur de commerce. Tu as déjà su en implémenter une et c'est déjà très bien. En plus,elle a l'air de te plaire, et énormément en plus :lol:

Alors soit tu t'en satisfait, soit tu y vas à fond et fais de courtes recherches et implémente une heuristique théoriquement meilleure.

Hehe jai oublier de mettre résolu

Car j'ai enfin de compte reussi a faire ce que le schéma faisait

Cest un peu brute, car si jamais jai 100 point et bien cest 100x100 trajet qui vont être testé

Mais bon, sur une 15 Aine de point ca se fait relativement vite.

Voila voila !

Je sais que le sujet a été résolu, mais je crois que ce sujet est traité dans la partie spécialité du cours de maths de Tle ES (il n'est pas disponible en S).
Voilà voilà...

Bonjour,

N'est-ce pas de l'algorithme de Dijkstra dont tu parles ?

Si après vérification, il s'agit de cet algorithme, pourquoi ?

Pour donner une référence précise au premier posteur.