2 pièce(s) jointe(s)
Plus grand chemin dans un graphe
slt à tous,:coucou:
je bloque depuis plusieurs jours sur un exercice. Mon algorithme marche mais met trop de temps:(
je dispose d'un labyrinthe sous la forme d'un graphe pondéré orienté et je dois trouver, à partir d'un sommet déterminé, le chemin le plus bénéfique(maximum de points récoltés) en visitant un nombre déterminé de chemin... un exemple :
Pièce jointe 217875
je dois partir au sommet n°1 et amasser les points en traversant 4 chemins (je peux aussi attendre à un sommet et récolté 0 points si c plus avantageux). La solution ici serait 15 avec le chemin 1-2 2-3 3-1 1-2
voilà ce que l'on me donne en entrée :
Code:
1
2
3
4
5
6
7
8
9
10
|
4 8 1 4
1 2 5
1 3 3
2 1 -2
2 3 6
2 4 3
3 1 -1
3 4 -2
4 3 1 |
les 4 premiers nombres sont respectivement :
nbSommets : nombre de sommets
nbArcs : nombre d'arcs
debut : sommet de départ
temps : temps à disposition
les nbArcs lignes suivantes (sous la forme s1 s2 l) décrivent le graphe (s1 relie s2 avec un poid l)
et voici mes algos (en python):
une version récursive :
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
|
import sys
def main():
nbSommets,nbArcs,debut,temps = map(int,sys.stdin.readline().split())
INFINI = 10**8
#INFINI = 100 #<-- à supprimer
voisin = [ [(i,0)] for i in range(nbSommets+1)]
for _ in range(nbArcs):
s1,s2,poid = map(int,sys.stdin.readline().split())
voisin[s1].append( (s2,poid) )
tabDynamique = [ [INFINI for i in range(temps)] for j in range(nbSommets+1)]
def MeilleurChemin(T,s):
if T ==0:
return 0
if tabDynamique[s][T-1] != INFINI:
return tabDynamique[s][T-1]
maxPoint = 0
for v,bonus in voisin[s]:
maxPoint = max(maxPoint,bonus + MeilleurChemin(T-1,v) )
tabDynamique[s][T-1] = maxPoint
return maxPoint
print(MeilleurChemin(temps,debut))
main() |
une version itérative :
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
|
import sys
def main():
nbSommets,nbArcs,debut,temps = map(int,sys.stdin.readline().split())
INFINI = 10**8
#INFINI = 100 #<-- à supprimer
voisin = [ [(i,0)] for i in range(nbSommets+1)]
visites = [False] * (nbSommets+1)
visites[debut] = True
scoresMax = [ [-INFINI for _ in range(temps+1)] for i in range(nbSommets+1)]
scoresMax[debut][0] = 0
scoreMax = -INFINI
for _ in range(nbArcs):
s1,s2,poid = map(int,sys.stdin.readline().split())
voisin[s1].append( (s2,poid) )
en_cours = [debut]
for t in range(1,temps+1):
for i in range(len(en_cours)):
s = en_cours[i]
for v,p in voisin[s]:
#print(v,p)
scoresMax[v][t] = max(scoresMax[v][t],scoresMax[s][t-1] + p)
scoreMax = max(scoreMax,scoresMax[v][t])
if not visites[v]:
visites[v] = True
en_cours.append(v)
sys.stdout.write(str(scoreMax))
main() |
mon problème est donc qu'ils prennent trop de temps et je poste pr savoir si qqn n'aurait pas une idée pr améliorer... Merci d'avance;)
