NSI - Loïs
Electrification d'un village et algorithme glouton :
Après les années 20, des ingénieurs se sont posé la question de l'optimisation de l'électrification des campagnes françaises. Pour trouver la longueur de câble la plus courte, ils ne disposaient pas de blobs comme l'a proposé Gerlero, ils ont donc réfléchi à comment résoudre ce problème par eux mêmes.
On ne peut pas utiliser la force brute pour tester toutes les combinaisons car le nombre de possibilité s'élève à n! (avec n le nombre de maisons) ce qui est astronomique pour un village de seulement 200 maisons.
En revanche, on peut modéliser le problème avec un algorithme glouton qui sélectionne un à un les trajets les plus courts entre chaque maison à raccorder.
Pour calculer la distance :
Un brillant élève de la classe à eu l'idée.... originale d'utiliser le théorème de pythagore pour calculer la distance entre 2 points de coordonnées cartésiennes connues. En est donc ressorti la fonction "distance_entre_deux_points" c'est une fonction qui calcule aussi surprenant que cela puisse paraître la distance entre deux points :
def distance_entre_deux_points (xa,xb,ya,yb):
return sqrt((xb-xa)**2+(ya-yb)**2)
Pour la fonction sqrt, on doit importer la bibliothèque maths, et on doit pour le calcul créer une liste x et une liste y contenant les coordonnées des maisons, et on peut déjà faire le calcul pour aller de la mairie à la première maison :
C'est déjà un début, mais le programme ne calcule que la distance entre la mairie et la première maison, et ce n'est que la première étape, il faut maintenant s'attaquer au reste et ça ne va pas être simple...
1er problème :
Ce programme, il vous semble correct?
Eh bien si on regardait ce que renvoie la console quand on l'éxecute :
>>>maisons
[0, 4, 6, 2, 11, 0, 4, 6, 2, 11, 0, 4, 6, 2, 11]
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]
maisons=[0]
en_cours=[]
def distance_entre_deux_points (xa,xb,ya,yb):
return sqrt((xb-xa)**2+(ya-yb)**2)
for j in range (1,len(x)) :
en_cours=[]
for i in range (1,len(x)):
if i not in maisons :
en_cours.append(distance_entre_deux_points(x[maisons[-1]],x[i],y[maisons[-1]],y[i]))
else : en_cours.append(1000000000)
distances.append(min(en_cours))
maisons.append(en_cours.index(min(en_cours)))
Ici, le problème semble venir des conditions, il n'est pas normalement possible d'avoir 2 fois le même indice dans la liste maisons, je ne comprends pas encore l'erreur mais j'ai des pistes de résolution, procédons par une méthode très scientifique : le tâtonnement
Pour savoir si une méthode est efficace pour résoudre un problème en informatique il suffit de se poser la question suivante : Est-ce que rester devant edupython toute la nuit pour finalement se réveiller vers 10h un samedi la tête sur son clavier valait le coup ?
Dans ce cas précis... non, il faut donc changer de méthode, je vais me faire un plan de la "ville" et voir quel chemin devrait prendre l'algorithme.
Voilà mon œuvre d'art faite sur géogebra en plaçant des points aux coordonnées de chaque maison sur un plan, maintenant je vais pouvoir mieux visualiser le problème et PEUT-ETRE le résoudre.
A moins que...
En traçant les chemins les plus courts uns à uns en partant de la mairie, je remarque que les valeurs qui se répètent dans la liste maisons ne sont même pas justes, c'est lamentable. Le problème est donc bien plus complexe que ce que j'ai imaginé (et je comprends aussi que j'ai passé une nuit entière à chercher au mauvais endroit).