| 5.AG.1. RUBIK'S CUBE
New section. Much to be added.
Richard E. Korf. Finding optimal solutions to Rubik's Cube using pattern databases. Proc. Nat. Conf. on Artificial Intelligence (AAAI-97), Providence, Rhode Island, Jul 1997, pp. 700-705. Studies heuristic methods of finding optimal solutions of the Cube. Claims to be the first to find optimal solutions for random positions of the Cube -- but I think others such as Kociemba and Reid were doing it up to a decade earlier. For ten random examples, he found optimal solutions took 16 moves in one case, 17 moves in three cases, 18 moves in six cases, from which he asserts the median optimal solution length seems to be 18. He uses the idea of axial moves and obtains the lower bound of 18 for God's Algorithm, as done in my Notes in 1980. Cites various earlier work in the field, but only one reference to the Cube literature.
Richard E. Korf & Ariel Felner. Disjoint pattern database heuristics. Artificial Intelligence 134 (2002) 9-22. Discusses heuristic methods of solving the Fifteen Puzzle, Rubik's Cube, etc. Asserts the median optimal solution length for the Cube is only 18. Seems to say one of the problems in the earlier paper took a couple of weeks running time, but improved methods of Kociemba and Reid can find optimal solutions in about an hour.
Dostları ilə paylaş: |
