il me semble que le chemin pourrait se recouper non ?

Bonjour Nodgim

Dans cette disposition les parcours rouges et bleus sont de même longueur :



Si on déplace un point on raccourcit l'un d'entre eux .

Sauf erreur

Vasimolo

Tout d'abord merci à Vasimolo pour son appétissant gâteau, le sujet est très intéressant.

En sortant l'artillerie lourde, il me semble que j'ai une légère amélioration à apporter au problème initial.

En premier lieu, remarquons qu'il n'est pas nécessaire de se soucier des croisements éventuels quand on recherche une solution. En effet, si un chemin passant par tous les points contient au moins un croisement, alors on sait qu'il existe un chemin plus court, comme le montre l'illustration (le raccourci est tracé en rouge, il fournit un chemin strictement plus court par l'inégalité triangulaire).



Pour résoudre notre problème, on va déterminer une ligne brisée qui passe par nos 49 points. Pour savoir dans quel ordre on va visiter ces 49 points, nous allons avoir recours à la courbe de Sierpinski.



Nul besoin de considérer la courbe de Sierpinski limite, qui s'auto-intersecte, ce qui complique les choses. On la trace juste avec un nombre d'itérations suffisant pour qu'elle passe à une distance suffisamment proche des 49 points, pas plus loin que epsilon, epsilon étant en définitive aussi petit que l'on veut.

Les 49 points sur la courbe de Sierpinski correspondent à 49 nombres de [0;1[. On relie ainsi ces 49 points dans l'ordre des 49 nombres, par des segments. Remarquons qu'il est alors possible que la ligne brisée obtenue s'auto-intersecte, d'où notre remarque en préambule.



Nous allons ensuite avoir recours à un lemme pour majorer la longueur de la ligne brisée. Chaque point de la courbe est repéré par un nombre de [0;1[, et on suppose que le carré est de côté 1 pour simplifier les calculs (on ne tiendra compte des 20 cm de côté qu'à la fin).

Lemme : si deux nombres de [0;1[ sont à une distance d (cela boucle : par exemple, la distance entre 0,9 et 0,1 est de 0,2), alors les deux points correspondants sur la courbe de Sierpinski sont à une distance inférieure ou égale à 2*racine(d).

Par exemple, les points repérés par 1/8 et 3/8 sont à la distance 1/4 sur [0;1[, et à la distance 1 sur la courbe, or 2*racine(1/4)=1 (c'est un cas où il y a égalité).

On peut maintenant majorer la longueur de la ligne brisée. Si on appelle d_i les distances entre deux nombres consécutifs sur [0;1[, alors on a somme(d_i)=1, et la longueur de la ligne brisée est <= somme(2*racine(d_i)) par le lemme. Par concavité de la fonction racine, on obtient que cette somme est <= 49*2*racine(1/49).

Enfin, on peut gratter un chouïa en se débarrassant d'une des 49 liaisons entre deux points (autant choisir la plus grande), pour passer d'une courbe fermée à une courbe ouverte. La longueur de la ligne brisée est donc au plus 48*2*racine(1/49)*(20 cm) = 1920/7 cm ~ 274,3 cm. Tout ça pour ça

La construction de la courbe est illustrée ici :

http://en.wikipedia.org/wiki/Sierpi%C5%84ski_curve

Quel que soit l'ordre de la courbe, on pose à 0 le point de la courbe situé juste au dessus du centre du gâteau, puis on tourne autour de la courbe dans le sens des aiguilles d'une montre. Si on sépare le gâteau en 4 carrés plus petits, le carré en haut à droite contient les points entre 0 et 1/4, celui en bas à droite contient les points entre 1/4 et 1/2...

C'est plus clair, ou je précise encore ?

S'il est vrai que la courbe de Sierpinski est tordue, elle ne sert qu'à déterminer l'ordre dans lequel les points seront visités. La ligne brisée obtenue n'est elle pas si tordue que ça, cf la 3e illustration.

Et puis, ça ne permet de gagner qu'un micropouième par rapport à la méthode de Promath-...

Je me suis rendu compte a posteriori que l'idée n'était pas si originale que ça : http://en.wikipedia.org/wiki/Sierpi%C5%84ski_curve "it has been used as a basis for the rapid construction of an approximate solution to the Travelling Salesman Problem (which asks for the shortest sequence of a given set of points): The heuristic is simply to visit the points in the same sequence as they appear on the Sierpiński curve".