Bonjour à tous,

Je tente d'écrire un programme permettant de résoudre le fameux problème du voyageur de commerce par la méthode gloutonne.
La solution gloutonne donne une distance de 810 km mais en sollicitant mon programme, j'obtiens 503 km...
Une erreur doit se nicher au niveau d'une boucle j'imagine mais impossible de mettre le doigt dessus ...

Pourriez-vous jeter un coup d'oeil à mon bout de code s'il vous plait ?
Je vous remercie pour votre aide,
Excellente journée !

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
 
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]))