albedo a écrit :
gregory1324 a écrit :
WillieTheWimp a écrit :
O--O--O--O
|**|**|**|
O--O--O--O
|**|**|**|
O--O--O--O
J'ai 19 Km !!!!
De diouf j'en suis qu'a 20
bon j'arrete de chercher ma femme me prends pour un malade avec mes schemas
bon, dans ce cas là, je vais expliquer le truc, alors
y'a surement d'autres chemins possibles, mais en voilà un qui fait 19
on part du O au milieu (2eme ligne) tout a gauche et puis, on suit le trajet :
haut
droite
droite
droite
bas
bas
gauche
gauche
gauche
haut
droite
haut
droite
bas
gauche
bas
droite
haut
droite
voila le parcours fait en 19km. Gregory doit en avoir un similaire, en tout cas, un qui part du meme point et qui arrive au meme (à la symetrie près)
Bon, j'explique un peu comment ca marche
j'avais parlé de mettre sur chaque immeuble le nombre de rues auxquelles il est relié, ca donne ça :
2--3---3---2
|**|**|**|
3--4---4--3
|**|**|**|
2--3---3---2
Bon, maintenant, vous vous demandez a quoi ca sert ...
en fait, il faut raisonner sur les immeubles. Si le balayeur rentre dans un immeuble par une rue, il faudra qu'il en ressorte (par une autre rue si possible, pour eviter les "gaspillages").
Dans le cas ou l'immeuble est relié a 2 ou 4 rues, ça pose aucun problème, parce que le balayeur rentrera dans l'immeuble par une rue, et ressortira par une autre pas encore utilisée (on se debrouillera pour, en tout cas)
Mais dans le cas où l'immeuble est relié a 3 rues, le balayeur sera obligé de passer 2 fois par cet immeuble pour nettoyer toutes les rues, mais, alors que la premiere fois, il pourra rentrer et sortir sans probleme par 2 rues differentes, la 2eme fois, il sera obligé de passer par une rue qu'il aura dejà emprunté.
On voit bien que c'est au niveau des immeubles reliés a 3 rues que se situent les "pertes", et c'est ça qui fait que le balayeur sera obligé de repasser plusieurs fois par une même rue.
A partir de là, il faut minimiser ces pertes.
Le truc, c'est de commencer et de finir le trajet sur un immeuble 3 de facon à ce qu'il n'y ait pas de pertes sur ces 2 immeubles là
Ensuite, il reste 4 immeubles 3. On s'arrange donc pour que les pertes fassent intervenir à chaque fois 2 immeubles 3 (faites le schema sur un papier avec les numeros et refaites le trajet pour bien voir ça)
De cette façon, on a bien le trajet optimal.
(faites bien le schema sur un papier avec les numeros si c'est pas tout a fait clair, ce que je dis)