Code qui plante, calcul de chemins

**thierry1967** · 04/11/2018, 19h01

Bonjour et merci par avance à celles et ceux qui m'aideront
je souhaite calculer tous les chemins possibles entre deux stations dans le cadre d'un projet.
mon code python plante pour une ou plusieurs raisons que je ne comprends pas.
je vous soumets le code pour critique. Merci pour vos explications.
je suis parti sur une recherche type taboo.

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
# matrice adjacentre = determine les liens entre les stations
relation=[
[0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0],[1,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0],[0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0],
[0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0],
[0,0,0,1,1,0,0,1,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0],
[0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0],
[0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,0],
[0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,1],
[0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0]]
 
# print(relation[0][3])
 
# taille du réseau
taille=len(relation)
taille=int(taille)
 
print("Le réseau comporte",taille,"stations")
 
# saisie du sommet de départ
depart=input("Saisie du sommet de départ:")
depart=int(depart)
 
#saisie du sommet d'arrivée
arrivee=input("Saisie du sommet d'arriveé:")
arrivee=int(arrivee)
 
# mémorisation du parcours
parcours=[taille]
 
# initialisation des sommets à 0 car aucun sommet n'a été exploré
exploration=["non"]*taille
 
def explorer(position,profondeur):
    # sauvegarde du chemin
    parcours[profondeur]=position
 
    # si la position correspond au sommet d'arrivée
    if position==arrivee:
        for i in range(0,taille):
            print(parcours[i],end="")
 
    # sinon la position ne correspond pas au sommet d'arrivee donc on marque le sommet comme exploré
    exploration[position]="oui"
 
    # on explore les autres chemins
    for i in range(0,taille):
        if(relation[position][i]==0 or exploration[i]=="non"):
            explorer(i,profondeur+1)
 
    # on marque la position comme non visitée
    exploration[position]="non"
 
# lancement de l'exploration avec le départ et profondeur de 0
explorer(depart,0)

**fred1599** · 04/11/2018, 19h09

Est-ce que l'exécution du code indique une erreur ou est-ce lié à des difficultés algorithmiques ?

**thierry1967** · 04/11/2018, 19h28

voici le message d'erreur qui s'affiche :

>>> (executing file "parcours-taboo.py")
Le réseau comporte 16 stations
Saisie du sommet de départ:1
Saisie du sommet d'arriveé:10
Traceback (most recent call last):
  File "F:\TIPE-julien\parcours-taboo.py", line 59, in <module>
    explorer(depart,0)
  File "F:\TIPE-julien\parcours-taboo.py", line 53, in explorer
    explorer(i,profondeur+1)
  File "F:\TIPE-julien\parcours-taboo.py", line 40, in explorer
    parcours[profondeur]=position
IndexError: list assignment index out of range

**fred1599** · 04/11/2018, 19h33

