Optimisation par algorithme glouton : passage de câble

Version imprimable

10/08/2015, 11h02
Sve@r

5 pièce(s) jointe(s)

Optimisation par algorithme glouton : passage de câble

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)
Pièce jointe 185024

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)
Pièce jointe 185025

La première approche serait donc de prendre l'isobarycentre des différentes hauteurs. Mais cela ne convient pas dans cette seconde configuration possible...
Pièce jointe 185026

Dans ce cas, les différents tests montrent que le cable doit passer par les deux maisons situées à la même hauteur.
Pièce jointe 185027
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...
Pièce jointe 185028.

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...)
10/08/2015, 11h30
tbc92

Bonjour,

Il faut prendre la valeur médiane.
C'est à dire :
- S'il y a un nombre impair de maisons, prendre la maison du milieu (en triant de la plus basse à la plus haute)
- S'il y a un nombre pair de maisons, prendre n'importe quel entier entre les 2 maisons du milieu (toujours en triant de la plus basse à la plus haute)

Et dans certains langages de programmation, la fonction médiane() existe.
10/08/2015, 15h14
Flodelarab

Bonjour :coucou:

:lol: Je l'ai faite, cette épreuve. En bash avec vim, bien sûr.

Je te ferais remarquer que personne ne te demande la position de la ligne réseau mais la quantité de câble nécessaire.

Deuxième remarque: pense à ce qu'a fait le mathématicien Gauss quand sa maitresse lui a demandé d'additionner les nombres de 0 à 100.

:ccool: Bonne chance!
10/08/2015, 16h05
Sve@r

Citation:

Envoyé par tbc92

Il faut prendre la valeur médiane.

Zut. J'avais bien pensé aux probas mais j'étais parti dans les droites de régression linéaires. Ca me donnait alors une droite avec une certaine pente ce qui était le plus optimisé possible mais ne correspondait pas au crière initial d'une droite obligatoirement horizontale. Et je suis complètement passé à coté de la médiane :hola:
Effectivement c'est tout con et ça fonctionne. :applo:

Citation:

Envoyé par Flodelarab

En bash avec vim, bien sûr.

Oui moi aussi j'utilise vim. Mais en bash !!! T'as franchement pas honte toi. M'étonne que t'aies pas tenté brainfuck !!!
Perso je voulais compléter sais plus quel succès qui demandait de résoudre une épreuve dans 5 langages différents donc j'ai résolu Thor en bash, Python, python3, C et C++ mais bon, quand on a Python, le bash ça devient un peu chiant...

PS: à propos de brainfuck, l'épreuve "hobbit" du challenge "optimisation" est en fait une épreuve de brainfuck :P

Citation:

Envoyé par Flodelarab

Je te ferais remarquer que personne ne te demande la position de la ligne réseau mais la quantité de câble nécessaire.

Evidemment (oui c'est vrai qu'après coup ça devient évident :oops:). Une fois qu'on a la médiane (équivalent à la position de la ligne) on se rend compte qu'elle s'additionne pour chaque élément d'un coté et se soustrait pour chaque élement de l'autre donc en fait elle disparait et ça revient à faire "somme(tout ce qui est après) - somme(tout ce qui est avant)". Mais au départ comme je ne pensais pas à la médiane je ne pouvais pas en déduire cet enchainement logique.

Bon, allez, :plusser: pour toi aussi :cool:

Citation:

Envoyé par Flodelarab

:ccool: Bonne chance!

Ben suis 941° avec 3330 pts :applo: :mrgreen:
Mais j'ai encore des épreuves partiellement résolues (toujours d'ailleurs sur des sujets d'algo glouton comme les montagnes russes ou la surface des lacs...)

Citation:

Mais en bash !!! T'as franchement pas honte toi. M'étonne que t'aies pas tenté brainfuck !!!

Ben, cela me permet de ne rajouter qu'une ligne sur cette épreuve...
Code:

1 2 3 4 5 6 7 8 # Auto-generated code below aims at helping you parse # the standard input according to the problem statement. read N for (( i=0; i<N; i++ )); do read X Y echo "$X $Y" done | sort -n -k2 | awk -vN=$N '(NR==1){OFMT="%1.0f";xmin=$1;xmax=$1;} (N==1){exit;} (NR>(N+1)/2){total+=$2;} ($1<xmin){xmin=$1;} ($1>xmax){xmax=$1;} (NR<(N+1)/2){total-=$2;} END{print xmax-xmin+total;}'
Bravo pour ton classement. Perso, je ne ferais sans doute qu'en bash. Après ça ne m'intéresse plus vraiment.

11/08/2015, 16h56
bbo08

dans la 3eme configuration , pourquoi ne pas relier les maisons du même niveau (ici 3) et relier les niveaux entre eux avec seulement deux câbles verticaux ?
11/08/2015, 19h11
Sve@r

Citation:

Envoyé par bbo08

dans la 3eme configuration , pourquoi ne pas relier les maisons du même niveau (ici 3) et relier les niveaux entre eux avec seulement deux câbles verticaux ?

Parce qu'il s'agit d'un exercice et que l'énoncé dit que chaque maison est relié de façon individuelle au cable principal...