Projet ISN Terminale Demande d'aide

Parcours de graphe / plan de métro

ache a marqué ce sujet comme résolu.

Bonjour, Nous sommes un groupe de trois en classe de Terminale S,en spécialité ISN. Pour notre projet de fin d’année,nous voulons réaliser un plan de métro dans lequel il est possible de rentrer la destination d’arrivée et de départ au choix. Il donne ensuite le chemin le plus court. Le graphe est non orienté. On a réussi à parcourir le graphe avec une destination et un point de départ FIXES. En revanche, on galère pour trouver un programme qui nous permet de choisir le départ et l’arrivée. Merci de votre aide!

+0 -0

Qu’avez-vous ?

Où en êtes vous au niveau du code ? Qu’y a-t-il qui change fondamentalement si on change de point ? Implémentez vous un algorithme particulier ? A*, Dijkstra ou un simple parcourt du graphe ?

Commencez par nous montrer votre code avec un exemple de plan de métro (un code fonctionnel sur un point fixe), on verra ce qu’on peut faire pour un point variable.

+2 -0

Merci pour votre réponse. Nous avons saisi une matrice d’adjacence pour un exemple réel de graphe. En changeant "m_adjac" (l.22), on obtient toujours une distance et un chemin mais il ne correspondent pas aux résultats attendus. Le chemin proposé relie par exemple des sommets qui ne sont pas reliés. Je n’arrive pas a vous joindre la photo du graphe en revanche, voici notre code sur Python:

Nvilles = 13

 # la matrice d'adjacence est mise en place de façon très simple ici
#   M E D F C H I G J A K L B
L0 = [0,0.5,0,0,0,0,0,0,0,0,0,0,0]#M
L1 = [0.5,0,0.5,0.33,0,0,0,0,0,0,0,0,0] # la méthode append (cf. étape 3) est utilisée dans la suite E
L2 = [0,0.5,0,0,0.36,0,0,0,0,0,0,0,0]#D
L3 = [0,0.33,0,0,0,0.43,0,0,0,0,0,0,0]#F
L4 = [0,0,0.36,0,0,0,0,0,0,0.66,0,0,0]#C
L5 = [0,0,0,0.43,0,0,0,0,0,0.85,0,0,0]#H
L6 = [0,0,0,0,0,0,0,0,0.42,0.45,0,0,0]#I
L7 = [0,0,0,0,0,0,0,0,0,0.42,0,0,0]#G
L8 = [0,0,0,0,0,0,0.42,0,0,0.8,0,0,0]#J
L9 = [0,0,0,0,0.66,0.85,0.45,0.42,0.8,0,0.48,0.32,0]#A
L10 = [0,0,0,0,0,0,0,0,0,0.48,0,0,0.39]#K
L11 = [0,0,0,0,0,0,0,0,0,0.32,0,0,0.5]#L
L12 = [0,0,0,0,0,0,0,0,0,0,0.39,0.5,0]#B

m_adjac = [L0,L1,L2,L3,L4,L5,L6,L7,L8,L9,L10,L11,L12] # m_adjac[4][2] contient la valeur 5, etc. 

DIJ=list() # la liste DIJ mémorise les données du tableau (cf. étape 1)

for i in range (Nvilles):
    DIJ.append([1000000,"X","N"]) # voir commentaire page suivante

ville_select=0 # numéro de la ville sélectionnée; 0 = ville de départ
dist_interm=0 # distance pour arriver à la ville sélectionnée; 0 au départ

while ville_select != Nvilles-1:
    minimum=1000000
    for n in range(1,Nvilles):
     if DIJ[n][2]=="N":
        dist=m_adjac[ville_select][n]
        dist_totale=dist_interm+dist
        if dist != 0 and dist_totale < DIJ[n][0]:
            DIJ[n][0]=dist_totale
            DIJ[n][1]=ville_select
        if DIJ[n][0]<minimum:
         minimum=DIJ[n][0]
         pville_select=n
    ville_select=pville_select # pville_select = numéro de la prochaine ville sélectionnée
    DIJ[ville_select][2]="O"
    dist_interm=DIJ[ville_select][0]
    for i in range(1,Nvilles):
        print (DIJ[i])
    print ("\n")