Si la variable profondeur prend une valeur supérieure à la longueur-1 (car l'index commence à 0) de la liste parcours, tu auras cette erreur.

**thierry1967** · 04/11/2018, 20h16

Merci pour cette info mais je ne comprends pas. il n'y a à aucun moment un pb avec la profondeur. elle débute à 0 et est ensuite incrémentée de +1
merci pour le retour

**fred1599** · 04/11/2018, 20h54

Oui sauf erreur de ma part, la taille de parcours semble être de 1, ce qui implique comme seule solution d'index, la valeur 0.

**Sve@r** · 04/11/2018, 21h00

Bonjour

Envoyé par thierry1967

elle débute à 0 et est ensuite incrémentée de +1

Incrémente ta profondeur de +1 un assez grand nombre de fois et elle dépassera fatalement à un moment donné la taille de ton tableau "position".
Tu devrais afficher sa valeur en ligne 39

Accessoirement tu as True et False plus adaptées que "oui" et "non" pour flaguer un truc...

**thierry1967** · 04/11/2018, 21h08

j'ai intégré l'affichage de position mais toujours une erreur

>>> (executing file "parcours-taboo.py")
Le réseau comporte 16 stations
Saisie du sommet de départ:1
Saisie du sommet d'arriveé:10
1
Traceback (most recent call last):
  File "F:\TIPE-julien\parcours-taboo.py", line 60, in <module>
    explorer(depart,0)
  File "F:\TIPE-julien\parcours-taboo.py", line 54, in explorer
    explorer(i,profondeur+1)
  File "F:\TIPE-julien\parcours-taboo.py", line 40, in explorer
    parcours[profondeur]=position
IndexError: list assignment index out of range

>>>

**Sve@r** · 04/11/2018, 23h14

Envoyé par thierry1967

j'ai intégré l'affichage de position mais toujours une erreur
1

Ca veut dire que "parcours" est soit un tableau d'un seul élément ; soit pas un tableau du tout.

Envoyé par thierry1967

Code python :

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

1
2
# mémorisation du parcours
parcours=[taille]

Ben oui, "parcours" est bien une liste n'ayant qu'un seul élément (indicé [0]) donc demander parcours[1] produit un IndexError.

**fred1599** · 05/11/2018, 08h49

Envoyé par fred1599

Oui sauf erreur de ma part, la taille de parcours semble être de 1, ce qui implique comme seule solution d'index, la valeur 0.

Je me permets de citer à nouveau mes dires...

**thierry1967** · 05/11/2018, 10h08

avec parcours[taille] je souhaitais créer une liste contenant autant d’éléments que la taille du réseau.
ensuite au fur et à mesure du déroulement du programme, mémoriser le chemin des sommets parcourus via parcours[0], parcours[1], parcours[2] ... jusqu'à l'arrivée puis afficher le chemin (tous les parcours[]) lorsque l'arrivée est atteinte.
Démarche fausse ?
merci pour votre aide et désolé de en pas comprendre toutes les finesses de python

**fred1599** · 05/11/2018, 10h33

avec parcours[taille] je souhaitais créer une liste contenant autant d’éléments que la taille du réseau.

Ce n'est pas comme cela qu'on crée une liste de taille précise...

Code :

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

parcours = [0 for i in range(n)]

où n est la taille de la liste, 0 représentant l'élément que tu souhaites insérés n fois.
Tu peux remplacer n et 0 à ta convenance et selon tes besoins.

désolé de en pas comprendre toutes les finesses de python

Ce n'est pas une finesse mais une base. Es-tu cherché comment créer une liste de n éléments ?

Quelques solutions,

**wiztricks** · 05/11/2018, 10h36

Envoyé par thierry1967

avec parcours[taille] je souhaitais créer une liste contenant autant d’éléments que la taille du réseau.

Soit vous créez une liste assez grande comme vous le faites ligne suivante avec exploration=["non"]*taille, soit vous créez une liste vide à laquelle vous ajoutez les éléments visités via .append.

- W

**Sve@r** · 05/11/2018, 12h11

Envoyé par thierry1967

je souhaitais créer une liste contenant autant d’éléments que la taille du réseau... désolé de en pas comprendre toutes les finesses de python

Envoyé par thierry1967

Code :

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

1
2
3
4
5
6
 
# mémorisation du parcours
parcours=[taille]
 
# initialisation des sommets à 0 car aucun sommet n'a été exploré
exploration=["non"]*taille

Ce n'est pas une question de "compréhension des finesses Python" mais d'analogie et de déduction. Si tu as créé un tableau nommé "exploration" contenant n items avec une certaine syntaxe ; et que tu désires créer un tableau nommé "parcours" contenant lui aussi n (ou m) items, il est évident que la syntaxe de création sera analogue.

**thierry1967** · 05/11/2018, 17h54

... je vais m'améliorer ... merci à vous tous. J'essaie ce soir et regarde si tout cela fonctionne.

Code qui plante, calcul de chemins

Python

Discussions similaires

Partager

Partager