Et non, ce n'est pas de Lorca ni de Nono qu'il s'agit.
Je ne sais plus très bien d'où m'est venue l'idée suivante. Prenons un quadrillage avec des cases carrées d'une unité de côté chacune, par exemple lui-même carré, et parcourons-le de case en case, avec pour seule règle de ne jamais repasser par une case où l'on soit déjà passé. On part d'où l'on veut, on arrive où l'on veut, et on saute d'une case à l'autre comme on veut.
Bien. Cherchons maintenant le chemin le plus court pour faire tout ça. C'est trivial, il y a un paquet de solutions consistant à passer systématiquement d'une case à l'une de ses voisines. La longueur du chemin est le nombre de cases moins une. Si je prends par exemple le carré 2x2 suivant :
A | B |
C | D |
On a toute une série de chemins comme ABDC, ACDB etc. qui font 3 unités de long.
Aucun intérêt. Mais quel est le chemin le plus long? Sur un exemple aussi simple il n'y a en fait que 3 familles de 4 parcours :
- Les parcours en "U" comme ABDC, de longueur 3
- Les parcours en "Z", comme ABCD, de longueur 2+racine(2) soit 3.41
- Les parcours en... alpha, comme BCAD, de longueur 1+2 racine(2) soit 3.82.
Après ça se complique très vite, le nombre de chemins possibles croissant comme (N^2)!/2 même si quelques symétries peuvent venir nous aider. Je ne vois pas de façon simple (ni même compliquée d'ailleurs) de générer les familles de parcours de même longueur. Et les parcours de longueur maximale ont une tête pas symétrique du tout.
Par exemple, sous réserve de vérification car pour l'instant je n'ai pas encore codé le bidule, pour un carré 3x3 :
A | B | C |
D | E | F |
G | H | I |
je trouve comme chemin très long AIDCGBHFE qui fait 3+5 racine(2)+3 racine(5) soit environ 16.77 à rapporter au chemin court de longueur 8.
Première question : comment on calcule un tel machin pour des carrés plus grands? Ca ressemble franchement au voyageur de commerce, mais à l'envers. A 3x3 cases il y a 181440 chemins. Faisable dans un temps honnête par un pécé de base, et je pense que l'humain de base que je suis ne doit pas être très loin. A 4x4 cases on passe à 10461 milliards. L'air de rien ça peut prendre un certain temps. On peut se réfugier dans les expédients habituels genre tirages aléatoires puis recuit simulé.
Voire tirages aléatoires seulement si l'on passe à la seconde question : ces machins ont peut-être une dimension fractale amusante. Quand on passe de 2x2 à 3x3, le plus court chemin passe de 3 à 8. Log(8/3) / Log (3/2) donne 2.41 mais plus généralement cette suite donne clairement une dimension fractale de 2. Par exemple de 10x10 à 11x11 on passe de 99 à 120 et le rapport des logs des longueurs aux côtés donne 2.018. Le plus long chemin passe quant à lui de 3.82 à 16.77 donc une première estimation de dimension de 4.03. Je veux bien que ça tende vers 2 mais ça commence mal.
J'ai fait une très rapide recherche sur internet. Ce problème est forcément déjà connu. Des idées?
Commentaires :
Re:
Pour finir ce premier épisode, je suis passé à l'acte et ai pondu un premier bout de code. Le pire chemin est, par exemple, HAFDIBGCE, de longueur 2+5 racine(2)+3racine(5) soit environ 17,78. La longueur moyenne d'un saut est de 2.22.
Correction par rapport au post précédent : la diagonale fait N racine(2) dont la dimension fractale est majorée par 3 et non par 2,5.
Maintenant qu'un premier pas est franchi côté codage, la voie est ouverte pour passer à des valeurs de N plus importantes, avec comme bémol que la solution trouvée sera approximative compte tenu de la combinatoire.
Je me réponds tout seul. Je me demandais ce matin si mes interrogations sur une éventuelle dimension fractale supérieure à 2 avaient un sens.
Le plus court chemen est évidemment en N^2.
Le plus long chemin comporte N^2-1 segments, mais contrairement à ce qui se passe pour le plus court chemin où ils sont tuos de longueur 1, leur longueur augmente avec la dimension. Un majorant strict consisterait à prendre comme pire cas la diagonale du carré, de longueur (2N)^1/2, ce qui indiquerait une dimension fractale 2.5.
Donc il n'est pas impossible, a priori, qu'en s'y prenant très mal on puisse faire pire que le mouvement brownien.
Autre chose. N'ayant pas de moyens informatiques décents, j'ai fait une bricole avec un tableur sur le tableau 3x3, qui m'a sorti un intéressant parcours HAFDIBGCE, de longueur 2+3racine(2)+5racine(5) soit environ 17.44
A suivre