建立桥梁问题 - 如何应用最长的增长子序列？

Question

建筑桥梁问题陈述如下:

有一条河流水平穿过一个区域.河流上下都有一组城市.河上的每个城市都与河下的城市相匹配,您可以将这种匹配作为一组配对.

您有兴趣在河对岸建造一组桥梁,以连接最大数量的匹配城市,但您必须以两座桥梁彼此不相交的方式进行连接.

设计算法以尽可能有效地解决此问题.

我听说这个问题与最长的子序列问题有关,但我不知道如何在这里使用它.例如,如果我们给对了

2  5  8  10
6  4  1  2

那么我们为LIS考虑哪个序列？

谢谢!

Answer 1

为了建立你如何使用最长的增长子序列算法来解决这个问题,让我们从一些直觉开始,然后建立一个解决方案.由于您只能在匹配索引的城市之间建立桥梁,因此您可以将最终构建的桥梁组视为您可以找到的不包含任何交叉的最大对.那么在什么情况下你会穿越？

让我们看看何时会发生这种情况.假设我们对他们的第一个城市建造的所有桥梁进行排序.如果两个桥交叉,那么我们必须有一些桥(a _i,b _i),这样对于某些其他桥(a _j,b _j),下列之一成立:

• 一个_我 <A _Ĵ和b _我 > b _Ĵ
• a _i > a _j和b _i <b _j

第一个案例说,有一座桥,其顶部城市比我们的桥的起点更靠右边,其底部城市比我们的桥的末端更靠左边,第二个案例处理相反的情况.

鉴于此属性需要保持,我们需要确保对于每组桥,我们对于任何一对桥(a _i,b _i),(a _j,b _j)都具有以下两个属性中的一个::要么

• 一个_我 ≤一个_Ĵ和b _我 ≤b _Ĵ

要么

• 一个_我 ≥一个_Ĵ和b _我 ≥b _Ĵ

换句话说,如果我们按照第一个坐标对桥进行排序,则第二个坐标集将始终增加.同样,如果我们按照第二个坐标对桥梁进行排序,第一个坐标将始终增加.

我们刚刚定义的属性定义偏序≤ _双方所设定的桥梁,在这里我们说的是:(a _我,B _我)≤ _两个(一个_Ĵ,B _Ĵ)如果_我 ≤一_Ĵ和b _我 ≤ b _j.请注意,这不是一个总排序 - 例如,(1,2)与(2,1)无法比较 - 但它是一个部分排序,因为它是自反的,反对称的和传递的.

鉴于此,问题的目标是找到我们可以通过这种关系完全排序的最大元素集,因为如果我们有一个包含两个无法比较的元素的集合,那么这些元素必然必须代表交叉桥.换句话说,我们希望找到部分顺序中最长的链.一种方法是,在O(n ²)时间内,将每个元素与每个其他元素进行比较,并查看哪些元素可以按_两者排序.这产生有向无环图,其中对(a _i,b _i)具有到(a _j,b _j)iff(a _i,b _i)≤ _两者(a _j,b _j)的边.一旦我们得到了这个有向无环图,我们就可以找到图中最长的路径,找到被_两者调用的最大元素集,然后给出问题的解决方案.因此总运行时间为O(n ²).

但是,我们可以做得比这更好.上述算法的问题在于我们不能轻易地分辨元素如何相互比较,因此我们必须明确地将每个城市与其他城市进行比较.

2  5  8 10
6  4  1  2 

让我们按最底行排序城市:

8 10  5  2
1  2  4  6

现在,这是非常酷的观察.如果我们通过下面一行排序的元素,那么我们可以说,如果两对通过≤订购_都通过看他们的第一行中的位置.如果第一对位于第二对的左侧,我们立即知道第一对的第二个元素小于第二对的第二个元素,因为我们已经按第二个坐标对它们进行了排序.然后,如果第一对的第一个元素小于第二个对的第一个元素,则可以将这对元素组合在一起.因此,如果我们想要找到一组可以一起构建的桥,我们正在寻找顶行的增加子序列,因为在这种情况下,当我们离开时,对的第一个和第二个元素都在增加.向左走.找到增长最长的子序列然后解决这个问题.因为我们可以通过它们在O(n log n)中的第二个字段对这些对进行排序,并在O(n log n)中找到最长的增加子序列,这是该问题的O(n log n)解决方案!

呼!希望这个答案能够详细解释!

Answer 2

首先考虑对:(2,6), (5, 4), (8, 1), (10, 2)根据对的第一个元素对它进行排序(在这种情况下已经排序)并计算对的第二个元素上的列表,从而计算LIS 6 4 1 2,即1 2.因此,您正在寻找的非重叠线是(8, 1)和(10, 2).

Answer 3

这是问题的Java实现.

    package DP;

    import java.util.Arrays;
    import java.util.Comparator;

    public class BuildingBridges {

        public static void main(String[] args) {
            Pair[] A = new Pair[7];
            A[0] = new Pair(22,4);
            A[1] = new Pair(2,6);
            A[2] = new Pair(10,3);
            A[3] = new Pair(15,12);
            A[4] = new Pair(9,8);
            A[5] = new Pair(17,17);
            A[6] = new Pair(4,2);

            System.out.println(lis(A));
        }

        public static int lis(Pair[] A){
            Arrays.sort(A, new Comparator<Pair>() {
                @Override
                public int compare(Pair o1, Pair o2) {
                    return o1.x - o2.x;
                }
            });

            int n = A.length;
            int max = 0;
            int[] dp = new int[n];
            Arrays.fill(dp, 1);

            for(int i=1; i<n; i++){
                for(int j=0; j<i; j++){
                    if(A[i].y > A[j].y){
                        dp[i] = Math.max(dp[i], dp[j]+1);
                    }
                }
                max = Math.max(max, dp[i]);
            }

            return max;
        }

        public static class Pair{
            int x, y;
            public Pair(int x_, int y_){
                x = x_;
                y = y_;
            }
        }

    }