Retour sur les longs parcours dans un quadrillage.
En première approximation et sans tenter d'user de moyens raffinés pour optimiser les choses, la longueur d'un chemin maximal dans un carré 4x4 est de l'ordre de 45,5. Je vous fais grâce du tracé, strictement illisible malgré la dimension modeste de la grille. La longueur minimale est bien évidemment de 15 mais elle ne nous intéresse pas du tout.
Une nouvelle approximation de la dimension fractale du chemin maximal serait donc log (45,5/16,77) / log (4/3) = 3,46, alors que le chemin minimal (qui tend évidemment vers 2) serait ici estimé à log (15/8)/log(4/3) soit 2,18.
A suivre pour des dimensions supérieures.
PS : tout ceci me rappelle l'agenda secret de Jacques Chirac, bouquin publié par les auteurs des guignols de l'info sur la campagne des lagéislatives menée par le président en question, qui semblait beaucoup s'ennuyer. Et qui a parcouru les grandes (et moins grandes) villes de province par ordre alphabétique.
Commentaires :
Re:
Je me demande, si l'on considère quatre points consécutifs du chemin A, B, C, D, si l'on peut obtenir facilement une caractérisation permettant de savoir si le chemin A, C, B, D est meilleur.
Re:
Re:
Ah ok je pense que je vois. Partant d'un état plus ou moins aléatoire, on peut facilement faire une petite ré-optimisation locale en permutant ce qui peut l'être histoire de générer un maximum de croisements :
- Je pars du début du parcours
- Je prends 4 points consécutifs ABCD
- Si AB+CD < AC+BD, j'échange B et C, et je recommence en remontant de 2 points puisque le quadruplet xyAB est devenu xyAC.
- Sinon je passe à BCDE etc.
C'est ça ton idée? Je vais tester.