KeyTo9_Fans 发表于 2009-11-18 20:48:04

对于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)   decab
--------------------------------
2:       10   00001
3:       19   00001
4:       34   00112
5:       57   11223
6:       88   11223
7:      123   12334
8:      176   23445
9:      253   33556
10:      342   34567
11:      449   34667
12:      572   45778
13:      749   5778 10
14:      980   5789 11
15:   1261   689 10 12
16:   1560   689 10 12
17:   1903   79 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   97249793979398619930
100000: 211.64145799125 99344 99344 99562 99781

上述结果很可能不是最终结果,但可以作为最终结果的一个很好的上界。

因为当n>32时,很可能会有新的移动模式出现。

而当前的移动模式仅仅只是新的移动模式的一个特例。

新的移动模式会在当前的基础上新增若干个参数,把当前的移动模式更为一般化。

所以接下来的工作是尝试寻找新的移动模式,看看上述结果能不能继续优化。

如果找不到新的移动模式,则说明上述结果就是最终结果,对其加以证明就完美解决问题了。

KeyTo9_Fans 发表于 2010-4-15 16:48:43

上述结果已经写到“在线整数数列百科大全”上面去了。

数列编号为A160002。

http://www.research.att.com/~njas/sequences/A160002

这个数列是由我们首创的。

因为将移动步数作为关键字,在google上只搜得到我们的结果,搜不到别人的结果。

希望再接再厉,不断完善这个问题的研究工作。

#####

2017年5月24日更新:

原链接已失效,新的链接是

http://oeis.org/A160002

gxqcn 发表于 2010-4-15 20:03:37

恭喜恭喜。

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

guxd 发表于 2013-7-6 08:54:13

用递归编程不就行了么

王守恩 发表于 2020-2-3 17:10:55

本帖最后由 王守恩 于 2020-2-3 18:12 编辑

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 发表于 2020-2-6 21:40:05

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

一旦完 ...

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

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

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

王守恩 发表于 2020-2-9 09:43:10

本帖最后由 王守恩 于 2020-2-9 11:39 编辑

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




页: 1 2 3 4 5 [6]
查看完整版本: 四柱汉诺塔升级版