chemin=list() # reconstitution du plus court chemin, en partant de la ville d'arrivée
ville=Nvilles-1
chemin.append(ville)
while ville != 0:
    ville=DIJ[ville][1]
    chemin.append(ville)

print ("plus court chemin, à lire à l'envers : ",chemin)
print ("distance totale : ",DIJ[Nvilles-1][0])

On obtient dans la console:

[0.5, 0, 'O']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']


[0.5, 0, 'O']
[1.0, 1, 'N']
[0.8300000000000001, 1, 'O']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']


[0.5, 0, 'O']
[1.0, 1, 'O']
[0.8300000000000001, 1, 'O']
[1000000, 'X', 'N']
[1.26, 3, 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']


[0.5, 0, 'O']
[1.0, 1, 'O']
[0.8300000000000001, 1, 'O']
[1.3599999999999999, 2, 'N']
[1.26, 3, 'O']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']


[0.5, 0, 'O']
[1.0, 1, 'O']
[0.8300000000000001, 1, 'O']
[1.3599999999999999, 2, 'O']
[1.26, 3, 'O']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[2.11, 5, 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']


[0.5, 0, 'O']
[1.0, 1, 'O']
[0.8300000000000001, 1, 'O']
[1.3599999999999999, 2, 'O']
[1.26, 3, 'O']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[2.02, 4, 'O']
[1000000, 'X', 'N']
[1000000, 'X', 'N']
[1000000, 'X', 'N']


[0.5, 0, 'O']
[1.0, 1, 'O']
[0.8300000000000001, 1, 'O']
[1.3599999999999999, 2, 'O']
[1.26, 3, 'O']
[2.47, 9, 'N']
[2.44, 9, 'N']
[2.8200000000000003, 9, 'N']
[2.02, 4, 'O']
[2.5, 9, 'N']
[2.34, 9, 'O']
[1000000, 'X', 'N']


[0.5, 0, 'O']
[1.0, 1, 'O']
[0.8300000000000001, 1, 'O']
[1.3599999999999999, 2, 'O']
[1.26, 3, 'O']
[2.47, 9, 'N']
[2.44, 9, 'O']
[2.8200000000000003, 9, 'N']
[2.02, 4, 'O']
[2.5, 9, 'N']
[2.34, 9, 'O']
[2.84, 11, 'N']


[0.5, 0, 'O']
[1.0, 1, 'O']
[0.8300000000000001, 1, 'O']
[1.3599999999999999, 2, 'O']
[1.26, 3, 'O']
[2.47, 9, 'O']
[2.44, 9, 'O']
[2.8200000000000003, 9, 'N']
[2.02, 4, 'O']
[2.5, 9, 'N']
[2.34, 9, 'O']
[2.84, 11, 'N']


[0.5, 0, 'O']
[1.0, 1, 'O']
[0.8300000000000001, 1, 'O']
[1.3599999999999999, 2, 'O']
[1.26, 3, 'O']
[2.47, 9, 'O']
[2.44, 9, 'O']
[2.8200000000000003, 9, 'N']
[2.02, 4, 'O']
[2.5, 9, 'O']
[2.34, 9, 'O']
[2.84, 11, 'N']


[0.5, 0, 'O']
[1.0, 1, 'O']
[0.8300000000000001, 1, 'O']
[1.3599999999999999, 2, 'O']
[1.26, 3, 'O']
[2.47, 9, 'O']
[2.44, 9, 'O']
[2.8200000000000003, 9, 'O']
[2.02, 4, 'O']
[2.5, 9, 'O']
[2.34, 9, 'O']
[2.84, 11, 'N']


[0.5, 0, 'O']
[1.0, 1, 'O']
[0.8300000000000001, 1, 'O']
[1.3599999999999999, 2, 'O']
[1.26, 3, 'O']
[2.47, 9, 'O']
[2.44, 9, 'O']
[2.8200000000000003, 9, 'O']
[2.02, 4, 'O']
[2.5, 9, 'O']
[2.34, 9, 'O']
[2.84, 11, 'O']

plus court chemin, à lire à l’envers : [12, 11, 9, 4, 2, 1, 0] distance totale : 2.84

Merci beaucoup

+0 -0

Je m’y colle, pour relancer un peu le sujet.

1ère façon de voir le problème : il existe des Algorithmes qui font le job. Ache a parlé de A*, de Dijkstra… Vous choisissez un algorithme, et vous le programmez. (ou vous recopiez le code qu’on trouve ici ou là, en adaptant les noms de variables)

2ème façon de voir le problème : Vous réinventez la roue, vous bâtissez un algorithme 'à vous’. Vous avez toutes les chances de retomber sur un des 2 algorithme susnommés… ou d’avoir un algorithme qui ne marche pas.

Ce 2ème scénario me convient tout à fait. C’est ce que j’aurais fait en tant qu’élève. Mais dans ce cas, il faut expliquer l’algorithme. Il faut bien le détailler, très précisément. Et quand on a la certitude que cet algorithme va fonctionner, il faut le traduire dans une autre langue (Python dans votre cas). Commencer à traduire une oeuvre dans une langue étrangère, sans avoir l’intrigue complète, ça ne marche pas

Ici, je peux essayer de retraduire votre code en langue française… mais ce serait plus simple si tu postais directement une version 'en français’ de l’algorithme.

+0 -0

Bonjour,

Visiblement l’algorithme que Théo utilise est l’algorithme de Dijkstra qui permet de trouver le plus court chemin dans un graphe aux poids positifs. Normalement le graphe que tu utilises est le suivant : graph.png

Pour choisir la station de départ et d’arrivée il faut que tu changes ta boucle de reconstruction de chemin pour utiliser ton index de départ et d’arrivé

 ville = end_ville
 chemin = [end_ville]
 while ville != start_ville:
    ville = DIJ[ville][1]
    chemin.append(ville)

De manière générale, je te conseils de créer une fonction qui prend en entrée la ville de départ et la ville d’arrivé et qui te retourne le chemin.

def plus_court_chemin(m_adjac, start_ville, end_ville=Nvilles):
    DIJ = list()  # la liste DIJ mémorise les données du tableau (cf. étape 1)
    for i in range(Nvilles):
        DIJ.append([float("inf"), "X", "N"])  # voir commentaire page suivante

    ville_select = start_ville  # numéro de la ville sélectionnée; 0 = ville de départ
    dist_interm = 0  # distance pour arriver à la ville sélectionnée; 0 au départ

    while ville_select != end_ville:
        DIJ[ville_select][0] = dist_interm
        DIJ[ville_select][2] = "O"
        minimum = float("inf")
        for n in range(0, Nvilles):

            if DIJ[n][2] == "N":
                dist = m_adjac[ville_select][n]
                dist_totale = dist_interm + dist
                print(ville_select, n, dist_totale)
                if dist != 0 and dist_totale < DIJ[n][0]:
                    DIJ[n][0] = dist_totale
                    DIJ[n][1] = ville_select

                if DIJ[n][0] < minimum:
                    minimum = DIJ[n][0]
                    pville_select = n

        ville_select = pville_select  # pville_select = numéro de la prochaine ville sélectionnée
        dist_interm = minimum

    ville = end_ville
    chemin = [end_ville]
    while ville != start_ville:
        ville = DIJ[ville][1]
        chemin.append(ville)

    return chemin

J’ai également remplacé tes valeurs 10000 par float("inf") qui sert de distance initiale dans le graphe

Puis pour calculer ton chemin tu as juste à faire ça : 

chemin = plus_court_chemin(m_adjac, 0, 6)
#pour le remettre dans le bon ordre
chemin = list(reversed(chemin))
+1 -0

Bonjour à tous, Je relance le sujet après avoir tenté de prendre en considération vos messages (merci pour votre aide précieuse déjà) et en essayant de rajouter des choses. Autant vous le dire tout de suite, le programme ne fonctionne pas vraiment (je vous l’ai mis en dessous). La console me demande bien une ville de départ et une ville d’arrivée puis se termine sans "erreur" mais ne m’affiche aucun chemin non plus… De fait, j’ai quelques interrogations:

  • est ce que je n’ai pas besoin de modifier ma matrice d’adjacence?
  • les différentes parties qui m’ont été proposées sont elles au bon endroit?
  • pour quelle(s) raison(s) le programme ne m’affiche t’il rien?

Merci beaucoup, Theo

Ci-dessous mon programme V.2:

Nvilles = 13

#   M E D F C H I G J A K L B

L1 = [0.5,0,0.5,0.33,0,0,0,0,0,0,0,0,0]#E la méthode append (cf. étape 3) est utilisée dans la suite
L2 = [0,0.5,0,0,0.36,0,0,0,0,0,0,0,0]#D
L3 = [0,0.33,0,0,0,0.43,0,0,0,0,0,0,0]#F
L4 = [0,0,0.36,0,0,0,0,0,0,0.66,0,0,0]#C
L5 = [0,0,0,0.43,0,0,0,0,0,0.85,0,0,0]#H
L0 = [0,0.5,0,0,0,0,0,0,0,0,0,0,0]#M
L6 = [0,0,0,0,0,0,0,0,0.42,0.45,0,0,0]#I
L7 = [0,0,0,0,0,0,0,0,0,0.42,0,0,0]#G
L8 = [0,0,0,0,0,0,0.42,0,0,0.8,0,0,0]#J
L9 = [0,0,0,0,0.66,0.85,0.45,0.42,0.8,0,0.48,0.32,0]#A
L10 = [0,0,0,0,0,0,0,0,0,0.48,0,0,0.39]#K
L11 = [0,0,0,0,0,0,0,0,0,0.32,0,0,0.5]#L
L12 = [0,0,0,0,0,0,0,0,0,0,0.39,0.5,0]#B

m_adjac = [L0,L1,L2,L3,L4,L5,L6,L7,L8,L9,L10,L11,L12]

start_ville = input("ville de départ ? [version liste]: ")
end_ville = input("ville d'arrivée ? [version liste] : ")

def plus_court_chemin(m_adjac, start_ville, end_ville = Nvilles):

  DIJ = list()  # la liste DIJ mémorise les données du tableau (cf. étape 1)
  for i in range(Nvilles):
     DIJ.append([float("inf"), "X", "N"])  # voir commentaire page suivante

  ville_select = start_ville  #numéro de la ville sélectionnée; 0 = ville de départ
  dist_interm = 0  #distance pour arriver à la ville sélectionnée; 0 au départ

  while ville_select != end_ville:
      DIJ[ville_select][0] = dist_interm
      DIJ[ville_select][2] = "O"
      minimum = float("inf")
      for n in range(0, Nvilles):

          if DIJ[n][2] == "N":
              dist = m_adjac[ville_select][n]
              dist_totale = dist_interm + dist
              print(ville_select, n, dist_totale)
              if dist != 0 and dist_totale < DIJ[n][0]:
                  DIJ[n][0] = dist_totale
                  DIJ[n][1] = ville_select

              if DIJ[n][0] < minimum:
                  minimum = DIJ[n][0]
                  pville_select = n

      ville_select = pville_select  # pville_select = numéro de la prochaine ville sélectionnée
      dist_interm = minimum

  ville = end_ville
  chemin = [end_ville]
  while ville != start_ville:
      ville = DIJ[ville][1]
      chemin.append(ville)

  print(chemin)
+0 -0

Bonjour,

Pour répondre à tes questions :

  • Tu n’as pas besoin de modifier ta matrice d’adjacence car l’algorithme te retourne le plus court chemin entre n’importe quels nœuds de ton graphe. En revanche, c’est surement plus simple de retenir que l’index 0 correspond à la station A que la station E donc je te conseilles de la remettre dans l’ordre alphabétique.
  • Les parties semblent être au bons endroits, en revanche dans la fonction tu as oublié le return chemin.
  • Tu n’as rien qui s’affiche car tu définis la fonction mais tu ne l’appelle pas donc le code à l’intérieur de la fonction ne s’exécute jamais

Ton erreur vient d’une mauvaise compréhension des fonctions, est ce que vous les avez vus en cours ? Dans tous les cas voici un petit rappel :

def carré(x) :
   valeur = x * x
   print(valeur)

# n'affiche rien, car on a juste expliqué à l'ordinateur comment on calcule le carré d'un nombre
# mais on ne lui à pas dit ce que vaut x.

carré(5) # => affiche 5
#quand on appelle carré(5) l'ordinateur va dans le code définit dans fonction et remplace x par 
# 5, ce qui lui permet de te donner le résultat

#Mais fait attention car print sert juste à afficher quelque chose à l'écran, donc tu ne peux pas
# récupérer le résultat de ta fonction.

a = carré(2) + 2 # provoque une erreur car carré ne retourne rien 

#Donc si tu veux utiliser le résultat de ta fonction pour autre chose il faut que tu la remplace par 
def carré(x):
   valeur = x * x
   return valeur 

a = carré(2) + 2 # a = 6
print(a) # affiche 6 sur l'écran
print(carré(2)) # affiche 4 sur l'écran

#donc il faut juste que tu mette en bas de ton code
plus_court_chemin(start_ville, end_ville) #si tu veux juste que le chemin s'affiche sur l'écran
#si tu veux utiliser ce chemin pour autre chose, il faut que tu rajoute un return chemin à la fin de la fonction plus_court_chemin.
+0 -0

Merci Kabegami, j’avais oublié le plus simple… J’ai aussi remis ma matrice d’adjacence dans l’ordre alphabétique en changeant aussi le nom des listes (qui ne devrait avoir a priori aucun impact). Toujours est-il que quelque chose cloche parce que la console me retourne une erreur dont j’ai du mal à saisir l’origine. Voilà mon nouveau code, avec ce que la console me renvoie après l’avoir fait fonctionné :

Nvilles = 13

#   A B C D E F G H I J K L
A = [0,0,0,0,0.66,0.85,0.45,0.42,0.8,0,0.48,0.32,0]#A
B = [0,0,0,0,0,0,0,0,0,0,0.39,0.5,0]#B
C = [0,0,0.36,0,0,0,0,0,0,0.66,0,0,0]#C
D = [0,0.5,0,0,0.36,0,0,0,0,0,0,0,0]#D
E = [0.5,0,0.5,0.33,0,0,0,0,0,0,0,0,0]#E 
F = [0,0.33,0,0,0,0.43,0,0,0,0,0,0,0]#F
G = [0,0,0,0,0,0,0,0,0,0.42,0,0,0]#G
H = [0,0,0,0.43,0,0,0,0,0,0.85,0,0,0]#H
I = [0,0,0,0,0,0,0,0,0.42,0.45,0,0,0]#I
J = [0,0,0,0,0,0,0.42,0,0,0.8,0,0,0]#J
K = [0,0,0,0,0,0,0,0,0,0.48,0,0,0.39]#K
L = [0,0,0,0,0,0,0,0,0,0.32,0,0,0.5]#L

m_adjac = [A,B,C,D,E,F,G,H,I,K,L]

start_ville = input("ville de départ ? [version liste]: ")
end_ville = input("ville d'arrivée ? [version liste] : ")

def plus_court_chemin(m_adjac, start_ville, end_ville = Nvilles):

  DIJ = list()  # la liste DIJ mémorise les données du tableau (cf. étape 1)
  for i in range(Nvilles):
     DIJ.append([float("inf"), "X", "N"])  # voir commentaire page suivante

  ville_select = start_ville  #numéro de la ville sélectionnée; 0 = ville de départ
  dist_interm = 0  #distance pour arriver à la ville sélectionnée; 0 au départ

  while ville_select != end_ville:
      DIJ[ville_select][0] = dist_interm
      DIJ[ville_select][2] = "O"
      minimum = float("inf")
      for n in range(0, Nvilles):

          if DIJ[n][2] == "N":
              dist = m_adjac[ville_select][n]
              dist_totale = dist_interm + dist
              print(ville_select, n, dist_totale)
              if dist != 0 and dist_totale < DIJ[n][0]:
                  DIJ[n][0] = dist_totale
                  DIJ[n][1] = ville_select

              if DIJ[n][0] < minimum:
                  minimum = DIJ[n][0]
                  pville_select = n

      ville_select = pville_select  # pville_select = numéro de la prochaine ville sélectionnée
      dist_interm = minimum

  ville = end_ville
  chemin = [end_ville]
  while ville != start_ville:
      ville = DIJ[ville][1]
      chemin.append(ville)
  return(chemin)
  print(chemin)

plus_court_chemin(m_adjac,start_ville,end_ville)

La console renvoit, lorsque je saisis au hasard deux points:

ville de départ ? [version liste]: B
ville d'arrivée ? [version liste] : I
Traceback (most recent call last):
  File "main.py", line 60, in <module>
    plus_court_chemin(m_adjac,start_ville,end_ville)
  File "main.py", line 32, in plus_court_chemin
    DIJ[ville_select][0] = dist_interm
TypeError: list indices must be integers or slices, not str

Merci d’avance, Theo

+0 -0

Le problème est que "B" correspond à 1 et "I" correspond à 8. Mais qu’il faut le dire quelque part dans le code.

Car tu ne peux pas faire DIJ["B"]. Tu dois faire DIJ[1].

Pour ça, rien de trop difficile.

start_ville = ord(input("ville de départ ? [version liste]: "))-ord("A")
end_ville = ord(input("ville d'arrivée ? [version liste] : "))-ord("A")

La fonction ord convertie un caractère (comme A) en sa représentation entière. Tous les caractères pour l’ordinateur ne sont que des nombres. Dans pratiquement toutes les représentations, les lettres suivent l’ordre alphabétique. C’est à dire que si A est représenté par 2222, alors B sera 2323. Donc tu vois que si tu retires ord("A") à un ord("I") tu obtiens 8 comme voulu.

C’est une méthode un peu naïve. Voir la réponse suivante pour une meilleur gestion de l’input. Reste que tu devrais pouvoir faire plus propre en créant une fonction pour cela.

PS: J’ai un doute sur la partie end_ville = Nvilles): de ton code. Nvilles correspond au nombre de ville. Il ne désigne pas un ville. Pour être la dernière ville, j’aurais plutôt fait : end_ville = Nvilles-1):. D’ailleurs, j’aurais également assigné start_ville à 0.

