God's algorithm
God's algorithm (english God's Algorithm) is a term from discussion on the optimal solution to the Rubik's Cube. The phrase comes from the English group theorist John Conway or one of his colleagues in Cambridge. It can also be related to other problems in combinatorics and game theory. He describes each algorithm that produces a solution with smallest greatest possible number of steps or moves.
Scope and definition
The term refers to puzzles that can assume a finite number of " configurations ", with a rather small, well-defined amount of " trains " that represent transformations between configurations. Solving a puzzle is, ( finite number ) to achieve one or more of certain specific " end configurations " from any arbitrary initial configuration, by applying a sequence of moves.
In some well -known puzzle applies to the description, eg Mechanical puzzles such as the Rubik's Cube, Tower of Hanoi and the 15- puzzle. Also Solitaire is one of them, as many logic puzzle how the problem of missionaries and cannibals. Share you with the mathematical modeling is as a directed graph, where the configurations to points and the trains to be arrows.
An algorithm is considered as an expectorant when an output in the form of a Zugsequenz that produces the desired configuration generated from the input of an arbitrary initial configuration, if the puzzle of this initial configuration is solvable, and otherwise outputs the impossibility of a solution. A solution is optimal, if the sequence of moves is as short as possible. A God - algorithm solves a puzzle always optimal.
A real "God's algorithm " should also be feasible, ie do not require an exceptional amount of space or time. So would a huge lookup table, indexed for all launch configurations, solutions very quickly spend, but occupy far too much space.
Instead of asking for a complete solution, it is also for the best first single train after the start configuration issues. An algorithm for individual trains can be transformed into an algorithm for the overall solution by repeating it until the final configuration. Conversely, so be disassembled and the algorithm for the overall solution in algorithms for single traits.