三、四柱汉诺塔问题
3、四塔问题：设有A，B，C，D四个柱子(有时称塔)，在A柱上有由小到大堆放的n个盘子，如图所示。
今将A柱上的盘子移动到D柱上去。可以利用B，C柱作为工作栈用，移动的规则如下:
①每次只能移动一个盘子。
②在移动的过程中，小盘子只能放到大盘子的上面。
设计并实现一个求解四塔问题的动态规划算法，并分析时间和空间复杂性。
■ 算法思想:
用如下算法移动盘子(记为FourPegsHanoi):
1)、将A柱上n个盘子划分为上下两部分，下方部分共有k(1≤k≤n)个盘子，上方部分共有n - k个盘子。
2)、将A柱上面部分n–k个盘子使用FourPegsHanoi算法经过C、D柱移至B柱。
3)、将A柱剩余的k个盘子使用ThreePegsHanoi算法经过C柱移至D柱。
4)、将B柱上的n–k个盘子使用FourPegsHanoi算法经过A、C柱移至D柱。
ThreePegsHanoi算法如下(设三个柱子分别为A、B、C，A柱上共有k个盘子):
1)、将A柱上方k-1个盘子使用ThreePegsHanoi算法经过B柱移至C柱。
2)、将C柱上最后一个盘子直接移至C盘。
3)、将B柱上k-1个盘子使用ThreePegsHanoi算法经过A柱移至C柱。
■ 算法步骤：
根据动态规划的四个步骤，求解如下:
1)、最优子结构性质:
四柱汉诺塔问题的最优解是用最少的移动次数将A柱上的盘子全部移到D柱上。当盘子总数为i时，我们不妨设使用FourPegsHanoi的最少移动次数为f(i)。相应的ThreePegsHanoi 算法移动次数为g(k)，由于g(k)=2g(k-1)+1=2k -1,当k确定时，g(k)也是不变的。
f(i)为最优解时，其子问题f(i-k)也必为最优解。如果f(i-k)不是最优解，那么存在f’(i-k) < f(i-k)。用f’(i-k)替换f(i-k)将产生一个比f(i)更优的解。这与f(i)为最优解是矛盾的。所以本问题具有最优子结构性质。
2)、递归地定义问题的最优解:
根据上述FourPegsHanoi算法得到最少移动次数f(i):
3)、自底向上地计算最优解的值:
(相应的Java源程序在Hanoi.java中。)
f(i)对应算法中的m[i ,
s[i]]。
-----------------------------------------------------------------------------------------
求四柱汉诺塔最小移动次数伪代码：
数组下标从0开始，数组m,s大小为n+1。数组m存储计算最小移动次数的中间值。数组s存储每步最小移动次数所对应的分割值k。
MinMovements ( n ):
m[0,0]
← s[0] ← 0 ▹为了方便计算增加了f(0) = m[0,s[0]] = 0
for
i ← 1 to n
do
min ← ∞
for
k ← 1 to i
do
m[i , k] ← 2 * m[i – k , s[i – k]] + 2k – 1
if
m[i , k] < min
then
min ← m[i , k]
s[i] = k
return
m[n , s[n]] & s
4)、根据计算信息构造最优解:
MinMovements求出的数组s中，s[i]是f(i)所对应的最优分割位置。根据数组s来构造移动盘子的最佳序列，伪代码如下:
-----------------------------------------------------------------------------------------
FourPegsHanoi (i , src, temp1, temp2, dest):
if i = 1
then
move(src , dest)
else FourPegsHanoi(i – s[i] ,
src , temp2 , dest , temp1)
ThreePegsHanoi(s[i] , src ,
temp2 , dest)
FourPegsHanoi(i – s[i] , temp1 , src , temp2 ,
dest)
----------------------------------------------------------------------------------------
ThreePegsHanoi(k , src , temp, dest):
if
k = 1
then
move(src , dest)
else ThreePegsHanoi(k - 1, src , dest ,
temp)
move(src
, dest)
ThreePegsHanoi(k
- 1, temp , src , dest)
-----------------------------------------------------------------------------------------
■
时间空间复杂度分析:
1、时间复杂度
MinMovements算法的时间复杂度为:
T(n) = 1 + 2 + ...
+ n = n(n+1)/2 = O(n2)
2、空间复杂度
MinMovements算法占用的空间为m 和 s数组的大小:
即 (n+1)2
+ (n+1) = O(n2)
通过分析m数组中记录了一些与结果不相关的数据,所以通过对MinMovements进行改进,可使占用空间减小为O(n)。
MinMovements ( n ):
m[0]
← s[0] ← 0
for
i ← 1 to n
do
m[i] ← ∞
for
k ← 1 to i
do
q ← 2 * m[i – k] + 2k – 1
if
q < m[i]
then
m[i] ← q
s[i] ← k
return
m[n] & s
■
算法测试
当n=10时，最小移动次数49。 移动序列如下:
|
1 A->D
2 A->B
3 A->C
4 B->C
5 D->C
6 A->B
7 A->D
8 B->D
9 A->B
|
10 D->A
11 D->B
12 A->B
13 C->A
14 C->D
15 C->B
16 D->B
17 A->B
18 A->C
19 A->D
|
20 C->D
21 A->C
22 D->A
23 D->C
24 A->C
25 A->D
26 C->D
27 C->A
28 D->A
29 C->D
|
30 A->C
31 A->D
32 C->D
33 B->C
34 B->D
35 B->A
36 D->A
37 C->A
38 B->D
39 B->C
|
40 D->C
41 B->D
42 C->B
43 C->D
44 B->D
45 A->B
46 A->C
47 A->D
48 C->D
49 B->D
|
当n=15时，最小移动次数129。移动序列如下:
|
1 A->B
2 A->C
3 A->D
4 C->D
5 B->D
6 A->C
7 A->B
8 C->B
9 A->C
10 B->A
11 B->C
12 A->C
13 D->A
14 D->B
15 D->C
16 B->C
17 A->C
18 A->D
19 A->B
20 D->B
21 A->D
22 B->A
23 B->D
24 A->D
25 A->B
26 D->B
|
27 D->A
28 B->A
29 D->B
30 A->D
31 A->B
32 D->B
33 C->D
34 C->B
35 C->A
36 B->A
37 D->A
38 C->B
39 C->D
40 B->D
41 C->B
42 D->C
43 D->B
44 C->B
45 A->C
46 A->D
47 A->B
48 D->B
49 C->B
50 A->D
51 A->C
52 D->C
|
53 A->D
54 C->A
55 C->D
56 A->D
57 A->C
58 D->C
59 D->A
60 C->A
61 D->C
62 A->D
63 A->C
64 D->C
65 A->D
66 C->A
67 C->D
68 A->D
69 C->A
70 D->C
71 D->A
72 C->A
73 C->D
74 A->D
75 A->C
76 D->C
77 A->D
78 C->A
|
79 C->D
80 A->D
81 B->D
82 B->A
83 B->C
84 A->C
85 D->C
86 B->A
87 B->D
88 A->D
89 B->A
90 D->B
91 D->A
92 B->A
93 C->B
94 C->D
95 C->A
96 D->A
97 B->A
98 B->C
99 B->D
100C->D
101B->C
102D->B
103D->C
104B->C
|
105 B->D
106 C->D
107 C->B
108 D->B
109 C->D
110 B->C
111
B->D
112 C->D
113 A->C
114 A->D
115 A->B
116 D->B
117
C->B
118
A->D
119 A->C
120 D->C
121 A->D
122 C->A
123 C->D
124 A->D
125 B->A
126 B->C
127 B->D
128 C->D
129 A->D
|
文章来源:
http://wintys.blog.51cto.com/425414/100703
[附件]:
四柱汉诺塔.zip
posted on 2009-03-18 12:02
天堂露珠 阅读(1165)
评论(0) 编辑 收藏 所属分类:
Algorithm