if ..
return A
else
return B
if ..
res = A
else ..
res = B
return res
if ..
return A
return B
if ..in track
return ..
nopickup = rectoprown(i, lastvisited)
rec_pickup = rectoprown(i, c(i))
if c(i)==lastvisited
pickup = rec_pickup + self.A*T(i)
else
pickup = rec_pickup + self.B*T(i)
maxi = max(nopickup, pickup)
track[(..)] = maxi
return maxi
track = {(2000000, 2000000): 2000000}
total = self.topdown.rectopdown(t, c, a, b, track)
def rectopdown(self, t, c, a, b, track, i=0, lastvisited=-170):
if i == len(c):
return 0
if (i, lastvisited) in track:
return track.get((i, lastvisited), "fail")
if c[i] == lastvisited:
maxi = max(self.rectopdown(t, c, a, b, track, i + 1, lastvisited), a * t[i] + self.rectopdown(t, c, a, b, track, i + 1, lastvisited))
else:
maxi = max(self.rectopdown(t, c, a, b, track, i + 1, lastvisited), b * t[i] + self.rectopdown(t, c, a, b, track, i + 1, lastvisited))
track[i, lastvisited] = maxi
return maxi
if c[i] == lastvisited:
maxi = max(self.rectopdown(t, c, a, b, track, i + 1, lastvisited), a * t[i] + self.rectopdown(t, c, a, b, track, i + 1, lastvisited))
print(maxi)
else:
maxi = max(self.rectopdown(t, c, a, b, track, i + 1, lastvisited), b * t[i] + self.rectopdown(t, c, a, b, track, i + 1, lastvisited))
print(maxi)
En ce qui concerne la complexité de ce nouvel algo', il est simplifié en terme de temps, mais je garde toujours la complexité logarithmique à cause des 2 appels récursifs dans le max(...) non ?
00
01
s2
000
001
010 <---
011 <---s2, mais on connait pas encore donc il faut explorer avant de cacher
100 <<il s'agit d'un nouveau symbole donc obliger de calculer les sommes
101
110 <---
111 <---s2, donc une seule explo (utilisation du cache)
0
0
0 P(2)
P(3) = 0
100
101
110
111
1 -> s2
-> 0 -> 0
-> 1
0
..
0 P(3)
P(4) = 0
10
10...P(2)
10
100
101
110
111
1 -> s3
-> 0 -> s2
-> 0 -> 0
-> 1
T(n)= Θ(n^(log_1 (2)))
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 5 invités
Tu pars déja ?
Identification
Pas encore inscrit ?
Ou identifiez-vous :