四柱汉诺塔升级版

mathe

贴吧中不知道谁发了帖子说我们这里有n=5的结果了，所以我只好写了个程序将$n<=13$的结果都给算出来了。不过用这个程序，已经很难解决规模再大一些的问题了，即使使用外存储器（硬盘），花上冗长的时间，用这个算法估计也就能再稍微提高几步。
所以关于更加大的n就不能用这种枚举所有情况的方法解决了
当然，关于更加大的n，考虑到最优解很难计算，给出一个比较好的结果也是可以接受的

无心人

n=14，15需要多少内存？

mathe

如果通过使用外存和比特位,应该能够计算到n=16.而且如果不要求将步骤给出来,使用1G内存可以计算出n=16的情况,而如果要求把步骤给出来,对于n=16的时候,需要512M*K的硬盘空间.其中K为步骤数目.

无心人

太大阿
n=16
估计在2000附近

无心人

能不能用时间换空间阿

即使用10倍时间也可以考虑
只要使用状态保存
我想我服务器用32M内内存和100M硬盘
计算30天也是可以考虑的吧

mathe

32M内存,100M硬盘太小了,硬盘只有100M???

mathe

内存小相对来说还好,因为还可以使用虚拟内存(操作系统自动管理),只是速度会慢很多.
可是硬盘太小就不好办了.
这个问题如果n=14,内存32M可以了(但是要稍微大于32M),n=15需要128M的内存,n=16需要512M的内存
而对于外存的需求,可以由B*K(其中B是内存的要求,K为步数)降低为B*(K/S+S),其中S是用户可选的一个参数,当然这时计算时间要翻倍(所有数据要计算两次,正逆各一次)

无心人

不是多的很
但不能都拿来算题阿
否则容易丢服务器上数据阿

你认为如果缩减下
能精简到多少？
内存可以适当大些
硬盘不要太大
硬盘大了不可靠

无心人

我看你结果，越到后面
相同的越多
能否利用呢？
从一个确定的状态推
比如n=14，大概在1000
首尾各确定200步
双向推能多大概率找到最优化？

mathe

按上面估计数字,大概20G硬盘空间可以拿下n=16.不过512M内存空间估计要求有点高.
其实如果要计算,拿服务器还不是拿普通台式机去计算.程序是可以分步计算的,每计算一步结果保存在硬盘上,下一次重新启动时可以将硬盘上最近一次结果读出继续开始就可以了.而且如果你担心硬盘不可靠,可以同时在两台台式机上运行相同内容.