+1 -0

Pour ça, rien de trop difficile.

start_ville = ord(input("ville de départ ? [version liste]: "))-ord("A")
end_ville = ord(input("ville d'arrivée ? [version liste] : "))-ord("A")

La fonction ord convertie un caractère (comme A) en sa représentation entière. Tous les caractères pour l’ordinateur ne sont que des nombres. Dans pratiquement toutes les représentations, les lettres suivent l’ordre alphabétique. C’est à dire que si A est représenté par 2222, alors B sera 2323. Donc tu vois que si tu retires ord("A") à un ord("I") tu obtiens 8 comme voulu.

ache

Ça ne semble quand même pas très intuitif comme solution de se baser sur des codes plus ou moins arbitraires pour chacun des caractères et du fait que les lettres minuscules soient correctement ordonnées.

Une meilleure solution serait de se baser sur la méthode index des chaînes de caractères qui permet d’associer une position à un caractère recherché dans la chaîne, ça évite quelques opérations bizarres. Tu as de plus le module string qui fournit une chaîne ascii_uppercase, idéale pour ce genre d’utilisation :

>>> import string
>>> string.ascii_uppercase.index('B')
1
>>> string.ascii_uppercase.index('I')
8

Et si jamais tu trouves trop coûteuse la recherche dans une chaîne, il est toujours possible de construire une table d’association :

