logo标签列表

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

algorithmdynamic-programming
33

建桥问题的陈述如下：

某区域有一条水平流动的河流。该区域上下各有一组城市。每个在河流上方的城市都与河流下方的一个城市匹配，你会得到这些匹配对。

你希望建立一组跨过河流的桥梁，以连接尽可能多的城市匹配对，但必须以不相交的方式完成。

设计一种算法，以尽可能高效地解决此问题。

我听说这个问题与最长上升子序列问题有关，但我不知道如何在这里使用它。例如，如果我们已经得到了以下匹配对：

2  5  8  10
6  4  1  2

那么我们应该考虑哪个序列来计算最长上升子序列呢？

谢谢！

1
我认为这个问题并不像你想象的那样广为人知... 你能详细描述一下吗？ - templatetypedef
考虑一个带有水平河流的二维地图，该河流穿过其中心。南岸上有n个城市，其x坐标为a(1) ... a(n)，北岸上有n个城市，其x坐标为b(1) ... b(n)。您想要连接尽可能多的南北城市对，以便桥梁不会交叉。在连接城市时，您只能将北岸上的第i个城市连接到南岸上的第i个城市。 - pranay
@pranay- 河岸上的城市按x坐标排序了吗？还是随机排列的？ - templatetypedef
@templatetypedef：它们可能是无序的，也可能是排序的。 - pranay
难道不清楚2 5 8 10是两者中最长的吗？ - monn
我认为你的问题陈述是“不正确的”，如果你看一下：http://www.geeksforgeeks.org/dynamic-programming-set-14-variations-of-lis/让我们退一步，假设你在北岸有n座建筑物，在南岸另外有n座建筑物，它们之间存在映射关系，从北岸城市到南岸城市，因此，你可以想象实际上其中一个岸的城市被认为是“排序”的。 - xxmajia
7个回答
58
为了解决这个问题，我们需要使用最长递增子序列算法，从直觉开始逐步推导出解决方案。由于只能在匹配索引之间建立桥梁，因此您可以将最终建造的桥梁集视为最大的一组不包含任何交叉的桥梁对。那么什么情况下会发生交叉呢？
让我们看看这种情况可能发生的时候。假设我们按照第一个城市建造的所有桥梁进行排序。如果两座桥梁相交，则必须有某座桥梁(ai, bi)，使得对于另一座桥梁(aj, bj)，以下情况之一成立：
- ai < aj 且 bi > bj - ai > aj 且 bi < bj 第一种情况表示存在一座桥梁，其顶部城市比我们的桥梁的起点更靠右，底部城市比我们的桥梁的终点更靠左，而第二种情况则处理相反的情况。
鉴于这个性质需要保持不变，我们需要确保对于每组桥梁，对于任何一对桥梁(ai, bi)和(aj, bj)，恰好满足以下两种属性之一：
  • ai ≤ aj 且 bi ≤ bj

或者

  • ai ≥ aj 且 bi ≥ bj

换句话说，如果我们按照第一个坐标对桥进行排序，则第二个坐标的集合始终是递增的。同样地，如果我们按照第二个坐标对桥进行排序，则第一个坐标始终是递增的。

我们刚才定义的属性在桥的集合上定义了一个≤both的偏序关系，其中我们说(ai, bi)≤both(aj, bj)，如果ai ≤ aj 且 bi ≤ bj。请注意，这不是一个完全的顺序关系-例如，(1,2)无法与(2,1)比较，但它是偏序关系，因为它是自反的，反对称的和传递的。

鉴于此，问题的目标是找到可以完全按照这种关系进行排序的最大元素集，因为如果我们有一个包含两个不可比较元素的集合，这些元素必须代表穿过桥梁。换句话说，我们想在偏序中找到最长的链。一种方法是，在O(n^2)时间内，将每个元素与每个其他元素进行比较，并查看哪些元素可以通过≤both进行排序。这会产生一个有向无环图，其中对(a_i, b_i)和(a_j, b_j)的配对，如果(a_i, b_i) ≤both (a_j, b_j)，则(a_i, b_i)有一条边指向(a_j, b_j)。一旦我们有了这个有向无环图，我们就可以找到图中的最长路径，以找到可以通过≤both相互比较的最大元素集，从而解决问题。因此，总运行时间为O(n^2)。
然而，我们可以比这个算法更好地做得多。上述算法的问题在于我们不能轻易地确定元素彼此之间的比较方式，因此我们必须显式地将每个城市与每个其他城市进行比较。
2  5  8 10
6  4  1  2

让我们按照底部行来排序城市：

8 10  5  2
1  2  4  6

