四柱汉诺塔升级版

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根柱移动的步数