TP
Algorithmes Gloutons

Activité préparatoire

Lors de l'électrification des campagnes françaises après 1920. Les ingénieurs étaient confrontés à un problème d'optimisation.

Comment relier aux réseaux les 200 maisons d'un village en utilisant le mois de cables et de poteaux possible.

On peut imaginer de séparer le problème en problème plus petit, plus facile à résoudre, on crée des quartier alimentés depuis la mairie, puis des rues ...

Pour commencer, on va d'abord calculer le nombre de possibilités = 200 factoriel soir un nombre très grand

def factorielle(n) :

resultat = 1

for i in range (n)

resultat= resultat * n

n= n-1

return resultat

print(factorielle(200))

On va alors essayer de créer un algorithme glouton qui va essayer à chaque étape de trouver la solution optimale. On choisit la maison la plus proche de la mairie, puis la plus proche de cette maison. En espérant que c'est le choix le plus optimal.

Pour cela on va d'abord créer deux listes, une liste x et une liste y, elles correspondent aux coordonnées de la mairie et des maisons

Ensuite pour trouver la distance entre deux points( maisons), un élève a trouvé qu'on pouvait utiliser le théorème de Pythagore pour y arriver. Cela donne en Python:

from math import *

x=[0, 54, -15, -23, 47, 12, 28, 30, 14, -88, 2, 92, -6, 13,-27]

y=[0, 41, 99, -40, -20, 0, -99, -5, 14, -98, 16, 97, 55, 43, 3]

distances=[]

maisons=[]

def distance_entre_deux_points (xa,xb,ya,yb):

return sqrt((xb-xa)**2+(ya-yb)**2)

On rajoute ici deux listes vides qui vont nous être utile pour la suite

from math import *
x=[0, 54, -15, -23, 47, 12, 28, 30, 14, -88, 2, 92, -6, 13,-27]
y=[0, 41, 99, -40, -20, 0, -99, -5, 14, -98, 16, 97, 55, 43, 3]
distances=[]
maisons=[]

def distance_entre_deux_points (xa,xb,ya,yb):
return sqrt((xb-xa)**2+(ya-yb)**2)

dist_inter=[]
for i in range(1,len(x)):
dist_inter.append(distance_entre_deux_points(x[i-1],x[i],y[i-1],y[i]))
distances.append(min(dist_inter))
maisons.append(dist_inter.index(min(dist_inter)))

from math import *
x=[0, 54, -15, -23, 47, 12, 28, 30, 14, -88, 2, 92, -6, 13,-27]
y=[0, 41, 99, -40, -20, 0, -99, -5, 14, -98, 16, 97, 55, 43, 3]
distances=[0] # stocke toutes les distances minimales
maisons=[0] # Stocke tous les indices des maisons les plus proches
def distance_entre_deux_points (xa,xb,ya,yb):
   return sqrt((xb-xa)**2+(ya-yb)**2)

for j in range (1,len(x)):

   dist_inter=[] # stocke toutes les distances entre le point central et les maisons
   for i in range (1,len(x)):
   if i not in maisons:
   dist_inter.append(distance_entre_deux_points(x[maisons[-1]],x[i],y[maisons[-1]],y[i]))
   else : dist_inter.append(10000)
   distances.append(min(dist_inter))
   maisons.append(dist_inter.index(min(dist_inter)))

TP Algorithmes Gloutons

Activité préparatoire

TP
Algorithmes Gloutons