论坛 › 算法交流 › 跳蚱蜢

aimisiyou 发表于 2020-8-9 08:43:48

跳蚱蜢

题目如图。除了用BFS求解，还有没有其他数学分析方法？

aimisiyou 发表于 2020-8-9 08:55:36

本帖最后由 aimisiyou 于 2020-8-9 09:03 编辑

根据对称性，初步感觉先以最少步数达到6、5、4、3，此时上半圆就固定不变，后续就以最少步数调整下半圆，最终达到目标状态。

hujunhua 发表于 2020-8-9 18:44:47

最后状态记为{2,1,7,8,0}, 要到达{7,8,0,1,2}, 计算搜索需要11步。
{{2, 1, 7, 8, 0}, {2, 1, 7, 0, 8}, {2, 1, 0, 7, 8}, {2, 0, 1, 7, 8}, {2, 7, 1, 0, 8}, {2, 7, 1, 8, 0}, {2, 7, 0, 8, 1}, {0, 7, 2, 8, 1}, {7, 0, 2, 8, 1}, {7, 8, 2, 0, 1}, {7, 8, 2, 1, 0}, {7, 8, 0, 1, 2}}
计算搜索，从{3,4,5,6,0}到{6,5,4,3,0}确实需要上图所示的10步。

所以，现在得到了最少步数的一个上界：22步。

aimisiyou 发表于 2020-8-9 18:56:41

本帖最后由 aimisiyou 于 2020-8-9 19:04 编辑

hujunhua 发表于 2020-8-9 18:44
最后状态记为{2,1,7,8,0}, 要到达{7,8,0,1,2}, 计算搜索需要11步。
{{2, 1, 7, 8, 0}, {2, 1, 7, 0, 8}, { ...

但是，网上用BFS求的结果是20次（没有具体过程）。除非6、5、4、3还有更少步数达到。

mathe 发表于 2020-8-9 19:42:44

的确是20，有444种不同的解法
比如:
{ 0 1 2 3 4 5 6 7 8 }=>
{ 7 1 2 3 4 5 6 0 8 }=>
{ 7 1 2 3 4 0 6 5 8 }=>
{ 7 1 2 3 4 6 0 5 8 }=>
{ 7 1 2 3 0 6 4 5 8 }=>
{ 7 1 0 3 2 6 4 5 8 }=>
{ 0 1 7 3 2 6 4 5 8 }=>
{ 1 0 7 3 2 6 4 5 8 }=>
{ 1 8 7 3 2 6 4 5 0 }=>
{ 1 8 7 3 2 6 0 5 4 }=>
{ 1 8 7 3 0 6 2 5 4 }=>
{ 1 8 7 0 3 6 2 5 4 }=>
{ 1 8 7 6 3 0 2 5 4 }=>
{ 1 8 7 6 3 5 2 0 4 }=>
{ 1 8 7 6 3 5 2 4 0 }=>
{ 1 8 7 6 3 5 0 4 2 }=>
{ 1 8 7 6 0 5 3 4 2 }=>
{ 1 8 7 6 5 0 3 4 2 }=>
{ 1 8 7 6 5 4 3 0 2 }=>
{ 1 8 7 6 5 4 3 2 0 }=>
{ 0 8 7 6 5 4 3 2 1 }
另外计算结果表明最多20步可以到达任意状态。

aimisiyou 发表于 2020-8-9 19:51:25

mathe 发表于 2020-8-9 19:42
的确是20，有444种不同的解法
比如:
{ 0 1 2 3 4 5 6 7 8 }=>


魔方数？

hujunhua 发表于 2020-8-9 20:00:56

但是，改变一下策略，搜索到了更少步数的路径。
在2#的第1步到达第2图之后，保持{1,7,8}不动，将{2,3,4,5,6,0}调序为{0,6,5,4,3,2}，搜索到最短路径为15步：
{{2, 3, 4, 5, 6, 0},
{2, 3, 4, 5, 0, 6},
{2, 3, 0, 5, 4, 6},
{0, 3, 2, 5, 4, 6},
{3, 0, 2, 5, 4, 6},
{3, 5, 2, 0, 4, 6},
{3, 5, 2, 6, 4, 0},
{3, 5, 2, 6, 0, 4},
{3, 5, 0, 6, 2, 4},
{0, 5, 3, 6, 2, 4},
{5, 0, 3, 6, 2, 4},
{5, 6, 3, 0, 2, 4},
{5, 6, 3, 4, 2, 0},
{5, 6, 3, 4, 0, 2},
{5, 6, 0, 4, 3, 2},
{0, 6, 5, 4, 3, 2}}
剩下部分，保持{2,3,4,5,6}不动，将{0,1,7,8}调序为{7,8,0,1}，搜索最短路径为4步：
{{0, 1, 7, 8},
{7, 1, 0, 8},
{7, 0, 1, 8},
{7, 8, 1, 0},
{7, 8, 0, 1}}
最后，合起来为1+15+4=20步。

hujunhua 发表于 2020-8-9 20:20:01

貌似 M12 的 FindShortestPath[] 函数只给找一条路径。

上面的策略虽然达到20步了，但不足以证明最短。然而不分区段地搜索，我的程序怕是不行。

aimisiyou 发表于 2020-8-9 20:36:15

若是将8增加到20呢？BFS还能跑动吗？有没有类似魔方公式，大大减少步数？

王守恩 发表于 2020-8-26 14:53:01

蚱蜢只数：2，3，4，5， 6，7， 8
跳跃次数：3，3，6，6，11，15，20
9，10，...，再来几个？

我们对空盘子的移动作个记录, 形成状态关联图（每个状态当一个点）
2只蚱蜢时，一共3!=6个状态，空盘子的移动有2个变换，故关联图为一个六边形。这是基本圈。
3只蚱蜢时，一共4!=24个状态，空盘子的移动有3个变换：
A：前进1步
B：后退1步
C：前进2步（后退2步）
开环跳跃的关联图为一个六棱柱，2度点和3度点各12个。
闭环跳跃的关联图在六棱柱的基础上2度变3度点，多了6条边，已不是平面图了。
闭环关联图显然可以嵌入到一个轮胎面上，要是能画出来就有点意思了。


4只蚱蜢时，一共5!=120个状态，空盘子的移动有4个变换：
A：前进1步
B：后退1步
C：前进2步
D：后退2步
关联图就很复杂，不便展示了。

查看完整版本: 跳蚱蜢