四柱汉诺塔升级版

KeyTo9_Fans

对于n≤32的情况，最优的移动方案可以归纳为如下图所示的移动模式。 但n=0、n=1、n=3和n=6例外，需要特殊处理。 令f(0)=0，f(1)=3，f(3)=19，f(6)=88， 然后利用f(0)到f(n)的结果，枚举a,b,c,d,e的值，就可以求得f(n+1)。 这样求f(n)的时间复杂度为O(n^6)。 f(2)到f(100)的结果如下： n f(n) d e c a b -------------------------------- 2: 10 0 0 0 0 1 3: 19 0 0 0 0 1 4: 34 0 0 1 1 2 5: 57 1 1 2 2 3 6: 88 1 1 2 2 3 7: 123 1 2 3 3 4 8: 176 2 3 4 4 5 9: 253 3 3 5 5 6 10: 342 3 4 5 6 7 11: 449 3 4 6 6 7 12: 572 4 5 7 7 8 13: 749 5 7 7 8 10 14: 980 5 7 8 9 11 15: 1261 6 8 9 10 12 16: 1560 6 8 9 10 12 17: 1903 7 9 10 11 13 18: 2328 8 10 11 12 14 19: 2889 9 11 12 13 15 20: 3562 10 12 12 14 17 21: 4377 10 13 13 15 18 22: 5276 10 13 13 15 18 23: 6251 11 14 14 16 19 24: 7392 12 14 16 17 19 25: 8779 13 16 16 18 21 26: 10488 14 17 17 19 22 27: 12469 14 17 18 20 23 28: 14832 15 18 19 21 24 29: 17497 15 18 19 21 24 30: 20228 16 19 20 22 25 31: 23377 17 20 21 23 26 32: 27082 18 21 22 24 27 33: 31465 19 22 23 25 28 34: 36636 20 23 24 26 29 35: 42581 20 24 24 27 31 36: 49348 21 25 25 28 32 37: 57157 22 25 26 28 32 38: 65222 22 26 26 29 33 39: 73865 23 27 27 30 34 40: 84022 24 28 28 31 35 41: 95757 25 28 30 32 35 42: 109094 26 30 30 33 37 43: 124525 27 31 31 34 38 44: 142220 27 31 32 35 39 45: 161801 28 32 33 36 40 46: 184494 29 33 34 37 41 47: 208359 30 34 34 37 42 48: 233220 30 34 35 38 42 49: 260873 31 35 36 39 43 50: 293016 32 36 37 40 44 51: 329391 33 37 38 41 45 52: 369778 34 38 39 42 46 53: 415899 35 39 40 43 47 54: 468000 35 40 40 44 49 55: 524585 36 41 41 45 50 56: 589570 37 42 42 46 51 57: 660389 38 42 43 46 51 58: 732678 38 43 43 47 52 59: 810215 39 44 44 48 53 60: 897344 40 45 45 49 54 61: 998343 41 46 46 50 55 62: 1109122 42 47 47 51 56 63: 1230093 43 48 48 52 57 64: 1366910 44 49 49 53 58 65: 1522459 45 50 50 54 59 66: 1687510 45 50 51 55 60 67: 1874643 46 51 52 56 61 68: 2079700 47 52 53 57 62 69: 2294287 48 53 53 57 63 70: 2516366 48 53 54 58 63 71: 2757895 49 54 55 59 64 72: 3030880 50 55 56 60 65 73: 3340433 51 56 57 61 66 74: 3675094 52 57 58 62 67 75: 4038133 53 58 59 63 68 76: 4443818 54 59 60 64 69 77: 4898969 55 60 60 65 71 78: 5384602 55 61 61 66 72 79: 5923263 56 62 62 67 73 80: 6511900 57 63 63 68 74 81: 7144699 58 64 64 69 75 82: 7793996 58 64 64 69 75 83: 8482247 59 65 65 70 76 84: 9228136 60 66 66 71 77 85: 10077385 61 67 67 72 78 86: 11018610 62 68 68 73 79 87: 12024387 63 69 69 74 80 88: 13105218 64 70 70 75 81 89: 14305059 65 71 71 76 82 90: 15636282 66 72 72 77 83 91: 17081249 66 72 73 78 84 92: 18638390 67 73 74 79 85 93: 20334841 68 74 75 80 86 94: 22165538 69 75 76 81 87 95: 24079237 70 76 76 81 88 96: 26068688 70 76 77 82 88 97: 28180781 71 77 78 83 89 98: 30496934 72 78 79 84 90 99: 33092587 73 79 80 85 91 100: 35924570 74 80 81 86 92 其中，n≤32的结果与之前做出来的结果完全吻合。 从表中可以看出五个参数均有良好的单调性和平滑性。 利用a,b,c,d,e的单调性和平滑性，可将时间复杂度优化为O(n)。 优化后可以计算很大的n，用来观察数据的增长趋势。 计算到n=100000，结果如下： n log(f(n)) d e c a b -------------------------------------------------- 10: 2.534026 3 4 5 6 7 100: 7.555392 74 80 81 86 92 1000: 22.358183 914 935 936 956 977 10000: 68.093119 9724 9793 9793 9861 9930 100000: 211.641457 99125 99344 99344 99562 99781 上述结果很可能不是最终结果，但可以作为最终结果的一个很好的上界。 因为当n>32时，很可能会有新的移动模式出现。 而当前的移动模式仅仅只是新的移动模式的一个特例。 新的移动模式会在当前的基础上新增若干个参数，把当前的移动模式更为一般化。 所以接下来的工作是尝试寻找新的移动模式，看看上述结果能不能继续优化。 如果找不到新的移动模式，则说明上述结果就是最终结果，对其加以证明就完美解决问题了。

