Initiation à la programmation ENSAE 1A

seance10_pdyn_cor.tex

récupération de la liste des villes (sans doublons)

vil = { }
for row in df.values :
    vil [row[0]] = 0
    vil [row[1]] = 1
vil = list(vil.keys())
print (len(vil))

construction d'un dictionnaire { (a,b):d, (b,a):d }

dist = { }
for row in df.values :
    a = row[0]
    b = row[1]
    dist[a,b] = dist[b,a] = row[2]
print (len(dist))

distance Charleville-Mezieres --> Bordeaux

print ( dist["Charleville-Mezieres","Bordeaux"] )

initialisation du tableau d

d = { }
d['Charleville-Mezieres'] = 0
for v in vil : d[v] = 1e10
for v,w in dist :
    if v == 'Charleville-Mezieres': 
        d[w] = dist[v,w]

une itération de l'algorithme de Dikjstra

for v,w in dist :
    d2 = d[v] + dist[v,w]
    if d2 < d[w] :
        d[w] = d2

l'algorithme de Dikjstra

for i in range(0,len(d)) :        
    for v,w in dist :
        d2 = d[v] + dist[v,w]
        if d2 < d[w] :
            d[w] = d2

coût de la meilleure distribution des skis

p = { }
p [-1,-1] = 0
for n,taille in enumerate(skieurs) : p[n,-1] = p[n-1,-1] + taille
for m,paire  in enumerate(paires ) : p[-1,m] = 0
for n,taille in enumerate(skieurs) :
    for m,paire in enumerate(paires) :
        p1 = p.get ( (n  ,m-1), 1e10 ) 
        p2 = p.get ( (n-1,m-1), 1e10 ) + abs(taille - paire)
        p[n,m] = min(p1,p2)
        
print (p[len(skieurs)-1,len(paires)-1])

récupération de la meilleure distribution

p = { }
p [-1,-1] = 0
best = { }
for n,taille in enumerate(skieurs) : p[n,-1] = p[n-1,-1] + taille
for m,paire  in enumerate(paires ) : p[-1,m] = 0
for n,taille in enumerate(skieurs) :
    for m,paire in enumerate(paires) :
        p1 = p.get ( (n  ,m-1), 1e10 ) 
        p2 = p.get ( (n-1,m-1), 1e10 ) + abs(taille - paire)
        p[n,m] = min(p1,p2)
        
        if p[n,m] == p1 : best [n,m] = n,m-1
        else : best [n,m] = n-1,m-1
        
print (p[len(skieurs)-1,len(paires)-1])

chemin = [ ]
pos = len(skieurs)-1,len(paires)-1
while pos in best :
    print (pos)
    chemin.append(pos)
    pos = best[pos]
chemin.reverse()
print (chemin)