>>> {c: i for i, c in enumerate(string.ascii_uppercase)}
{'A': 0, 'B': 1, 'C': 2, 'D': 3, 'E': 4, 'F': 5, 'G': 6, 'H': 7, 'I': 8, 'J': 9, 'K': 10, 'L': 11, 'M': 12, 'N': 13, 'O': 14, 'P': 15, 'Q': 16, 'R': 17, 'S': 18, 'T': 19, 'U': 20, 'V': 21, 'W': 22, 'X': 23, 'Y': 24, 'Z': 25}
+2 -0

Ça ne semble quand même pas très intuitif comme solution de se baser sur des codes plus ou moins arbitraires pour chacun des caractères et du fait que les lettres minuscules majuscules soient correctement ordonnées.

Plus ou moins arbitraire… Bon UTF8 quoi. Mais je comprend ce que tu veux dire.
Ça évite juste d’avoir une chaîne de caractère "ABCDEFGHIJKLMNOPQRSTUVWXYZ" dans son code. Après, si elle existe déjà dans le module string pourquoi pas.

L’avantage d’utiliser index est que justement, on peut se baser sur autre chose que "ABCD..". Par exemple "0123456789ABCD...abcd..". Ça peut être important si le nombre de villes à gérer augmente.

+0 -0

Le projet repose sur une petite partie du métro parisien (on compte à peine une quarantaine de stations). Donc utiliser une lettre pour chaque liste de la matrice semble compromis (à moins que l’on utilise aussi les minuscules?). Notre professeur nous avait conseillé de créer une bibliothèque dans laquelle chaque station porte un code auquel on associe un nombre (exemple avec la station République : c’est la 18ème station de la ligne 3 donc son "code" serait 3–18 qui vaudrait 23 par exemple). Je ne sais pas trop comment gérer les correspondances du coup. Toutefois je me demande si le code ASCII ne serait pas plus simple dans ce cas… Qu’en pensez-vous? La solution qui utilise index me paraît aussi à privilégier.

