二、嵌套箱问题

2、一个维箱(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},试设计并实现一个贪心算法找出这d维箱中的一个最长嵌套箱序列,并用n描述算法的计算时间复杂性。

 

1)  箱嵌套关系的传递性

证明:

设有3d维箱B1(x1 , x2 , ... , xd) B2 (y1 , y2 , ..., yd) B3(z1 , z2 , ..., zd) B1可嵌入B2B2可嵌入B3

B1可嵌入B2,则存在排列π使得:

xπ(1) < y1xπ(2) < y,...,xπ(d) < yd        ——1

B2可嵌入B3,则存在排列θ使得:

yθ(1) < z1yθ(2) < z,...,yθ(d) < zd        ——2

   1式可得:

xθ(π(1)) < yθ(1)xθ(π(2)) < yθ(2) ,...,xθ(π(d)) < yθ(d)  ——3

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

xλ(1) < z1xλ(2) < z,...,xλ(d) < zd

根据d维箱的定义可得,B1可嵌入B3。因此,嵌套箱关系具有传递性。

 

2)  d维箱的嵌套关系

   贪心选择性质:

对于d维箱X(x1 , x2 , ... , xd),Y (y1 , y2 , ..., yd),排列 πθ是分别使XY非递减有序的排列,有如下结论:XY(表示X可嵌入Y)的充要条件是,对任意1idxπ(i) < yθ(i)

 

证明:

      a.充分性:

对任意1idxπ(i) < yθ(i)时,令λ = πθ-1,那么

xλ(i) xπ(θ-1 (i)) < yθ(θ-1 (i)) = y即存在一个排列λ使得对于任意1idxλ(i) < y,所以XY

   b.必要性:

用数学归纳法证明。

当维数为1,X可得 x1y那么xπ(1) < yθ(1)成立

假设维数为d时,结论成立,即: XY时,对于任意1id,有xπ(i) < yθ(i)那么当维数为d + 1时,对于任意1id+1XY,则存在λ使得:

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) <y

由假设可知,对任意1id,有存在排列πθ使得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(1id+1非递减有序。

同理,也有θ’使得yd+1按大小顺序插入到3式后(设插入位置为k)yi(1id+1非递减有序。

因为xλ(d+1) <yd+1易知jk

j = k时,因为xy(1md+1)的对应位置都没有变,显然xπ’(i) < yθ’(i) (1id+1)所证结论成立。

j<k时,x1<yx2<y2,...,xj<xj+1<yxj+1<xj+2< yj+1,...,xk-1<xk< yk -1xk<yk -1 < ykxk+1<y k+1,...,xd+1< y d+1

, 对任意1id+1 xπ’(i) < yθ’(i) 所证结论成立。

命题得证。

 

   算法实现

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

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

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

返回1表示X嵌套Y(YX)

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

返回0表示XY之间无嵌套关系

NEST(X , Y , d):

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

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)  最长嵌套箱序列

   算法思想

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

深度值的递归定义如下:

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

   贪心选择性质

假设最长d维箱序列的一个最优解是B1 , B2 , …,Bk  (k>1),其对应的深度值分别为H1, H, …, Hk(H> H2…> Hk)

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

b.H1不是最大的深度值,不妨设H1<Hj (1<jk)。但B1嵌套B可得H1 >Hj。与假设矛盾。所以H1为最大的深度值,这说明问题的最优解以一个贪心选择开始。

   最优子结构性质

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

   算法实现

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

B为存放nd维箱的二维数组

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(nd lgd)

 

   算法测试:

相应的算法实现文件为LongestNestedBox.java

输入数据: (86维箱)

{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开始)

最长嵌套箱序列:7256