二、嵌套箱問題
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
天堂露珠 閱讀(332)
評論(0) 編輯 收藏 所屬分類:
Algorithm