Algorithme de Dieu

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.
Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

Les informations figurant dans cet article ou cette section doivent être reliées aux sources mentionnées dans les sections « Bibliographie », « Sources » ou « Liens externes » ().

L'algorithme de Dieu est une notion qui vient de discussions sur la méthode la plus rapide pour résoudre le Rubik's Cube, mais qui s'applique à la résolution d'autres casse-tête combinatoires et jeux mathématiques. Cette notion renvoie à un algorithme qui donne le nombre minimum de mouvements pour atteindre la solution, un être omniscient étant capable de déterminer le mouvement optimal à partir de n'importe quel état.

Étendue

Cette notion s'applique aux casse-tête qui ont un nombre fini d'états, et « quelques mouvements » bien définis permettant de passer d'un état à un autre. Résoudre le casse-tête signifie atteindre une position précise en appliquant une suite de mouvements, à partir de n'importe quel état initial.

Quelques casse-tête mécaniques répondent à ces exigences, comme le Rubik's Cube, les tours de Hanoï et le taquin. Le solitaire répond également à ces exigences, ainsi que les casse-tête de logique, tels que les problèmes de passage de rivière. Ils peuvent être modélisés mathématiquement par des graphes orientés dans lesquels les sommets sont les états et les arcs, les mouvements.

Notes et références

Bibliographie