KeyTo9_Fans

上述结果已经写到“在线整数数列百科大全”上面去了。 数列编号为A160002。 http://www.research.att.com/~njas/sequences/A160002 这个数列是由我们首创的。 因为将移动步数作为关键字，在google上只搜得到我们的结果，搜不到别人的结果。 希望再接再厉，不断完善这个问题的研究工作。 ##### 2017年5月24日更新： 原链接已失效，新的链接是 http://oeis.org/A160002

gxqcn

恭喜恭喜。 本论坛网友已贡献了多条记录，它们都不容易得到，需要数学和计算机都要比较厉害，结合起来才能获得。

guxd

用递归编程不就行了么

王守恩

KeyTo9_Fans 发表于 2009-11-18 20:48
对于n≤32的情况，最优的移动方案可以归纳为如下图所示的移动模式。

四柱汉诺塔升级版问题
有四个排成一行的柱子和n个大小不同的盘子，
每次可以将一个盘子移动到相邻的柱子上，但是大盘子不能放在小盘子上面。
请用最小的步数将n个盘子从第一个柱子全部移到第4个柱子
a(n)= 3, 10, 19, 34, 57, 88, 123, 176, 253, 342, 449, 572, 749

n=03，019-3=03+02+2+01+03+2+03
n=04，034-3=03+08+2+03+01+2+02+10
n=05，057-3=10+08+2+10+01+2+02+19
n=06，088-3=19+08+8+04+19+8+19
n=07，123-3=19+26+2+19+04+8+08+34
n=08，176-3=34+26+2+34+04+8+08+57
n=09，253-3=57+26+2+57+04+8+08+88
n=10，348-3=57+80+8+57+04+8+08+123

每串数从左往右是一种移法，从右往左是另一种移法，

上面算式中的数字说明如下
003=利用4根柱移动1个盘所需的步数
010=利用4根柱移动2个盘所需的步数
019=利用4根柱移动3个盘所需的步数
034=利用4根柱移动4个盘所需的步数
057=利用4根柱移动5个盘所需的步数
088=利用4根柱移动6个盘所需的步数
123=利用4根柱移动7个盘所需的步数

02=利用3根柱移动1个盘所需的步数
08=利用3根柱移动2个盘所需的步数
26=利用3根柱移动3个盘所需的步数
80=利用3根柱移动4个盘所需的步数

