魔方与马可夫过程

noski

<P>马可夫过程是随机过程的一种，它的特点是：一个状态序列，N+1时的状态只与N时刻有关，而与N-1时刻无关。</P>
<P>而魔方的转动就是一个马可夫过程，因为第N+1步转出什么状态，完全由第N步的结果决定，而与之前是什么样的无关。</P>
<P>而其中一个令人感兴趣的定义就是“首达时间”，既可以由各种路径从状态i 变化到状态j ，首达时间为其中最短的一条的长度，顾名思义，首次到达。</P>
<P>&nbsp;</P>
<P>&nbsp;</P>
<P>现在马可夫过程已经有许多理论成果，网上也搜得到，不知是否对魔方的理论有所帮助。</P>
<P>但还有一些问题，马可夫过程理论偏向于概率方面的研究，如果魔方的每次转动都是随机的，似乎更适合一点。</P>
<P>而像首达时间，或者说首达步数，比如从状态A到状态B的首达步数为N的充要条件为N-1步不能从A走到B，似乎又落到穷举的陷阱里了。。</P>
<P>&nbsp;</P>
<P>&nbsp;</P>
<P>&nbsp;</P>

pengw

言之有理，以前构造的三阶最短路径树，也可解释为马可夫过程，但树本身是一个穷举结构。

pengw

<P>言之有理，以前构造的三阶最短路径树，也可解释为马可夫过程，但树本身是一个穷举结构。对最简单的二阶魔方，也可以称簇魔方，单簇构成，这样一个魔方，面对的穷举是百万数量级（已消同态），计算方面是可以授受的，而对一个无色向簇的穷举是23！（已消同态），几乎跟三阶状态数是一个数量级！我以前的思路是，簇状态用穷举，魔方状态用协调，这样可以从根本上除去成指数的增长问题，但协调算法设计也是不易之事。</P>
<P>我觉得从簇层面走算法而不是穷举，情况可能要好一点，但至今没有看到令人信服的算法，除了听到一些莫名其妙的描述，如什么48状态！</P>

[ 本帖最后由 pengw 于 2008-3-7 09:16 编辑 ]