现在，这里有一个非常酷的观察结果。如果我们按照它们底部行的顺序对元素进行排序，那么我们可以通过查看它们在顶部行中的位置来判断两个配对是否可以被≤both排序。如果第一对在第二对的左侧，我们立即知道第一对的第二个元素小于第二对的第二个元素，因为我们已经按第二个坐标对它们进行了排序。然后，我们有当且仅当第一对的第一个元素小于第二对的第一个元素时，元素对可以一起构建。因此，如果我们想要找到一组可以一起构建的桥梁，我们要寻找顶部行的递增子序列，因为在这种情况下，从左到右移动时，配对的第一个和第二个元素都在递增。然后，找到最长的递增子序列就解决了这个问题。由于我们可以按照它们的第二字段在O(n log n)内对配对进行排序，并在O(n log n)内找到最长的递增子序列，因此这是该问题的一个O(n log n)解决方案！希望这个答案详细地解释了问题！
关于DAG的直觉很棒 - Simone
这个回答已经超过3年了，但仍然非常有帮助。 :D - coderzz027
@mohit 你能详细说明一下吗？你将使用哪两个序列？ - templatetypedef
15

首先考虑这些数对：(2,6), (5, 4), (8, 1), (10, 2)，按照数对的第一个元素排序（在本例中已经排好序），计算数对的第二个元素列表，因此计算6 4 1 2上的最长上升子序列（LIS），即为1 2。因此，您要寻找的不重叠的线是(8, 1)和(10, 2)。

1
如果您还没有这样做，请给我一个+1，不用客气；） - Simone
不错的解决方案。我也点赞了。 :) - Vikas Gupta
是啊，我也这么觉得！比被接受的更好！简短而精练。 - Kaushal28
5

这是一个关于该问题的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_;
            }
        }

    }
4

这是一个动态规划问题，可以将其建模为最长子序列问题。考虑将河北城市的坐标视为a1,a2,a3..aN。现在找到南岸对应的城市，并将它们也标记为a1,a2,a3..aN。 然后该问题的解决方案将是在河北和河南的aI形成的字符串中最长的公共子序列。

1

对一个列表进行排序并在另一个列表中找到最长上升子序列。C++ 代码如下：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool cmp(pair<int,int> a, pair<int,int> b){
    return a.first<b.first;
}

int bridges(vector<pair<int,int> > connect){
    int i, j, n=connect.size();
    sort(connect.begin(),connect.end(),cmp);
    vector<int> lis(n,1);
    int m=0;
    for(i=0;i<n;i++){
        for(j=i-1;j>=0;j--){
            if(connect[i].second>connect[i].first)lis[i]=max(lis[i],lis[j]+1);
        }
        m=max(m,lis[i]);
    }
    return m;
}

int main(){
    int n, i;
    cin >> n;
    vector<pair<int,int> > a(n);
    for(i=0;i<n;i++)cin >> a[i].first >> a[i].second;
    cout << bridges(a) <<endl;
    return 0;
}
1

以下是针对上述问题的 C++ 工作代码。

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

struct pairs{
int x;
int y;  
};

bool myf(struct pairs p1,struct pairs p2){
return p1.x<p2.x;   
}

int lis(struct pairs a[],int n){
sort(a,a+n,myf);

int lis[n];

for(int i=0;i<n;i++)
    lis[i]=1;

for(int i=1;i<n;i++){

    for(int j=0;j<i;j++){
        if((a[j].y<a[i].y)&&(lis[i]<lis[j]+1))
            lis[i]=lis[j]+1;
    }
}

int max=lis[0];

for(int i=1;i<n;i++){
    if(max<lis[i])
        max=lis[i]; 
}

return max;
}

int main()
{
struct pairs arr[100];
int n;
cin>>n;
for(int i=0;i<n;i++){
    cin>>arr[i].x>>arr[i].y;    
}

int max=lis(arr,n);
cout<<max<<"\n";

return 0;
}
2
但是没有解释或评论来解释为什么它能工作。 - Richard
0

这是一个建桥问题，不允许交叉，并可以通过以下三个步骤解决。

  • 按照一对中的第一个值按升序对数组进行排序。如果两个第一个值相同，例如我们有(3, 6)和(3, 5)，则考虑第二个值。所以在这个例子中，(3, 5)将排在(3, 6)之前。
  • 根据第二个值找到已排序数组的最长递增子序列（LIS）。
  • 输出LIS数组的长度。

让我们来看一个例子：

输入：[(8, 1), (1, 2), (4, 3), (3, 4), (2, 6), (6, 7), (7, 8), (5, 5)]

步骤1：[(1, 2), (2, 6), (3, 4), (4, 3), (5, 5), (6, 7), (7, 8), (8, 1)]

第二步：LIS（最长递增子序列）为[2, 6, 4, 3, 5, 7, 8, 1]的结果是[2, 4, 5, 7, 8]。
第三步：输出为len([2, 4, 5, 7, 8]) = 5。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接