[导入][原]算法设计与分析3 - 动态规划解决四柱汉诺塔问题 - 露水阑珊

wintys

浏览: 196466 次
性别:
来自: 芜湖

最近访客更多访客>>

qq849397558

zb872676223

majianshe

csmyp

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

[导入][原]算法设计与分析3 - 动态规划解决四柱汉诺塔问题

博客分类：

Algorithm

算法 C C++C#F#

三、四柱汉诺塔问题

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= 2^k -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]] + 2^k – 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(n² )

2 、空间复杂度

MinMovements 算法占用的空间为 m 和 s 数组的大小 :

即 (n+1)² + (n+1) = O(n² )

通过分析 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] + 2^k – 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
[附件]:

算法的Java实现.zip (185.4 KB)
下载次数: 0

分享到：

[原]使用Ant实现zip压缩解压功能 | [原]导出CodeHelp的数据

2009-03-18 12:02
浏览 1140
评论(0)
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

[导入][原]算法设计与分析3 - 动态规划解决四柱汉诺塔问题

评论

发表评论

相关推荐

最近访客 更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

[导入][原]算法设计与分析3 - 动态规划解决四柱汉诺塔问题

评论

发表评论

相关推荐

[导入][原]算法设计与分析1 - 主元素

[导入][原]算法设计与分析2 - 嵌套箱问题

[导入]快速查找中位数 - 基于ANSI C的实现

最近访客更多访客>>