+0 -0

Je te conseillerais de te baser sur un truc déjà en place. Comme le code des stations de métro;

Après, tout dépends ce que tu veux entrer dans ton application. Le code alphabétique me semble bien plus simple et utile à entrer mais toutes les stations n’en ont pas.

+0 -0

Le code alphabétique me semble bien plus simple et utile à entrer mais toutes les stations n’en ont pas.

ache

C’est-à-dire? Utiliser le code des stations de métro me semble une bonne idée mais je dois tout de même les associer à des chiffres allant de 0 à n-1 stations du coup?

+0 -0

Yep, si tu décides de rester sur la même matrice d’adjacence.

Mais tu pourrais très bien imaginer une matrice d’adjacence à base de dictionnaire n’utilisant que des codes des stations.

+0 -0

J’ai modifié mon programme de ce que j’ai compris de vos conseils. Je rencontre pourtant le même problème donc j’imagine que l’erreur doit provenir du dictionnaire mais je ne comprends pas trop où. J’ai changé le nom des stations (A,B,C,D…) par le code d’oblitération de la RATP dans ma matrice d’adjacence mais il considère celui ci comme des nombres (error literals) malgré des guillemets (’0408’). J’ai donc ajouté un S pour "station". Par rapport à la remarque de asche sur Nvilles-1 je suis d’accord avec toi donc j’ai apporté la modification. En revanche, si je pose start_ville=0 j’ai peur que ma ville de départ devienne systématiquement Montparnasse-Bienvenüe. 

