Code qui plante, calcul de chemins

Version imprimable

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:

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)

04/11/2018, 19h09
fred1599

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

message d'erreur

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

04/11/2018, 19h33
fred1599

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.
04/11/2018, 20h16
thierry1967

je ne comprends pas

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
04/11/2018, 20h54
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.
04/11/2018, 21h00
Sve@r

Bonjour

Citation:

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...

cela ne fonctionne pas

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

>>>

04/11/2018, 23h14
Sve@r
Citation:

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.
Citation:
Envoyé par thierry1967

Code:

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.
05/11/2018, 08h49
fred1599

Citation:

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...
05/11/2018, 10h08
thierry1967

compris ?

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
05/11/2018, 10h33
fred1599
Citation:

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:

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.

Citation:

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,
05/11/2018, 10h36
wiztricks

Citation:

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
05/11/2018, 12h11
Sve@r
Citation:
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

Citation:

Envoyé par thierry1967

Code:

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.
05/11/2018, 17h54
thierry1967

Trop bête

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