非专业分析KCube

aubell

目前，Kociemba是我们学习最少步数时无法绕开的名字。

我准备把 Greg Schmidt的程序KCube1.0分析一下，希望真正
对2-phase理解。

大名鼎鼎的CubeTwister里有一个求解的程序，大家在网上下载到源码以后，
在这个目录层次下可以找到：
cubetwister-2.0alpha125src\CubeTwister\src\main\ch\randelshofer\rubik\solver

这个程序是把KCube用Java重写了，喜欢看java代码的朋友可以看看。

遇到难的地方，大家一定要不吝赐教啊。

有人支持吗？

感谢大家的支持

夜雨听风
329774632
AlphaCB
mengfl
斜月

yanzi7816
今夜微凉
zbyxzh
dangerxxxx
r_517

yq_118
臭虫
ynyht
superflip
oyyq99999
superacid
铯_猪哥恐鸣
ggglgq
cube_master

[ 本帖最后由 aubell 于 2010-5-1 15:52 编辑 ]

锋魔方

支持支持楼主呢

锋魔方

感谢楼主。在8年前就研究了。我这小小辈学习呢。不过现在我用VS2017编译是出好多错误的，

lovelesszhou

支持一下，虽然看不懂。。。

aubell

伪码是这样的：

1. maxLength=9999
   
2. 
   
3. function Kociemba ( position p)
   
4.   for depth d from 0 to maxLength
   
5.     Phase1search( p; d )
   
6.   endfor
   
7. endfunction
   
8. 
   
9. function Phase1search( position p; depth d )
   
10.   if d=0 then
    
11.     if subgoal reached and last move was a quarter turn of R, L, F, or B then
    
12.       Phase2start( p )
    
13.     endif
    
14.   elseif d>0 then
    
15.     if prune1[p]<=d then
    
16.       for each available move m
    
17.         Phase1search( result of m applied to p; d-1 )
    
18.       endfor
    
19.     endif
    
20.   endif
    
21. endfunction  
    
22. function Phase2start ( position p)
    
23.   for depth d from 0 to maxLength - currentDepth
    
24.     Phase2search( p; d )
    
25.   endfor
    
26. endfunction
    
27. 
    
28. function Phase2search( position p; depth d )
    
29.   if d=0 then
    
30.     if solved then
    
31.       Found a solution!
    
32.       maxLength = currentDepth-1
    
33.     endif
    
34.   elseif d>0 then
    
35.     if prune2[p]<=d then
    
36.       for each available move m
    
37.         Phase2search( result of m applied to p; d-1 )
    
38.       endfor
    
39.     endif
    
40.   endif
    
41. endfunction  

复制代码

不是去掉-1。我想我要慢慢理解这个2-phase。

oyyq99999

把-1去掉不行，我后来试的另一个打乱出现了两个16步解，而且第二个是在threshold=15的时候第一阶段16步，第二阶段0步

aubell

回楼上：
     if (depth >= min_solution_length-1)
            return OPTIMUM_FOUND;
这一句
把-1去掉就有了。

oyyq99999

有个问题，试试 R L U2 R' L' F 这个打乱，最后解出来的不是最短

aubell

话说这么小的程序，还要动用VC6的IDE环境吗？
用notepad++就好了。
感觉再用 .NET 下的VC编译环境，就像用炮轰小鸟了。

我已经out很久了，还没用上 .NET，也还没学习Java。准备改投gcc 的怀抱了。
他们说：.NET和Java是一个金碧辉煌的坑。我还没勇气跳下去。
用免费的，但不是盗版的gcc，心安一点。

自己写的代码也贴出来了，分析工作结束了。
最关键一行是直接Copy的，那一行还要细细品味。
整个程序，就那一行代码最关键。

感谢祖国。
感谢大家的支持。感谢 GNU的gcc ，感谢Notepad++，感谢 LarryWall 的Perl。
感谢无私的人们与我们分享智慧的果实。

aubell

这个貌似同头文件的包含次序有关系，VC下的常见错误。
以下内容是Copy来的：

VC6中的解决方法：
菜单--〉项目--〉设置...，出现“项目设置”对话框，左边展开项目，在“源文件”中找到出错的文件，然后在右边选择“C/C++”属性页，在Category下拉框中选择“Precompiled Headers”，然后在下面选择“Not using precompiled headers”，重新编译一般就没问题了。