四柱汉诺塔升级版

无心人

我倾向于使用半人工的方式搜索 首先根据假设得到首尾两个状态 然后指定中间状态，机器自动生成较好的生成序列 如果中间状态足够接近原始状态，则该生成序列应该唯一且最优化 这么作，可否逐渐得到次优化解

无心人

另外，我还有个猜测 对每个状态都有一个镜像状态 对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

当1628时，捆绑前(n-13)个盘子会造成结果不优，于是停止寻找最短路径，手工往下推导。 仿照前28个盘子的移动方案，以相同的方式移动29盘至32盘，结果为： 29: 17497 30: 20228 31: 23377 32: 27082 以上数据和方案均可通过之前发布的操作平台的验证。 如果有人在操作平台上玩出了更优解，请回贴告知。

mathe

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