# two-phase algorithm



## FMC (Sep 30, 2010)

the two phase algo. reduces the cube first to the 
subgroup:G1 = <U,D,R2,L2,F2,B2> and then solves 
the entire cube using U,D,R2,L2,F2,B2 turns only
now the question is:
though the cube can be solved using U,D,R2,L2,F2,B2,
is it necessary that the optimal solution should always
contain moves U,D,R2,L2,F2,B2 ? for example,from G1 we can also 
solve the cube with U,D,R,L2,F2,B2(please note R instead of R2).
can anyone prove that the optimal solution of G1 
should only contain U,D,R2,L2,F2,B2 and not U,D,R,L2,F2,B2?
A much more straight forward question:
from the solved state if i just use the R and U turns to scramble,
can we have optimal solution with R,U and F turns?


----------



## Kirjava (Sep 30, 2010)

If you reduce the cube to a subset, a bigger generator group will produce equal or shorter solutions.

Here's a <R,U> vs <U,L,D,R> example;

U2 R2 U2 R2 U2 R2
U2 L2 D2 R2 D2 L2

Something that produces a shorter solution with a bigger generator is the MU 6flip;

<M,U>

M' U M' U2 M U M U M' U M'

<R,r,U,M>

R U' r' U' M' U r U r'

I can't think of a good example for <UDR2F2L2B2> vs <UDRL2F2B2> right now but I'm certain they exist.


----------



## Stefan (Sep 30, 2010)

_"Take for example the cube C generated by R L U2 R L . F (6 moves)."_
-- http://kociemba.org/math/imptwophase.htm


----------



## FMC (Sep 30, 2010)

so if they exist,and if i understand well,is the optimality of kociemba algo. questionable?


----------



## qqwref (Sep 30, 2010)

FMC said:


> so if they exist,and if i understand well,is the optimality of kociemba algo. questionable?


 
The Kociemba algorithm is not designed to be optimal; the website itself says that it can miss the optimal solution. It is designed to quickly search for a reasonably short solution. Cube Explorer comes with a fast optimal search algorithm as well.


----------



## FMC (Oct 1, 2010)

qqwref said:


> The Kociemba algorithm is not designed to be optimal; the website itself says that it can miss the optimal solution. It is designed to quickly search for a reasonably short solution. Cube Explorer comes with a fast optimal search algorithm as well.


 
you say that cube explorer's fast optimal search algorithm is different from kociemba's
algorithm.then how does the optimal search algorithm work?


----------



## Herbert Kociemba (Oct 1, 2010)

FMC said:


> you say that cube explorer's fast optimal search algorithm is different from kociemba's
> algorithm.then how does the optimal search algorithm work?



It was Mike Reids idea which I implemented here (in the basic optimal solver, not the huge solvers): Look only for solutions of phase1 in three orthogonal directions in parallel, that is for solutions in the intersection of <U,D,R2,L2,F2,B2>,<U2,D2,R,L,F2,B2> and <U2,D2,R2,L2,F,B>. No phase 2 at all, just continue until the id-cube is found.


----------

