Discussion :

[thierry1967]

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]

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

[thierry1967]

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]

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]

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]

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]

Bonjour

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