Algorithme définissant l'itinéraire.
Fidèle
-
drazx974 Messages postés 48 Date d'inscription Statut Membre Dernière intervention -
drazx974 Messages postés 48 Date d'inscription Statut Membre Dernière intervention -
Bonjour,j'ai un problème. Dans mes travaux personnels d'étudiants je dois réaliser un algorithme définissant l'itinéraire d'un commerçant sur les 6 villes d'une région de mon pays connaissant les différentes distances qui les séparent les unes des autres. Voici les différentes distances:
Ville 1 vers ville2 = 200km
Ville 1 vers ville3 = 110km
ville 1 vers ville4 = 60km
ville1 vers ville5 = 270km
ville1 vers ville 6 = 80km
En sachant que Ville 1 est la source (point de départ).
Merci
Ville 1 vers ville2 = 200km
Ville 1 vers ville3 = 110km
ville 1 vers ville4 = 60km
ville1 vers ville5 = 270km
ville1 vers ville 6 = 80km
En sachant que Ville 1 est la source (point de départ).
Merci
A voir également:
- Algorithme définissant l'itinéraire.
- Itinéraire google map entre deux adresses - Guide
- Mappy itinéraire - Télécharger - Transports & Cartes
- Logiciel algorithme euromillion - Télécharger - Loisirs créatifs
- Itinéraire michelin gratuit - Télécharger - Transports & Cartes
- Via Michelin - Télécharger - Transports & Cartes
2 réponses
Euh, tu n'as pas les autres distances (2 vers 3, 2 vers 4, etc.) ? Sans elles, ça va être dur de déterminer le plus court chemin ;-)
Si tu n'as que 6 villes, tu peux te permettre d'y aller bourrin et de calculer la distance du voyageur pour chaque permutation et de renvoyer la plus petite. Par contre, cette méthode est loin de passer à l'échelle (720 itinéraires possibles avec 6 villes, 3 millions avec 10...).
Si tu en as plus, tu trouvera des algos détaillés (donnant une réponse optimale ou approchée) en cherchant "travelling salesman problem" sur google
Si tu n'as que 6 villes, tu peux te permettre d'y aller bourrin et de calculer la distance du voyageur pour chaque permutation et de renvoyer la plus petite. Par contre, cette méthode est loin de passer à l'échelle (720 itinéraires possibles avec 6 villes, 3 millions avec 10...).
Si tu en as plus, tu trouvera des algos détaillés (donnant une réponse optimale ou approchée) en cherchant "travelling salesman problem" sur google
