A propos d'algorithmes glouton et d'un voyageur de commerce. A l'aide svp

**William06** · 30/04/2023, 20h28

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]))

**wiztricks** · 01/05/2023, 11h58

Salut,

Envoyé par William06

Une erreur doit se nicher au niveau d'une boucle j'imagine mais impossible de mettre le doigt dessus ...

Il y a assez peu de villes pour que la vérification du résultat "à la main" soit rapide et facile.

- W

**Sve@r** · 01/05/2023, 12h09

Bonjour

Envoyé par William06

La solution gloutonne donne une distance de 810 km mais en sollicitant mon programme, j'obtiens 503 km...

Vu que ton programme donne une solution cohérente, qui passe effectivement par toutes les villes, et dont le total des distances fait effectivement 503km, je ne vois pas comment tu peux dire que "la" solution est de 810km.

Envoyé par William06

if pp == None

On ne compare pas "None" via l'égalité mais via "is" => if pp is None => https://peps.python.org/pep-0008/#pr...ecommendations

[edit]j'ai compris d'où sort le 810. Il sort de l'algorithme "simpliste" => prendre le minimum de ce qui est proposé

A la ville 1, le minimum c'est 55 pour la ville 2 (total 55)
A la ville 2, le minimum c'est 176 pour la ville 4 (total 231)
A la ville 4, le minimum c'est 123 pour la ville 5 (total 354)
A la ville 5, le minimum c'est 153 pour la ville 3 (total 507)
Et à la ville 3, le retour à la ville 1 fait 303 (total 810)

Toutefois la différence entre cet algo et le tien c'est que cet algo part de la ville 1 (le tien part de la ville 2) et qu'il retourne à la ville d'origine (le tien se termine à la dernière ville sans boucler). Donc tu as ta réponse sur le pourquoi de la différence.

**jurassic pork** · 01/05/2023, 14h15

Hello,
il y a un truc de louche dans ton code :
c'est que l'appel de la fonction :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

circuit_glouton(1,dist,villes[0])

ne correspond pas à la définition de la fonction :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

def circuit_glouton(villes, dist, depart)

villes n'est pas utilisée dans ta fonction.

Ami calmant, J.P

**Sve@r** · 01/05/2023, 14h28

Je crois qu'il y a un autre souci: la numérotation des villes va de 1 à 5. Mais dans un tableau, la numérotation commence à 0.
Fatalement ville[1] présumé taper dans la première ville (et qu'on voit dans dist[villes][i] < dist[villes][pp]) tape en réalité dans la seconde. C'est pour ça que son résultat part de la ville 2.
Si on renumérote les villes correctement (de 0 à 4) on obtient le parcours que j'ai cité en 507 km qui, si on le fait reboucler sur la ville de départ, fait alors 810km.
Et (accessoirement) si on commence réellement par la ville 2, alors le voyage n'en fait plus que 809.

**wiztricks** · 01/05/2023, 15h01

Envoyé par Sve@r

Je crois qu'il y a un autre souci: la numérotation des villes va de 1 à 5. Mais dans un tableau, la numérotation commence à 0.

Certes mais ce numéro va dans villes qui n'est pas utilisé.

Si la question est pourquoi on ne trouve pas 810 kms, le soucis est que la ligne 24 est un copie/coller de la ligne 22:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

       distance_total += cumul_etapes(courante, suivante,  dist)

A la sortie de la boucle, courante == suivante et ça ajoute 0.

On devrait (à la place) ajouter la distance entre courante/suivante et départ.

- W

**jurassic pork** · 01/05/2023, 15h57

Hello,
finalement, en prenant en compte les remarques à Sve@r et Wiztricks , on obtient bien 810 avec ce code :

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
villes = ['ville1','ville2','ville3','ville4','ville5']
 
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(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, depart,  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 is 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
 
circuit_glouton(0)

Remarques :
1 - circuit_glouton n'a plus qu'un paramètre qui est l'indice de la ville de départ ( indice qui commence à 0). je me suis aperçu que les autres paramètres ne servaient pas car les fonctions prenaient en compte les variables définies au début du programme. D'ailleurs qui peut m'expliquer le pourquoi car je croyais qu'il fallait définir les variables en global pour avoir ce type de comportement (à noter que ces variables ne sont pas modifiées dans les fonctions). Le test a été effectué en python 3.10.
2 - j'ai remplacé les villes par des noms.
3 - Le print de la dernière ligne ne servait à rien et retournait None. Les print sont faits dans les fonctions
Voici le résultat :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 il faut aller de ville1 à ville2 en 55 km
 il faut aller de ville2 à ville4 en 176 km
 il faut aller de ville4 à ville5 en 123 km
 il faut aller de ville5 à ville3 en 153 km
 il faut aller de ville3 à ville1 en 303 km
 la distance totale est de : 810

Ami calmant, J.P

**Sve@r** · 01/05/2023, 15h58

Envoyé par wiztricks

Certes mais ce numéro va dans villes qui n'est pas utilisé.

Ca reste quand-même un bug (suffit de remplacer par villes = [5, 1, 2, 3, 4] et on voit l'IndexError sortir)

Envoyé par jurassic pork

D'ailleurs qui peut m'expliquer le pourquoi car je croyais qu'il fallait définir les variables en global pour avoir ce type de comportement

Toute variable définie dans le scope global (hors de toute fonction) est implicitement connue des fonctions appelées après (mêmes si définies avant), mais en lecture seule.
L'instruction global var dans la fonction sert juste à rendre la variable "var" modifiable par la fonction (et c'est souvent pas une bonne idée)

**wiztricks** · 01/05/2023, 16h34

Envoyé par Sve@r

Ca reste quand-même un bug (suffit de remplacer par villes = [5, 1, 2, 3, 4] et on voit l'IndexError sortir)

Certes mais je me limite à la question posée... et à (essayer de) donner des pistes au PO pour trouver tout seul.
Ecrire plus proprement un code assez classique dont on trouve déjà plusieurs variantes sur Internet a (pour moi) un intérêt limité.

- W

**jurassic pork** · 01/05/2023, 18h12

voici des données avec des villes françaises :
villes=["Brest","Paris","Nantes","Rennes","Caen"]
dist=[[0,592,295,243,374],[592,0,385,354,238],
[295,385,0,113,290],[243,354,113,0,185],
[374,238,290,185,0]]
cela donne :

il faut aller de Brest à Rennes en 243 km
il faut aller de Rennes à Nantes en 113 km
il faut aller de Nantes à Caen en 290 km
il faut aller de Caen à Paris en 238 km
il faut aller de Paris à Brest en 592 km
la distance totale est de : 1476

En "Visuel" (en utilisant le module python folium qui génère un fichier html qui affiche une carte open streetmap avec des graphiques dessus) :

Nom : AlgoVoyageur.jpg
Affichages : 119
Taille : 86,5 Ko