Algorithme de Dieu

L'algorithme de Dieu est un 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, tel que le problème des missionnaires et des cannibales. 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

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « God's algorithm » (voir la liste des auteurs)

Bibliographie

• (en) David Joyner, Adventures in Group Theory, Johns Hopkins University Press, 2002. ISBN 0-8018-6947-1

• Portail de l’algorithmique
• Portail des jeux