Bonjour à toutes et toutes,

dans le cadre de mon projet, je travaille sur le GPS, plus particulièrement sur le méthode de recherche du plus court chemin. J'ai lors implémenté l'algorithme de Dijkstra afin de réaliser une simulation. Il fonctionne mais Le problème est qu'il ne marche que si je rentre 'Lyon','Paris'; si je rentre l'inverse il ne marche pas et si je rentre d'autres villes, il me renvoie le même résultat que si j'avais rentré 'Lyon','Paris'. Je ne comprends pas pourquoi. 

Je  vous remercie par avance, 

Bonne journée 

 

-
Edité par est21 12 avril 2018 à 12:07:46

Bonjour,

Peux tu copier-coller le code directement? Je regarderai ca demain après midi ( sauf s'il y a une réponse avant ). Juste à la lecture du code je n'ai pas trouver l'incohérence mais la fatigue fait peut-etre son effet

Merci

Bonsoir, merci pour votre réponse.

Bonne soirée,

Voici le code:

graphe_villes={'Roanne':{'Lyon':85,'Beaune':148},

'Beaune':{'Lyon':157,'Auxerre':148},

'Lyon':{'Roanne':85,'Beaune':157,'Auxerre':302,'Bourg':87},

'Auxerre':{'Lyon':302,'Beaune':148,'Bourg':253,'Paris':167},

'Bourg':{'Lyon':87,'Auxerre':253,'Paris':428},

'Paris':{'Auxerre':167,'Bourg':428}}

def dijkstra_PCC(G,depart,arrivee,visites=[],distance={},predecesseur={}):

if depart not in G:

raise TypeError

if arrivee not in G:

raise TypeError

if depart==arrivee:

chemin=[]

pred=arrivee

while pred!=None:

chemin.append(pred)

pred=predecesseur.get(pred,None)

print('plus court chemin:'+str(chemin)+"distance(km)="+str(distance[arrivee]))

else:

if not visites:

distance[depart]=0

for voisin in G[depart]:

if voisin not in visites:

nouvelle_dist=distance[depart]+G[depart][voisin]

if nouvelle_dist<distance.get(voisin,float('inf')):

distance[voisin]=nouvelle_dist

predecesseur[voisin]=depart

visites.append(depart)

nonvisites={}

for i in G:

if i not in visites:

nonvisites[i]=distance.get(i,float('inf'))

x=min(nonvisites, key=nonvisites.get)

dijkstra_PCC(G,x,arrivee,visites,distance,predecesseur)

Bonjour,

Avant de te donner la solution à ton problème, quelques conseils lorsque tu demandes de l'aide:

• Place ton code dans les balises de code. Là où tu écris ton message, il y a un bouton pour le faire </>.
• Il faut toujours donner l'entièreté du code. Tu ne nous a mis que la fonction mais non les appels à cette fonction pour tes tests.
• "Ca ne marche pas" n'est pas utile pour recevoir de l'aide. Donne tout le Traceback ainsi que le message d'erreur dans son entièreté.

J'ai pris la peine de recopier le code que tu as fournis en texte brut. J'ai du ajouter manuellement les indentations. Et j'ai dû ajouter quelques tests.

Je suppose que ton erreur n'apparaît jamais au premier appel à cette fonction. C'est toujours lors d'un deuxième appel. La raison est simple mais surprend tout le monde la première fois, moi y compris ! Le problème est que lorsque tu définis la fonction dijkstra_PCC, tu donnes une liste et deux dictionnaires comme default arguments. Ces objets sont créés à la définition de la fonction. Ce qui signifie que comme ce sont des objets mutables, ils sont modifiés par le premier appel à cette fonction mais lors du deuxième appel, ils ne sont pas ré-initialisé. Ils conservent les éléments du dernier appel. Et ça c'est pas bon. 

Pour voir une démo de ce problème, j'ai fait un petit code sur Python tutor qui démontre le problème : https://goo.gl/x74Kn8

En Python, la règle est de ne jamais utiliser des objets mutables comme default argument. On utiliser comme default argument la valeur None et on vérifiera dans la fonction si l'argument est None auquel cas on assignera une nouvelle liste vide (ou un dictionnaire vide).

graphe_villes={'Roanne':{'Lyon':85,'Beaune':148},
    'Beaune':{'Lyon':157,'Auxerre':148},
    'Lyon':{'Roanne':85,'Beaune':157,'Auxerre':302,'Bourg':87},
    'Auxerre':{'Lyon':302,'Beaune':148,'Bourg':253,'Paris':167},
    'Bourg':{'Lyon':87,'Auxerre':253,'Paris':428},
    'Paris':{'Auxerre':167,'Bourg':428}}


def dijkstra_PCC(G,depart,arrivee,visites=None,distance=None,predecesseur=None):
    visites = visites or []
    distance = distance or {}
    predecesseur = predecesseur or {}
    if depart not in G:
        raise TypeError
    if arrivee not in G:
        raise TypeError
    if depart==arrivee:
        chemin=[]
        pred=arrivee
        while pred!=None:
            chemin.append(pred)
            pred=predecesseur.get(pred,None)
        print('plus court chemin:'+str(chemin)+"distance(km)="+str(distance[arrivee]))
    else:
        if not visites:
            distance[depart]=0
        for voisin in G[depart]:
            if voisin not in visites:
                nouvelle_dist=distance[depart]+G[depart][voisin]
                if nouvelle_dist<distance.get(voisin,float('inf')):
                    distance[voisin]=nouvelle_dist
                    predecesseur[voisin]=depart
        visites.append(depart)
        nonvisites={}
        for i in G:
            if i not in visites:
                nonvisites[i]=distance.get(i,float('inf'))
        x=min(nonvisites, key=nonvisites.get)
        dijkstra_PCC(G,x,arrivee,visites,distance,predecesseur)

if __name__ == '__main__':
    dijkstra_PCC(graphe_villes, "Lyon", "Bourg")
    dijkstra_PCC(graphe_villes, "Lyon", "Paris")
    dijkstra_PCC(graphe_villes, "Beaune", "Paris")

Il y a quelques petites choses à dire sur le code aussi. Je ne m'attarderai que sur un seul point. Lorsqu'on entre une ville qui n'est pas dans le graphe, c'est un peu bizarre de balancer un TypeError. On utilise ce genre d'exception lorsque le type reçu n'est pas celui attendu. Dans ce cas, ce serait plutôt un KeyError je trouve, étant donné qu'on ne trouve pas la ville. On pourrait ajouter un petit message pour donner un peu plus de contexte aussi.

-
Edité par Dan737 13 avril 2018 à 8:25:43

Bonjour, tout d'abord un grand merci pour votre réponse! Je n'avais effectivement pas pensé à ce problème 

Ensuite, excusez-moi, c'est la première fois que je poste, et je ne savais pas qu'il fallait faire cela.

Juste, je ne comprends pas à quoi servent les 4 dernières lignes que vous avez rajouté .

Merci encore, bonne journée

Salut

J'espère que tu comprends les lignes 42-44. Ce sont juste des petits tests en appelant la fonction avec des lieux différents.

Le test en ligne 41 ne sera vrai que si le script est exécuté et non importé. Autrement dit, lorsque tu fais dans la console python mon_script.py, la variable __name__ créée par Python vaudra "__main__".

Par contre si tu exécutes un autre script qui lui importe ton module avec un import mon_script, lors de l'import tout le script est lu. Et donc les fonctions test seraient exécutées. Cependant lorsque le module est importé, sa variable __name__ sera égale au nom du module, donc à "mon_script", et la condition du if sera fausse, donc les lignes 42-44 ne seront pas exécutées.

J’ai compris , merci beaucoup !

Dan737 a écrit:

Je suppose que ton erreur n'apparaît jamais au premier appel à cette fonction. C'est toujours lors d'un deuxième appel. La raison est simple mais surprend tout le monde la première fois, moi y compris ! Le problème est que lorsque tu définis la fonction dijkstra_PCC, tu donnes une liste et deux dictionnaires comme default arguments. Ces objets sont créés à la définition de la fonction. Ce qui signifie que comme ce sont des objets mutables, ils sont modifiés par le premier appel à cette fonction mais lors du deuxième appel, ils ne sont pas ré-initialisé. Ils conservent les éléments du dernier appel. Et ça c'est pas bon. 

-
Edité par Dan737 il y a environ 8 heures

Eheu, de ce que j'ai vu sur ton test, ça signifie que l'objet mutable devient global ? C'est super bizarre comme comportement.

Il n'est pas global, il appartient à la déclaration de la fonction. Voici une explication un poil plus élaborée. http://docs.python-guide.org/en/latest/writing/gotchas/#mutable-default-arguments

-
Edité par Dan737 13 avril 2018 à 16:59:45

Ah c'est bon j'ai compris C'est super logique en faite... mais impossible a debugger si tu ne connais pas lol

Merci pour l'info

En effet Moi aussi je me suis fait avoir par cet étrange comportement et ça m'a pris un long moment avant de découvrir l'origine du problème. Une fois attrapé, on n'oublie plus !