关于魔方最少步数的问题

乌木

原帖由 乌木 于 2009-2-13 23:16 发表
何以见得？在建立态树时，原来Y那个位置（N＋1步的位置）已经被消同态了。但是在单独考查这原来Y位置的原父代X时，这X完全可以再次走一步而到达Y，不料此处是个“空号”，只好空欢喜一场，一下子跌到更低处了－－看看状态还是和Y一样，但是和X0的距离却小于N＋1了。

补充：用具体一些的例子来说吧。
0步态   X0 。
1步态 （用X0做一步动作的符号U、U' ……等等来表示1步态）U， U'， D， D'， L， L'， R， R'， F， F'， B， B'  ，共12个1步态。
2步态   每个1步态有11个后代（2步态），所以，刚才的12个1步态共有可能的2步态数目为12×11＝132个，但是这同一代内部要消去18个同态（比如UU＝U'U' ，UD＝DU，……等等）。故X0的2步态只有114个，分别是UU，UD， UD'  ……等等。
3步态    且看一个2步态UU，它再走一步U，得到3步态UUU，可是UUU＝U'，这个3步态UUU应该合并到同态U'，而U' 却是个1步态！！！

这最后一个例子说明问题了吧？！

注：X0不一定要用复原态，任何一个态出发，变化都是上述规律。但老祖宗X0取复原态的话，看起头几代来较简明直观。

xiaobao

看不明白，不懂呀！最小步很难不知道该如何学习。

骰迷

那麼X就是U2，Y既是N+1，又是N-1，這和我的意見沒有衝突。X和Y的步數必相差一，要不就是零。題目就是要證明一定不能是零。

乌木

嗯。这种时候，X走一步所得到的态Y，Y消同态和不消同态，在态树上的位置虽然不同，但两个位置的Y的步数和X的步数，两者之差的绝对值都是1。

这和“Y的步数不该算作（N＋1）而应该算作（N－1）”是两个问题，且这两个问题谈不上冲突的。

我举这个第四代的“UUU”合并为第二代的“U' ”的例子，只是表明我反对“Y不可能往下兼合”这种说法而已。

[ 本帖最后由 乌木 于 2009-2-14 20:10 编辑 ]

骰迷

看來我是表達錯誤了，Y只可能往上、平行和向下兩層兼合
X只可能往上、平行兼合
所以通常那些打亂魔方的程式都不是一步一步算的，因為動了單數步/雙數步都只能達到總狀態數一半的狀態，雖然還是很多，一輩子都玩不完，但還是較不公平一些
小籠包兄和樓主在＂最長例外列＂中的證明做得很好看，雖然沒全搞懂，希望他快點找到這裡吧，我可不會

骰迷

我可能找到了證明的門路。很像＂移動數字的問題＂裡的。
魔方擰一步R，角塊的循環節有一個，亦即有奇數個循環節。
擰兩步R2，角塊的循環節有兩個，亦即有偶數個循環節。
魔方擰一步，魔方的狀態就會從奇數轉為偶數，又或者從偶數轉為奇數。
X算是偶數狀態，要打亂再復原，中間必須經過偶數次的變換。
偶數－＞奇數－＞偶數－＞奇數－＞偶數
變換次數：四次（偶數）

乌木

1楼说：“……Y复原成X0的最少步数不是N-1步，就是N+1步。”
这大概指一般情况综合而言的吧？如果具体给定了一个Y态，它到X0的最少步数如果是N－1的话，就不再可能是N＋1；或者，是N＋1的话，就不可能是N－1 了。

任何一个态到X0的路线有无数条，但是最短路线只有一条。

所以，为了让态树上的各个态到达树根的路线最短，合并同态时应该往下（往接近树根的地方）合并，不能如有人说的什么往上合并。

否则，不单单影响它一个态，还连累它的一大批后代，都要花费非最少步数回到树根。

[ 本帖最后由 乌木 于 2009-2-14 20:09 编辑 ]

lulijie

我所知道的语文中，
    不是…就是…    这种 语句的意思是二者选一，    是指   N+1  或者 N-1 的意思，不是指 既是N+1 又是N-1。
不知兄台所学的语文中，该语句是什么意思。
是不是我的表达不当造成了兄台的误解。
还有，兄台中有句话   任何一个态到X0的路线有无数条，但是最短路线只有一条。
这句话意思是对的，但表达的不够准确。
按照兄台举的例子：从X0，经过R2旋转所成的状态X，它是2步态。最短路线不是只要1条，而是2条：RR和R‘R'。

骰迷

"任何一个态到X0的路线有无数条，但是最短路线只有一条。"
U2=U'2
UD=DU
(RUR'U')3=(URU'R')3
這一句是不對的吧。
不過＂不能如有人说的什么往上合并。＂這一句倒是對的，我忽略了＂最少步數＂這一節上。

骰迷

補充一下#36：棱塊、角塊和中心塊的色向、棱塊的位置都可以用偶數步的公式來還原（在角塊位置已還原的前提下），因此並未計在奇偶態的分辨裡。