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

wintys

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

最近访客更多访客>>

qq849397558

zb872676223

majianshe

csmyp

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

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

博客分类：

Algorithm

算法嵌入式 J#F#XML

二、嵌套箱问题

2、一个d 维箱(x₁,x₂,...,x_n)嵌入另一个d 维箱(y₁,y₂,...,y_n)是指存在1,2,…,d 的一个排列π，使得x_π(1)<y₁ ,x_π(2) <y₂, ... , x_π(d)<y_d 。

1) 证明上述箱嵌套关系具有传递性；

2) 试设计并实现一个贪心算法，用于确定一个d维箱是否可嵌入另一个d维箱；

3) 给定由n 个d 维箱组成的集合{ B₁,B₂,B₃,...,Bn}，试设计并实现一个贪心算法找出这n 个d维箱中的一个最长嵌套箱序列，并用n和d 描述算法的计算时间复杂性。

1) 箱嵌套关系的传递性

证明：

设有3个d维箱B₁(x₁ , x₂ , ．．． , x_d)，B₂ (y₁ , y₂ , ．．．, y_d)，B₃(z₁ , z₂ , ．．．, z_d)，B₁可嵌入B₂，B₂可嵌入B₃。

B₁可嵌入B₂，则存在排列π使得：

x_π(1)< y₁，x_π(2)< y₂，．．．，x_π(d)< y_d ——1

B₂可嵌入B₃，则存在排列θ使得：

y_θ(1)< z₁，y_θ(2)< z₂，．．．，y_θ(d)< z_d ——2

由1式可得：

x_θ(π(1))< y_θ(1)，x_θ(π(2))< y_θ(2)，．．．，x_θ(π(d))< y_θ(d)——3

由23可得：存在排列λ = θπ使得：

x_λ(1)< z₁，x_λ(2)< z₂，．．．，x_λ(d)< z_d

根据d维箱的定义可得，B₁可嵌入B₃。因此，嵌套箱关系具有传递性。

2) d维箱的嵌套关系

■ 贪心选择性质:

对于d维箱X(x₁ , x₂ , ．．． , x_d),Y (y₁ , y₂ , ．．．, y_d),排列 π、θ是分别使X、Y非递减有序的排列，有如下结论:X→Y(表示X可嵌入Y)的充要条件是，对任意1≤i≤d有x_π(i) < y_θ(i)。

证明:

a.充分性:

当对任意1≤i≤d有x_π(i) < y_θ(i)时，令λ = πθ^-1,那么

x_λ(i)= x_π(θ^-1_(i)) < y_θ(θ^-1_(i)) = y_i_，即存在一个排列λ使得对于任意1≤i≤d，x_λ(i) < y_i，所以X→Y。

b.必要性:

用数学归纳法证明。

当维数为1时,X→Y 可得 x₁< y₁_，那么x_π(1) < y_θ(1)成立。

假设维数为d时，结论成立，即: 当X→Y时，对于任意1≤i≤d，有x_π(i) < y_θ(i)_。那么当维数为d + 1时，对于任意1≤i≤d+1，X→Y，则存在λ使得:

x_λ(1) < y₁， x_λ(2) < y₂，．．．，x_λ(d) <y_d，x_λ(d+1) <y_d+1——1

先观察1式前d项, x_λ(1) < y₁， x_λ(2) < y₂，．．．，x_λ(d) <y_d。

由假设可知，对任意1≤i≤d，有存在排列π、θ使得x_π(i) < y_θ(i)，

即:

