Two directional serch for cube solutions...
Submitted by crepeau on Wed, 07/14/2004 - 09:06.
I was wondering if anyone has ever build a bi-directional tree search for solving specific cube positions.
Let me explain.
Suppose one starts with a solved cube (3x3x3) and find all the configurations after one rotation, and so on say until 10 or 11 rotations. The resulting tree will contain a large number of nodes, but not completely unreasonable.
Now suppose you wish to find the shortest solution for a specific configuration. You may start building another tree similar to the above and look for collisions between nodes of the two trees. After exploring say 10 or 11 levels of the tree it is very likely that the two trees will connect and the shortest path can be obtained.
Anybody ever tried that ?
I was wondering if anyone has ever build a bi-directional tree search for solving specific cube positions.
Let me explain.
Suppose one starts with a solved cube (3x3x3) and find all the configurations after one rotation, and so on say until 10 or 11 rotations. The resulting tree will contain a large number of nodes, but not completely unreasonable.
Now suppose you wish to find the shortest solution for a specific configuration. You may start building another tree similar to the above and look for collisions between nodes of the two trees. After exploring say 10 or 11 levels of the tree it is very likely that the two trees will connect and the shortest path can be obtained.
Anybody ever tried that ?