有这么一类问题:

  1. n个状态S1,S2,…,Sn
  2. Move
    Si –> Sj成为Si Move到 Sj,即Si->Sj将Si转换到Sj
  3. 定义初始状态Start,和结果状态End
    Start可以是n状态中的任意一个
    End却只能是被指定的一个
  4. Distance
    S1转换为End要经过若干个Move,称为D1;
    S2转换为End要经过若干个Move,称为D2;
    如此类推

是否存在算法A,对于任意的Start,都能找到一系列Moves,能成功到达End?

对于某个算法A,它能给出D1…Dn

很显然,有很多这样的算法,A1,A2,…,Am,排成图表如下:

             D1  D2  D3 。。。Dn

A1

A2

An

对于每一列Di所对应的数值列,一定有个最小值,所以有n个最小值

God’s algorithm就是那个总是产生这n个最小值的算法

这m个最小值一定有个最大值,max【min】,God’s number就是这么一个值

这个值的下界在1981年被证明>=18,在1995年被证明>=20,在2010年被证明<=20,所以God’s number等于24.

 

魔方问题就是这么一个问题,魔方问题的God‘s Algorithm由http://www-compsci.swan.ac.uk/~csphil/CS335/korfrubik.pdf得到,魔方问题的God’s number被证明为是20

Advertisements