x_π(₁₎≤x_π(₂₎≤ ．．．≤x_π(_d)——2

y_θ(₁₎≤y_θ(₂₎≤ ．．．≤y_θ(_d) ——3

x_π(1) < y_θ(1)，x_π(2) < y_θ(2)，．．．，x_π(d) < y_θ(d)——4

此时，π、θ只对1式前d项进行排列，并不包含x_λ(d+1)和 y_d+1。可以将x_λ(d+1)按大小顺序插入到2式(设插入位置为j)，从而有新的排列π’使得x_i(1≤i≤d+1) 非递减有序。

同理，也有θ’使得y_d+1按大小顺序插入到3式后(设插入位置为k)，y_i(1≤i≤d+1) 非递减有序。

因为x_λ(d+1) <y_d+1_，易知j≤k。

当j = k时，因为x_m、y_m(1≤m≤d+1)的对应位置都没有变，显然x_π’(i)< y_θ’(i)(1≤i≤d+1)，所证结论成立。

当j<k时，x₁<y₁，x₂<y₂，．．．，x_j<x_j+1<y_j，x_j+1<x_j+2< y_j+1，．．．，x_k-1<x_k< y_{k -1}，x_k<y_{k -1} < y_k，x_k+1<y_k+1，．．．，x_d+1< y_d+1。

即, 对任意1≤i≤d+1 x_π’(i) < y_θ’(i)，所证结论成立。

命题得证。

■ 算法实现

由上面所得结论，对两个d维箱进行排序后，只要判断排序后两个d维箱的嵌套关系就可以得出结果。

-----------------------------------------------------------------------------------------

求两个箱子的嵌套关系的伪代码:

返回1表示X嵌套Y(即Y→X)

返回–1表示Y嵌套X(即X→Y)

返回0表示X和Y之间无嵌套关系

NEST(X , Y , d):

Sort(X) ▹对数组所表示的d维箱X、Y进行排序

Sort(Y)

if X[0] > Y[0]

then for i ← 1 to d – 1

do if X[i] <=Y[i]

then return 0

return 1

else for i ← 0 to d – 1

do if X[i] >=Y[i]

then return 0

return –1

--------------------------------------------------------------------------------------

■ 时间复杂度分析

NEST()的主要时间消耗在于排序，使用快速排序时，NEST()的时间复杂度为: O(d lgd)。

■ 算法测试

对应的算法实现Java源文件为NestedBox.java

输入：X(1,6,2,5,9) ，Y(7,4,8,19,32)

输出: Y嵌套X

3) 最长嵌套箱序列

■ 算法思想

将n个d维箱之间的关系用一棵树来表示，其中可嵌套其它箱子的箱子为父节点，被嵌套的箱子作为孩子节点，无嵌套关系的节点为兄弟节点。这样就一个d维箱的深度值就是在这棵树中的深度。

深度值的递归定义如下:

只要找出深度最大的节点，然后递归地输出它嵌套的箱子，结果就是最长嵌套箱序列。

■ 贪心选择性质

假设最长d维箱序列的一个最优解是B₁ , B₂ , …,B_k(k>1),其对应的深度值分别为H₁, H₂, …, H_k (H₁> H₂…> H_k)。

a.若H₁为最大的深度值，则说明问题的最优解以一个贪心选择开始。

b.若H₁不是最大的深度值，不妨设H₁<H_j (1<j≤k)。但B₁嵌套B_j可得H₁ >H_j。与假设矛盾。所以H₁为最大的深度值，这说明问题的最优解以一个贪心选择开始。

■ 最优子结构性质

设嵌套序列B₁ , B₂ , …,B_k(k>1)是问题的一个最优解，各个箱子的深度值为H₁, H₂, …, H_k (H₁> H₂…> H_k)。由贪心选择性质可知H₁为最大深度值，其余箱子组成的序列B₂ ,B₃, …,B_k(k>1)是在所有箱子中去掉B₁及与其具有相同深度值的箱子后，在剩下的箱子中查找最长嵌套箱序列的一个最优解。因此，最长嵌套箱序列问题具有最优子结构性质。

■ 算法实现

--------------------------------------------------------------------------------------

求最长嵌套箱序列的伪代码:

B为存放n个d维箱的二维数组

Longest(B , n , d):

▹A 存放各箱子嵌套关系的二维数组,下标从0开始,列数为n+1.

▹A[i,n]表示箱子i的深度值

▹初始化A数组

for i ← 0 to n

do A[i , n] ← 0

▹计算嵌套关系

for i ← 0 to n – 1

do for j ← i+1 to n – 1

do A[i , j] ← nest(B[i] , B[j] , d)

A[j , i] ← – A[i , j]

▹递归地修改嵌套的深度值

for i ← 0 to n – 1

do for j ← 0 to n – 1

if A[i , j] = – 1

then addHeight(A , n , i , j)

▹查找深度值最大的箱子作为首嵌套箱

maxBoxIndex ← findMax()

▹输出最长嵌套箱序列

trace(maxBoxIndex)

--------------------------------------------------------------------------------------

递归地修改嵌套箱的深度值

addHeight(A , n , i , j):

if A[i , n] = A[j , n]

then A[j , n] ← A[j , n] + 1

for k ← 0 to n – 1

do if A[j , k] = – 1

then addHeight(A , n , j , k)

--------------------------------------------------------------------------------------

查找深度值最大的箱子作为首嵌套箱

findMax(A , n):

max ← A[0 , n]

maxBoxIndex ← 0

for i ← 0 to n – 1

do if A[i , n] > max

then max ← A[i , n]

maxBoxIndex ← i

return maxBoxIndex

--------------------------------------------------------------------------------------

根据深度值最大的箱子,输出最长嵌套箱序列

trace(n , maxIndex):

while A[max][n] > 0

do seq ← (max+1) + “→” + seq

m ← 0

for i ← 0 to n – 1

do if A[max , i] = 1 and A[i , n] >=m

then m ← A[i , n]

temp ← i

max ← temp

seq ← (max+1) + “→

分享到：

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

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

发表评论

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

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

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

评论

发表评论

相关推荐

最近访客 更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

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

评论

发表评论

相关推荐

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

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

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

最近访客更多访客>>