1=利用3根柱移动1个盘(1个柱位)所需的步数
4=利用3根柱移动2个盘(1个柱位)所需的步数

我把我的算法晒在这里，大家看看，错在哪里了？
大家能补充一点资料吗？谢谢！
譬如：n=10,11,12 用字母 A,B,C,c,b,a 表示的移动方案。

dlpg070

KeyTo9_Fans 发表于 2009-11-2 22:27
我编了一个图形界面的操作平台，把这个问题作为一个小游戏来玩了，玩家通过鼠标操作来移动盘子。

一旦完 ...

刚刚下载，很好玩
要完成全部n的最小步数方案有点耗时，能否提供record.txt ?

KeyTo9_Fans

dlpg070 发表于 2020-2-6 21:40
刚刚下载，很好玩
要完成全部n的最小步数方案有点耗时，能否提供record.txt ?

record.zip (5.11 KB, 下载次数: 5)

2020-2-7 00:01 上传

点击文件名下载附件

王守恩

KeyTo9_Fans 发表于 2020-2-7 00:02

整理一下。
n=01，0000+000+0000+000+0000+0000+0000+0000+0000+3=3
n=02，0000+000+0000+000+0000+0002+0000+0005+0000+3=10
n=03，0003+000+0000+000+0000+0002+0003+0005+0003+3=19
n=04，0003+000+0000+000+0000+0010+0003+0005+0010+3=34
n=05，0010+000+0000+000+0000+0010+0010+0005+0019+3=57
n=06，0019+000+0000+000+0000+0008+0019+0020+0019+3=88
n=07，0019+000+0000+000+0000+0028+0019+0020+0034+3=123
n=08，0034+000+0000+000+0000+0028+0034+0020+0057+3=176
n=09，0057+000+0000+000+0000+0028+0057+0020+0088+3=253
n=10，0034+019+0019+011+0019+0064+0057+0028+0088+3=342
n=11，0088+000+0000+000+0000+0082+0088+0065+0123+3=449
n=12，0123+000+0000+000+0000+0082+0123+0065+0176+3=572
n=13，0123+023+0057+035+0057+0064+0123+0088+0176+3=749
n=14，0123+070+0057+089+0057+0064+0176+0088+0253+3=980
n=15，0176+070+0088+089+0088+0064+0253+0088+0342+3=1261
n=16，0176+070+0088+089+0088+0201+0253+0250+0342+3=1560
n=17，0253+070+0123+089+0123+0201+0342+0250+0449+3=1903
n=18，0342+070+0176+089+0176+0201+0449+0250+0572+3=2328
n=19，0449+070+0253+089+0253+0201+0572+0250+0749+3=2889
n=20，0572+089+0342+198+0342+0196+0572+0268+0980+3=3562
n=21，0749+198+0342+269+0342+0196+0749+0268+1261+3=4377
n=22，0749+198+0342+269+0342+0609+0749+0754+1261+3=5276
n=23，0980+198+0449+269+0449+0609+0980+0754+1560+3=6251
n=24，0980+211+0572+251+0572+0604+1560+0736+1903+3=7392
n=25，1560+198+0749+269+0749+0609+1560+0754+2328+3=8779
n=26，1903+198+0980+269+0980+0609+1903+0754+2889+3=10488
n=27，1903+595+0980+755+0980+0609+2328+0754+3562+3=12469
n=28，2328+595+1261+755+1261+0609+2889+0754+4377+3=14832
n=29，2328+595+1261+755+1261+1816+2889+2212+4377+3=17497
n=30，2889+595+1560+755+1560+1816+3562+2212+5276+3=20228
n=31，3562+595+1903+755+1903+1816+4377+2212+6251+3=23377
n=32，4377+595+2328+755+2328+1816+5276+2212+7392+3=27082

每种移法用10个数表示
我们约定第1个数不大于第9个数
第10个数(3)表示最大盘移动的步数
第2,4,6,8个数表示利用3根柱移动的步数
第1,3,5,7,9个数表示利用4根柱移动的步数