我倾向于使用半人工的方式搜索
首先根据假设得到首尾两个状态
然后指定中间状态，机器自动生成较好的生成序列
如果中间状态足够接近原始状态，则该生成序列应该唯一且最优化
这么作，可否逐渐得到次优化解
另外，我还有个猜测
对每个状态都有一个镜像状态
对n为奇数，则步骤数为奇数
则除中央状态外其他状态相对中央状态对称且成镜像
同样对n为偶数，也是
但没有中央状态
可以考虑这么一个问题，对于一个n个碟子的汉诺塔最优移动序列，如果我们从中删除所有对最小n-k个碟子的移动过程，而只保留最大k个碟子的移动过程，那么这个是不是一种k个碟子的最优移动过程呢？如果不是，是不是存在某个$n_0(k)$,使得对于一切$n>=n_0(k)$，都存在一种n个碟子的最优移动序列，使得对应最大k个碟子的移动过程都是相同的?
你这个问题的镜像也是个问题
应该是我说的问题的精确解释
因为从1到4和从4到1呈镜像关系
我觉得考虑最大的移动过程和考虑最小的移动过程
其结果应该正好相反
但其数量关系应该等价
做广度优先搜索时，扩展出来的新状态放在队列尾端。
而已经扩展过的状态是没有必要保留的，可以直接从队列头部清除，释放空间。
但为了防止走回头路，需要保留上一步扩展到的状态。
综上所述，扩展过程只需用三个数组：last[]，now[]，next[]。
逐一扫描now[]数组所记录的状态，把扩展出来的状态与last[]、now[]、next[]中的状态均比较一遍，如果是新的状态，则记录到next[]里。
扫描完毕后，把数组滚动一下，即 last = now，now = next，然后继续扫描now[]数组。
对n=16做这种推进式的扩展，高峰时每个数组存储的状态数为一千多万（为了方便查找重复状态，当然是以状态的哈希值作为下标），共占用200M左右的内存，还不至于动用硬盘空间。
这种推进式的扩展没有保留扩展路径，所以只能得到最佳步数，不能得到方案。
所幸的是，n<=16的情况都通过手工操作找到了最佳步数对应的一种可行方案。
我编了一个图形界面的操作平台，把这个问题作为一个小游戏来玩了，玩家通过鼠标操作来移动盘子。
一旦完成任务，系统会自动把你的操作步骤记录下来，存到record.txt里。
每次重开此游戏，系统都会读取record.txt，载入上次的进度。
record.txt里的内容是直接用便于阅读的格式规范的明文写的，可作为玩家之间交流学习的媒介。
操作说明：
鼠标左键点击盘子再点击位置可以移动盘子。
点击右方的数据可以选择关卡。
点击鼠标右键为撤销。
用鼠标左键点击盘子以外的地方为重做。
可以移动多个盘子。
在1、4柱之间移动则用到前面的数据。
在2、4或1、3柱之间移动则为(3^m-1)步，m为要移动盘子的个数。
做广度优先搜索时，扩展出来的新状态放在队列尾端。
而已经扩展过的状态是没有必要保留的，可以直接从队列头部清除，释放空间。
但为了防止走回头路，需要保留上一步扩展到的状态。
综上所述，扩展过程只需 ...
KeyTo9_Fans 发表于 2009-11-2 22:23 http://bbs.emath.ac.cn/images/common/back.gif
使用状态的hash值来保存，你能够保证不同状态之间不会出现冲突的hash值吗？不然会有问题的
不过如果只有1000多万个状态，使用hash表问题应该不大。n=16的每个状态32比特数据就可以保存。
当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
以上数据和方案均可通过之前发布的操作平台的验证。
如果有人在操作平台上玩出了更优解，请回贴告知。
不错，不过纯手工肯定是无法找到比你的更好的结果的:)