un soucis sur la récursivité

Version imprimable

Bonjour à tous !!

Je me permets de passer vous voir car je fais face à un un problème technique qui touche à la récursivité.
Je tente de développer une fonction dont l'objectif serait de parcourir un graphe, en partant d'un point initial et récupérant tous les chemins possible à effectuer avec une distance maximum. Je pars donc de A, sans point d'arrivée précis, mais je n'ai le droit de parcourir que 300 par exemple, et je récupère dans l'idéal la liste des chemins possibles à faire depuis A.
Pour cela je dispose d'un dictionnaire contenant tous les noeuds. Chaque noeud a pour clef sont identifiant et comme valeur un autre dictionnaire contenant les noeuds auxquels il est connecté et la valeur à parcourir pour les rejoindre

EX :
2654 :{2655:170, 2987:22, 3500:98}
Le noeud 2654 est relié aux noeuds 2655,2987,3500 et dois parcourir respectivement 170,22,98 pour les atteindre.

j'étais parti sur un test de ce genre :
Code:

1 2 3 4 5 6 7 8 9 10 def parcours(dico,debut,dist,way,maxi,all_way): for key,value in begining.items(): if key not in way : way.append(key) dist+=value if dist<maxi : parcours(dico,dico[key],dist,way,maxi,all_way) else : all_way.append(way) print(dist)
Bon j'obtiens des truc bizarres, notamment le print qui me retourne des valeurs beaucoup plus élevées que le maximum prévu initialement :?
Si quelqu'un a une bonne idée je suis preneur, au besoin je pourrai vous joindre le fameux dictionnaire si vous voulez faire des tests avec.

Merci d'avance à tout le monde :lol:

PS: si jamais le post arrive au mauvais endroit, mes excuses, faites moi signe et je le déplace

26/07/2015, 20h34
josmiley

il faut donc récupérer tous les chemins possibles(les plus longs) depuis A en tenant compte d'une distance maximum, c'est ça ?
26/07/2015, 21h12
jeremy.GELB

Exactement :D
est-ce que vous voyez ce qui ne va pas ?

perso j'aime pas les récursives, théoriquement on peut lever un max recursion ...
j'ai supposé que les noeuds finaux n'étaient pas présent dans le dico.

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
mon_dict = {2654 :{2655:170, 2987:22, 3500:98},
            2655:{5214:14, 6324:10, 2221:25},
            2987:{1214:20, 2014:35, 4400:17},
            3500:{5552:23, 2000:60}}
 
 
def foo(D,initial,dist_max):
    scan = [((initial,),0)]
    result = []
    while scan:
        noeuds,dist = scan.pop(0)
        items = D.get(noeuds[-1],{}).items()
        if not items:
            result.append((noeuds,dist))
        else:
            for noeud_next,dist_next in items:
                if dist + dist_next > dist_max:
                    result.append((noeuds,dist))
                else:
                    scan.append((noeuds+(noeud_next,),dist + dist_next))
    return set(result)
 
 
for chaine,distance in foo(mon_dict,2654,300):
    print(chaine,distance)

Code:

1
2
3
4
5
6
7
8
(2654, 3500, 2000) 158
(2654, 2655, 2221) 195
(2654, 2987, 2014) 57
(2654, 2655, 5214) 184
(2654, 2655, 6324) 180
(2654, 2987, 4400) 39
(2654, 2987, 1214) 42
(2654, 3500, 5552) 121

02/08/2015, 15h41
PetitChameau

Bonjour,
Je n'ai pas de quoi tester mais, à première vue, il y a déjà un soucis dans ta condition d'arrêt : tu ajoutes la nouvelle clé au chemin avant de savoir si tu peux l'atteindre !
En effet, si ton max est 300, que tu as déjà cumulé 280 en distance et que ta nouvelle clé est à 200... Tu vas certes arrêter ta récursion mais ta distance aura largement dépassé le max autorisé !