二、嵌套箱问题
2、一个d 维箱(x1,x2,...,xn)嵌入另一个d 维箱(y1,y2,...,yn)是指存在1,2,…,d 的一个排列π，使得xπ(1)<y1 ,xπ(2) <y2,
... , xπ(d)<yd 。
1) 证明上述箱嵌套关系具有传递性；
2) 试设计并实现一个贪心算法，用于确定一个d维箱是否可嵌入另一个d维箱；
3) 给定由n 个d 维箱组成的集合{ B1,B2,B3,...,Bn}，试设计并实现一个贪心算法找出这n 个d维箱中的一个最长嵌套箱序列，并用n和d
描述算法的计算时间复杂性。
1) 箱嵌套关系的传递性
证明：
设有3个d维箱B1(x1 , x2
, ．．． , xd) ，B2 (y1 , y2 , ．．．, yd) ，B3(z1 , z2 , ．．．, zd) ，B1可嵌入B2，B2可嵌入B3。
B1可嵌入B2，则存在排列π使得：
xπ(1) < y1，xπ(2) < y2 ，．．．，xπ(d) < yd ——1
B2可嵌入B3，则存在排列θ使得：
yθ(1) < z1，yθ(2) < z2 ，．．．，yθ(d) < zd ——2
由1式可得：
xθ(π(1)) < yθ(1)，xθ(π(2)) < yθ(2) ，．．．，xθ(π(d)) < yθ(d) ——3
由23可得：存在排列λ = θπ使得：
xλ(1) < z1，xλ(2) < z2 ，．．．，xλ(d) < zd
根据d维箱的定义可得，B1可嵌入B3。因此，嵌套箱关系具有传递性。
2) d维箱的嵌套关系
■
贪心选择性质:
对于d维箱X(x1 , x2 , ．．． , xd),Y (y1 , y2 , ．．．, yd),排列 π、θ是分别使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)) = yi ，即存在一个排列λ使得对于任意1≤i≤d，xλ(i) < yi ，所以X→Y。
b.必要性:
用数学归纳法证明。
当维数为1时,X→Y 可得 x1< y1 ，那么xπ(1) < yθ(1)成立。
假设维数为d时，结论成立，即: 当X→Y时，对于任意1≤i≤d，有xπ(i) < yθ(i)。那么当维数为d + 1时，对于任意1≤i≤d+1，X→Y，则存在λ使得:
xλ(1) < y1， xλ(2) < y2 ，
．．．，xλ(d) <yd ， xλ(d+1)
<yd+1 ——1
先观察1式前d项, xλ(1) < y1， xλ(2)
< y2 ， ．．．，xλ(d) <yd 。
由假设可知，对任意1≤i≤d，有存在排列π、θ使得xπ(i) < yθ(i)，
即:
xπ(1)≤xπ(2)≤ ．．．≤xπ(d) ——2
yθ(1)≤yθ(2)≤ ．．．≤yθ(d) ——3
xπ(1) < yθ(1) ，xπ(2) < yθ(2) ，．．．，xπ(d) < yθ(d) ——4
此时，π、θ只对1式前d项进行排列，并不包含xλ(d+1) 和
yd+1。可以将xλ(d+1)
按大小顺序插入到2式(设插入位置为j)，从而有新的排列π’使得xi(1≤i≤d+1) 非递减有序。
同理，也有θ’使得yd+1按大小顺序插入到3式后(设插入位置为k)，yi(1≤i≤d+1) 非递减有序。
因为xλ(d+1)
<yd+1，易知j≤k。
当j = k时，因为xm 、ym (1≤m≤d+1)的对应位置都没有变，显然xπ’(i) < yθ’(i) (1≤i≤d+1)，所证结论成立。
当j<k时，x1<y1 ，x2<y2，．．．，xj<xj+1<yj ，xj+1<xj+2< yj+1，．．．，xk-1<xk< yk -1，xk<yk -1 < yk，xk+1<y k+1，．．．，xd+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维箱序列的一个最优解是B1 , B2 , …,Bk (k>1),其对应的深度值分别为H1,
H2 , …, Hk (H1 > H2…> Hk)。
a.若H1为最大的深度值，则说明问题的最优解以一个贪心选择开始。
b.若H1不是最大的深度值，不妨设H1<Hj
(1<j≤k)。但B1嵌套Bj 可得H1
>Hj。与假设矛盾。所以H1为最大的深度值，这说明问题的最优解以一个贪心选择开始。
■
最优子结构性质
设嵌套序列B1
, B2 , …,Bk (k>1)是问题的一个最优解，各个箱子的深度值为H1, H2 , …, Hk
(H1 > H2…> Hk)。由贪心选择性质可知H1为最大深度值，其余箱子组成的序列B2 ,B3 , …,Bk (k>1)是在所有箱子中去掉B1
及与其具有相同深度值的箱子后，在剩下的箱子中查找最长嵌套箱序列的一个最优解。因此，最长嵌套箱序列问题具有最优子结构性质。
■
算法实现
--------------------------------------------------------------------------------------
求最长嵌套箱序列的伪代码:
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) + “→” + seq
print
seq
--------------------------------------------------------------------------------------
■
时间复杂度分析:
算法的主要时间消耗在于Longest()中计算嵌套关系的时候，其中nest()算法的时间复杂度为O(d lgd)。所以总时间复杂度为:O(n2 d lgd)。
■
算法测试:
相应的算法实现文件为LongestNestedBox.java
输入数据: (8个6维箱)
{5, 2, 20, 1, 30, 10},{23, 15, 7, 9 ,11, 3},
{40 ,50 ,34 ,24, 14, 4},{9 ,10,
11 ,12, 13, 14},
{31, 4 ,18, 8 ,27, 17},{44, 32, 13, 19 ,41, 19},
{1 ,2, 3 ,4 ,5, 6},{80, 37 ,47 ,18 ,21, 9}
输出数据: (输出数据中的数字代表按顺序输入的箱子，编号从1开始)
最长嵌套箱序列:7→2→5→6
文章来源:
http://wintys.blog.51cto.com/425414/100701
[附件]:
嵌套箱.zip
posted on 2009-03-18 12:02
天堂露珠 阅读(325)
评论(0) 编辑 收藏 所属分类:
Algorithm