四柱汉诺塔升级版

无心人

我倾向于使用半人工的方式搜索
首先根据假设得到首尾两个状态

然后指定中间状态，机器自动生成较好的生成序列
如果中间状态足够接近原始状态，则该生成序列应该唯一且最优化

这么作，可否逐渐得到次优化解

无心人

另外，我还有个猜测

对每个状态都有一个镜像状态
对n为奇数，则步骤数为奇数
则除中央状态外其他状态相对中央状态对称且成镜像

同样对n为偶数，也是
但没有中央状态

mathe

可以考虑这么一个问题，对于一个n个碟子的汉诺塔最优移动序列，如果我们从中删除所有对最小n-k个碟子的移动过程，而只保留最大k个碟子的移动过程，那么这个是不是一种k个碟子的最优移动过程呢？如果不是，是不是存在某个$n_0(k)$,使得对于一切$n>=n_0(k)$，都存在一种n个碟子的最优移动序列，使得对应最大k个碟子的移动过程都是相同的?

无心人

你这个问题的镜像也是个问题

应该是我说的问题的精确解释

因为从1到4和从4到1呈镜像关系
我觉得考虑最大的移动过程和考虑最小的移动过程
其结果应该正好相反
但其数量关系应该等价

KeyTo9_Fans

做广度优先搜索时，扩展出来的新状态放在队列尾端。

而已经扩展过的状态是没有必要保留的，可以直接从队列头部清除，释放空间。

但为了防止走回头路，需要保留上一步扩展到的状态。

综上所述，扩展过程只需用三个数组：last[]，now[]，next[]。

逐一扫描now[]数组所记录的状态，把扩展出来的状态与last[]、now[]、next[]中的状态均比较一遍，如果是新的状态，则记录到next[]里。

扫描完毕后，把数组滚动一下，即 last = now，now = next，然后继续扫描now[]数组。

对n=16做这种推进式的扩展，高峰时每个数组存储的状态数为一千多万（为了方便查找重复状态，当然是以状态的哈希值作为下标），共占用200M左右的内存，还不至于动用硬盘空间。

这种推进式的扩展没有保留扩展路径，所以只能得到最佳步数，不能得到方案。

所幸的是，n<=16的情况都通过手工操作找到了最佳步数对应的一种可行方案。

KeyTo9_Fans

我编了一个图形界面的操作平台，把这个问题作为一个小游戏来玩了，玩家通过鼠标操作来移动盘子。

一旦完成任务，系统会自动把你的操作步骤记录下来，存到record.txt里。

每次重开此游戏，系统都会读取record.txt，载入上次的进度。

record.txt里的内容是直接用便于阅读的格式规范的明文写的，可作为玩家之间交流学习的媒介。

操作说明：

鼠标左键点击盘子再点击位置可以移动盘子。

点击右方的数据可以选择关卡。

点击鼠标右键为撤销。

用鼠标左键点击盘子以外的地方为重做。

可以移动多个盘子。

在1、4柱之间移动则用到前面的数据。

在2、4或1、3柱之间移动则为(3^m-1)步，m为要移动盘子的个数。

h4.rar (548.02 KB, 下载次数: 16)

2020-1-27 02:29 上传

点击文件名下载附件

mathe

做广度优先搜索时，扩展出来的新状态放在队列尾端。

而已经扩展过的状态是没有必要保留的，可以直接从队列头部清除，释放空间。

但为了防止走回头路，需要保留上一步扩展到的状态。

综上所述，扩展过程只需 ...
KeyTo9_Fans 发表于 2009-11-2 22:23

使用状态的hash值来保存，你能够保证不同状态之间不会出现冲突的hash值吗？不然会有问题的

mathe

不过如果只有1000多万个状态，使用hash表问题应该不大。n=16的每个状态32比特数据就可以保存。

KeyTo9_Fans

当16<n<29时，捆绑前(n-13)个盘子，即把最小的几个盘子作为一个整体。

这个整体直接在1柱和4柱上移动，移动1次的代价为f(k)，k为这个整体的盘子数，f是前面已经算好的数据。

例如，n=17时，捆绑1~4盘，作为一个整体，移动代价为f(4)=34。

这样就相当于只有14个盘子了，状态数为4^14，是可以全部存下来的。

由于捆绑了4个盘子，而f(5)、f(6)、……的移动无法仅用f(4)来表示，所以移动规则要相应地修改。

除了把一个盘子移到相邻的柱子之外，还要考虑1次性把多个盘子从1柱移到4柱或移回来。

即f(4)到f(16)的移动均可直接进行。

这样，问题就变成了在含有4^14个顶点、标有长度的边的无向图中找最短路径。

由于这个图的边是有规律且很稀疏的，所以即使顶点数高达4^14，找最短路径也不成问题。

如果捆绑前(n-13)个盘子不会造成结果不优，那么1盘到28盘的移动步数分别为：

1:     3
2:    10
3:    19
4:    34
5:    57
6:    88
7:   123
8:   176
9:   253
10:   342
11:   449
12:   572
13:   749
14:   980
15:  1261
16:  1560
17:  1903
18:  2328
19:  2889
20:  3562
21:  4377
22:  5276
23:  6251
24:  7392
25:  8779
26: 10488
27: 12469
28: 14832

当n>28时，捆绑前(n-13)个盘子会造成结果不优，于是停止寻找最短路径，手工往下推导。

仿照前28个盘子的移动方案，以相同的方式移动29盘至32盘，结果为：

29: 17497
30: 20228
31: 23377
32: 27082

以上数据和方案均可通过之前发布的操作平台的验证。

如果有人在操作平台上玩出了更优解，请回贴告知。

mathe

不错，不过纯手工肯定是无法找到比你的更好的结果的