Bonjour à tous
Je viens ici car je suis désespérément bloqué sur une optimisation d'algorithme glouton depuis plusieurs jours. Je ne suis d'ailleurs même pas certain que cette optimisation soit possible mais sait-on jamais...
Le principe est le suivant: on reçoit des ordonnées de maisons placées à différentes hauteurs sur un terrain (comme le montre cette image)
Le but de l'algo est de trouver la position d'un cable réseau qu'on placera horizontalement de telle façon que le rajout de cable supplémentaires (verticaux) sera la plus économique posible. Si dans l'exemple précédent on place le cable en position 1 ou 3, il faudra alors 3 unités de plus pour relier les autres maisons. Mais si maintenant on le place en position 2, il n'en faudra alors plus que 2 (voir image)
La première approche serait donc de prendre l'isobarycentre des différentes hauteurs. Mais cela ne convient pas dans cette seconde configuration possible...
Dans ce cas, les différents tests montrent que le cable doit passer par les deux maisons situées à la même hauteur.
Et ce serait la même chose même s'il y avait une hauteur intermédiaire n'ayant pas de maison.
Je me dis "ok, te suffit de choper la hauteur qui aura le plus de maisons" mais cela ne va plus dans cette 3° configuration ou justement le cable n'est pas placé là où il y en a le plus...
.
Donc pour l'instant, mon algo est tout con: une fois que j'ai tout récupéré (les différentes hauteurs arrivent une à une), j'effectue un balayage de toutes les positions possibles et ressort la plus économique. Ca fonctionne, c'est évident, malheureusement cet algo ne répond pas assez vite à la contrainte temporelle (il doit donner la solution dans un certain laps de temps). D'où tentative d'optimisation mais rien en fonctionne. J'ai d'abord essayé de calculer la hauteur à chaque nouvelle maison en me disant que soit le cable restait à sa position initiale, soit il se placait forcément sur la nouvelle maison mais la première image montre que ça ne fonctionnera pas (à la première maison en Y=0 le cable se positonne en Y=0, puis la seconde en Y=1 le cable reste en Y=0 puis à la 3° en Y=2 le cable devrait aller en Y=1 mais à ce moment là ce test ne se fait plus).
La 3° configuration me donne bien une idée: soit il y a une seule hauteur ayant le plus de maisons et c'est sur celle-là que doit se positionner le cable, soit il y en a plusieurs et le cable devra alors être placé à l'isobarycentre non pas de toutes les positions mais seulement des positions ayant le plus de maisons. Mais je pense que cette recherche des n hauteurs ayant le plus de maisons sera aussi longue que mon algo initial.
Si quelqu'un avait une idée...
Merci de m'avoir lu jusqu'au bout
PS: les hauteurs sont toujours des nombres entiers. De même, le cable doit-être positionné sur une hauteur entière. Et je suis presque sûr que le cable devra forcément être placé là où il y a une maison (ça m'évite de tester tous les intervalles dans le cas où il y a une maison en Y=0 et une autre en Y=1000 mais ça n'est pas encore assez rapide...)
Partager