Cette création est mise à disposition sous un contrat Creative Commons
Table des matières
Recherche de la solution optimale du taquin
Présentation
Ce projet a été réalisé conjointement avec Olivier Robin, sous forme de projet du cours long d'Informatique à l'Ecole Polytechnique.
Sujet
Le but était de trouver la solution optimale (au sens du nombre du coups) au jeu du taquin.
Il fallait également minimiser le temps de recherche : une exploration “naïve” de toutes les combinaisons possibles était donc exclue.
Le code a été écrit entièrement en Java, langage principal à l'Ecole Polytechnique.
Réalisation
L'algorithme dit en IDA-* a été très utile. On peut l'appliquer à une recherche de meilleur trajet entre Paris et Lyon. Si l'on sait que la distance finale sera inférieure à 500 km et que l'on se trouve en un point à 70 km de route de Paris et à 470 km à vol d'oiseau de Lyon
1)
, alors on peut abandonner la recherche en ce point. Cela a pour effet de limiter la recherche à une ellipse dont Paris et Lyon sont les foyers. L'inconvénient est qu'il faut avoir une idée de la distance finale.
Résultats
Les résultats sont très variables. En effet, certaines positions ne demandent qu'une poignée de secondes (pour 500 000 itérations par exemple). Mais d'autres positions, non nécessairement plus difficile pour un humain, nécessitent jusqu'à 15 000 000 d'itérations et donc une centaine de secondes.
1)
Il faut bien sûr que la distance à vol d'oiseau soit toujours inférieure à la distance par la route