Nvilles = 13

#   A B C D E F G H I J K L M
S0408 = [0,0,0,0,0.66,0.85,0.45,0.42,0.8,0,0.48,0.32,0] #Monparnasse Bienvenue
S1510 = [0,0,0,0,0,0,0,0,0,0,0.39,0.5,0] #Raspail
S0207 = [0,0,0.36,0,0,0,0,0,0,0.66,0,0,0] #Duroc
S0208 = [0,0.5,0,0,0.36,0,0,0,0,0,0,0,0] #Vaneau
S0209 = [0.5,0,0.5,0.33,0,0,0,0,0,0,0,0,0] #Sèvres Babylone
S0211 = [0,0.33,0,0,0,0.43,0,0,0,0,0,0,0] #Rennes
S0412 = [0,0,0,0,0,0,0,0,0,0.42,0,0,0] #Saint Placide
S0414 = [0,0,0,0.43,0,0,0,0,0,0.85,0,0,0] #Notre Dame des Champs
S1601 = [0,0,0,0,0,0,0,0,0.42,0.45,0,0,0] #Falguière
S1602 = [0,0,0,0,0,0,0.42,0,0,0.8,0,0,0] #Pasteur
S0407 = [0,0,0,0,0,0,0,0,0,0.48,0,0,0.39] #Vavin
S0406 = [0,0,0,0,0,0,0,0,0,0.32,0,0,0.5] #Edgar Quinet
S0210 = [0,0.5,0,0,0,0,0,0,0,0,0,0,0] #Rue du Bac

