Algo "glouton" en python et voyageur de commerce

Bonjour à tous,
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
  • [Utilisateur supprimé]
    Modifié (May 2023)
    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.
  • [Utilisateur supprimé]
    Modifié (May 2023)
    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 donne
    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
    =========
    Petite 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 ?
  • Greg0606
    Modifié (May 2023)
    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 ! 
Connectez-vous ou Inscrivez-vous pour répondre.