Voyageur du commerce? onagain

[fatal_error]

Salut,

en ce moment, mon kiffe c'est le TPS.
Le truc, c'est que j'ai un ptit problème, mais je sais pas si mon intuition est bonne...et j'arrive pas à la prouver.

Donc on est dans un repere (o,i,j)
On se donne p points, respectivements de coordonnés P_0(x_0;y_0), P_1(x_1,y_1)...
On trace un chemin, qui part de P_0, et qui arrivent jusqu'à P_19 de longueur p-1 (cad qu'il passe par chacun des points, une et une seule fois).

Ce que j'aimerais montrer, c'est que ce chemin n'est PAS optimal si il y a un croisé.

Ce que j'appele croisé, c'est par exemple : si on a 4 points qui forment un quadrilatère classique ABCD, alors on voit que (AC) et (BD) se croisent (ce qui invaliderait le chemin ACBD)

Pour 4 , ya ptet moyen de m'en sortir, mais pour plus...

[Doraki]

Avec l'inégalité triangulaire tu devrais pouvoir montrer que si les segments AC et BD se croisent, alors AC+BD >= AB+CD, et puis après faut que t'expliques comment tu adaptes le chemin pour que ça se décroise.

[fatal_error]

A priori,
en fait si j'ai mes n points consécutifs qui forment un chemin, j'ai
() qui s'intersecte avec () ou () ...
L'idée que j'ai, c'est de looker si (p_1,p_2) s'intersecte avec ()
si c'est le cas
alors je connecte (et donc deconnecte )
puis connecte
Bon, la reconnexion est un peu naive, mais a priori, ya moyen que c'est pas trop mauvais, faudra que je teste.

[Ben314]

Salut,
J'ai l'impression qu'il y a deux problèmes :
1) La plupart du temps, dans le problème type "voyageur de commerce", les distances entre les points ne sont pas des distances euclidiennes entre points du plans, mais des trucs quelconques donc ton algo ne s'appliquera que à des cas trés particuliers ou on a une représentation plus ou moins géométrique du problème.
2) Etant donné n points du plan affine, je pense qu'il y a encore une énorme foultitude de façon de les relier entre eux sans faire de croisements donc je sais pas si ça gagne gras de savoir que la soluce est dans cet ensemble là (qui ne vas pas être stable par grand chose donc il sera assez difficile d'y appliquer une méthode style "recuit")

[fatal_error]

salut ben,

ben ya un paquet de méthode pour résoudre le truc. J'ai vu que ca peut se faire par programmation linéaire(!).

Mais je laisse ca à ceux qui ont un réel besoin pour le tps. Jtrouve plus marrant d'arriver à identifier des patterns et à les résoudre.

1)pas de soucis, je suis tout ce qu'il ya de plus géométrique! et ma distance c'est l'euclidienne sans la racine carrée. Tant pis si c'est pas réutilisable.

2) en fait, je couple ca avec les plus proches voisins. J'initialise un trajet de proche en proche (la derniere ville connectée est la plus proche de l'avant derniere).
Ca permet d'éviter les ptites boucles de merde (mais pas les grosses).
Apres, pour les grosses boucles, jvais tenter les intersections, ou eventuellement du clustering sur les points les plus proches avec des points d'entrée.

[Ben314]

De toute façon, je disait ça juste pour que tu imagine pas "que tu fa décrocher la timbale" et que ton truc, ça resterait une tentative pour trouver un chemin pas totalement minable...

Par contre, fait gaffe, si j'ai bien compris, et que tu prend dist( (x,y), (x',y') )=(x-x')²+(y-y')², alors ça vérifie pas l'inégalité triangulaire ni le fait que la longueur d'un segment est égale à la somme de deux sous-segments qui le composent.
Donc la preuve comme quoi "quand ça croise c'est pas bon" n'est plus valable dans ce contexte.

[fatal_error]

voila, juste pour dire que ca rend pas trop mal a laide de deux trois idée naives et une correcte:
-une brute force sur 5 villes adjacentes du chemin. Puis on decale la fenetre de brute force (un peu comme une convolution)
-un rameneur de ville, ou on essaie dans un certain cercle d'insérer une ville a coté de soi
-un 2opt (jcrois c un truc dans le genre, jai lu un doc hier mais jétais pété, jai rien retenu XD), fin bref, c'est le truc pour niquer les croisillons.
pis on boucle...

Au tout début, on génère les n chemins par derniere ville la plus proche (comme dit dans un précédent post). Pis on garde que le meilleur.




Uploaded with ImageShack.us

Apres, on pourrait faire du recuit et tout, mais bon, je verrai pour plus tard ca...
Au final, j'ai gardé ma métrique avec mes carrés, et je recompute a chaque fois le trajet (:) ), au lieu de me servir de l'inégalité qui nécessite une racine carrée comme a bien fait de me l'apprendre ben. On pourrait faire mieux, mais bon, plus assez de neurones.

ps: ben même avec ma métrique de carrés, tous les croisillons s'en vont! mais bon, je ne saurais pas l'expliquer...