m_adjac = [S0408,S1510,S0207,S0208,S0209,S0211,S0412,S0414,S1601,S1602,S0407,S0406,S0210]

conversion = {'S0408':0,'S1510':1,'S0207':2,'S0208':3,'S0209':4,'S0211':5,'S0412':6,'S0414':7,'S1601':8,'S1602':9,'S0407':10,'S0406':11,'S0210':13}

start_ville = input("ville de départ ? [oblitération]: ")
end_ville = input("ville d'arrivée ? [oblitération] : ")

m_adjac = [conversion.values()]

def plus_court_chemin(m_adjac,start_ville,end_ville = Nvilles-1):

  DIJ = list()  # la liste DIJ mémorise les données du tableau (cf. étape 1)
  for i in range(Nvilles):
     DIJ.append([float("inf"), "X", "N"])  # voir commentaire page suivante

  ville_select = start_ville  #numéro de la ville sélectionnée; 0 = ville de départ
  dist_interm = 0  #distance pour arriver à la ville sélectionnée; 0 au départ

  while ville_select != end_ville:
      DIJ[ville_select][0] = dist_interm
      DIJ[ville_select][2] = "O"
      minimum = float("inf")
      for n in range(0, Nvilles):

          if DIJ[n][2] == "N":
              dist = m_adjac[ville_select][n]
              dist_totale = dist_interm + dist
              print(ville_select, n, dist_totale)
              if dist != 0 and dist_totale < DIJ[n][0]:
                  DIJ[n][0] = dist_totale
                  DIJ[n][1] = ville_select

              if DIJ[n][0] < minimum:
                  minimum = DIJ[n][0]
                  pville_select = n

      ville_select = pville_select  # pville_select = numéro de la prochaine ville sélectionnée
      dist_interm = minimum

  ville = end_ville
  chemin = [end_ville]
  while ville != start_ville:
      ville = DIJ[ville][1]
      chemin.append(ville)
  return(chemin)
  print(chemin)

plus_court_chemin(m_adjac,start_ville,end_ville)
+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte