Algo "glouton" en python et voyageur de commerce
désolé de vous casser les pieds mais pourriez-vous jeter un coup d’œil à mon code s'il vous plait ?
Je tente de domestiquer les algos dits gloutons en travaillant sur le problème du voyageur de commerce (visiter toutes les villes une fois et revenir à la ville d'origine en faisant le moins de km...).
La solution "gloutonne" renvoie 810 km et mon programme seulement 709 ...
Une erreur doit se nicher au niveau d'une boucle j'imagine mais impossible de mettre le doigt dessus ...
Si vous pouviez m'éclairer et ainsi sauver les 3 cheveux qu'il me reste ...
Un grand merci,
Excellente journée.
villes = [1,2,3,4,5] dist = [[0 , 55 , 303 , 188 , 183], [55 , 0 , 306 , 176 , 203], [303, 306 , 0 , 142 , 155], [188, 176 , 142 , 0 , 123], [183, 203 , 153 , 123 , 0 ]] n=len(villes) def circuit_glouton(villes, dist, depart): visitees=[False]*n distance_total = 0 courante=depart for i in range (n-1): visitees[courante] = True suivante=plus_proche(courante,dist, visitees) distance_total += cumul_etapes(courante, suivante, dist) courante = suivante distance_total += cumul_etapes(courante, suivante, dist) print (' la distance totale est de :', distance_total) def plus_proche(villes, dist, visitees): pp= None for i in range(len(visitees)): if not visitees[i]: if pp == None or dist[villes][i] < dist[villes][pp]: pp = i return pp def cumul_etapes (courante,suivante,dist): distance =dist[courante][suivante] print (" il faut aller de", villes[courante], "à", villes[suivante],'en',distance, "km") return distance print(circuit_glouton(1,dist,villes[0]))
Réponses
-
J'ai cherché la description de l'algorithme glouton dans le cadre du problème du voyageur de commerce.
Je trouve ceci :Sur les N villes du problème, on commence par en relier 3 au hasard pour constituer le chemin initial (c'est un triangle).
Prenons par exemple les villes 1, 2 et 3.
Le triangle les reliant est unique donc c'est le chemin optimal pour ces 3 villes.
Pour les N-3 villes restantes (villes 4 à N), on effectue l'opération suivante :Etape i : On introduit la ville dans le chemin (ou l'enveloppe) construit à l'&tape précédente i-1, en essayant de nous assurer que le nouveau chemin obtenu allonge le moins le parcours :
Appelons C la ville à insérer. On devra supprimer un seul arc [AB] reliant deux villes A et B du trajet contruit à l'étape i-1, et le remplacer par les deux arcs [AC] et [BC]
Il faut donc choisir les deux villes A et B appartenant déjà au trajet, telles que la quantité d(A,C)+d(B,C)-d(B,C) soit minimale.Et le document en question continue en expliquant que cet algorithme ne donne pas systématiquement la meilleure solution.
Donc quelques questions :
- Ce que tu appelles l'algorithme-glouton, c'est l'algorithme ci-dessus ?
- Si oui, je ne vois pas l'initialisation 'Un triangle au hasard'
- Et comme dit dans le commentaire : on n'a pas l'assurance de trouver la solution optimale.
Si l'algorithme que tu cherches à implémenter est différent, ce serait bien d'en donner une description sommaire, avec des mots en français.
Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
L'hypocrisie est pire qu'une vérité qui fait mal. Franck Ntasamara. -
Il faut peut-être tester chaque ville comme point de départ ?Un algorithme glouton cherche la solution la meilleure, mais parmi les propositions immédiates.Algebraic symbols are used when you do not know what you are talking about.
-- Schnoebelen, Philippe -
Quelques remarques à chaud
- Ton code n'est pas très compréhensible, je vais donc essayer de le décortiquer un peu après.
- Tu as deux variables villes différentes dans circuit_glouton.
- À l’exécution j'obtiens
il faut aller de 2 à 1 en 55 km il faut aller de 1 à 5 en 183 km il faut aller de 5 à 4 en 123 km il faut aller de 4 à 3 en 142 km il faut aller de 3 à 3 en 0 km la distance totale est de : 503 None
et pas 709. - Tu considères la ville de départ comme étant visitée et tu sembles ne jamais revenir dessus : c'est pourquoi dans mon exécution on va de 3 à 3, ce qui n'a aucun sens ici.
- Tu pars de villes[0], donc la première ville, mais à l'exécution on vois qu'on part de la deuxième.
- Ton code n'est pas très compréhensible, je vais donc essayer de le décortiquer un peu après.
-
Bon, ton code étant inutilement compliqué je l'ai réécrit.
#!/usr/bin/env python3 towns=[0,1,2,3,4] towns_length=len(towns) distances=[[0 , 55 , 303 , 188 , 183], [55 , 0 , 306 , 176 , 203], [303, 306 , 0 , 142 , 155], [188, 176 , 142 , 0 , 123], [183, 203 , 153 , 123 , 0 ]] def circuit(start): visited=[False]*towns_length total_distance=0 current=start for i in range(towns_length): if i == towns_length-1: visited[start]=False visited[current]=True next=neighbour(current,visited) distance=distances[current][next] total_distance+=distance print ("(", current, ",", next, "):", distance) current=next return total_distance def neighbour(current,visited): current_distance=100000 nb=0 for i in range(towns_length): if not visited[i]: distance_to_test=distances[current][i] if distance_to_test < current_distance: current_distance=distance_to_test nb = i return nb for i in range(towns_length): print("Start:", i) print(circuit(i)) print("=========")
Ce qui me donnePetite remarque tout de même : ton algorithme fonctionne bien dans ce cas précis, mais (et je te laisse chercher) que se passe-t-il si plusieurs villes sont à une même distance d'une même autre ? Que se passe-t-il alors si tu en choisis une, un peu au pif (en gardant cet algo là, ce serait la première trouvée), telle que le cumul des distances qui s'en suit est supérieur à si tu en avais choisi une autre ?Start: 0 ( 0 , 1 ): 55 ( 1 , 3 ): 176 ( 3 , 4 ): 123 ( 4 , 2 ): 153 ( 2 , 0 ): 303 810 ========= Start: 1 ( 1 , 0 ): 55 ( 0 , 4 ): 183 ( 4 , 3 ): 123 ( 3 , 2 ): 142 ( 2 , 1 ): 306 809 ========= Start: 2 ( 2 , 3 ): 142 ( 3 , 4 ): 123 ( 4 , 0 ): 183 ( 0 , 1 ): 55 ( 1 , 2 ): 306 809 ========= Start: 3 ( 3 , 4 ): 123 ( 4 , 2 ): 153 ( 2 , 0 ): 303 ( 0 , 1 ): 55 ( 1 , 3 ): 176 810 ========= Start: 4 ( 4 , 3 ): 123 ( 3 , 2 ): 142 ( 2 , 0 ): 303 ( 0 , 1 ): 55 ( 1 , 4 ): 203 826 =========
-
Un grand merci à tous pour le coup de main...
Je vais tacher décortiquer le code qui fonctionne afin de comprendre où je me trompe , j'ai un souci avec villes[0] , c'est ce qui empeche de traiter le cas de la dernière ville je pense.
Une fois tout cela résolu, je me penche sur les questions subsidiaires dp, promis !
Encore merci.
Excellente journée !
Bonjour!
Catégories
- 164.9K Toutes les catégories
- 53 Collège/Lycée
- 22.1K Algèbre
- 37.5K Analyse
- 6.3K Arithmétique
- 57 Catégories et structures
- 1.1K Combinatoire et Graphes
- 13 Sciences des données
- 5.1K Concours et Examens
- 20 CultureMath
- 50 Enseignement à distance
- 2.9K Fondements et Logique
- 10.7K Géométrie
- 82 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 77 Informatique théorique
- 3.9K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 334 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10.1K Probabilités, théorie de la mesure
- 794 Shtam
- 4.2K Statistiques
- 3.8K Topologie
- 1.4K Vie du Forum et de ses membres