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

Question

建桥问题表述如下：

有一条河流水平流过一个区域。河的上方和下方有一组城市。河流上方的每个城市都与河流下方的城市相匹配，并且您会以一组对的形式获得此匹配。

您有兴趣在河流上建造一组桥梁来连接最多数量的匹配城市对，但您必须以没有两座桥梁相互相交的方式进行此操作。

设计一种算法来尽可能有效地解决这个问题。

我听说这个问题与最长递增子序列问题有关，但我没有看到如何使用这里。例如，如果给定对

2  5  8  10
6  4  1  2

，那么我们应该考虑 LIS 的哪个序列？

谢谢！

Answer 1

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

让我们看看什么时候会发生这种情况。假设我们对第一个城市建造的所有桥梁进行排序。如果两座桥交叉，那么我们必须有某个桥 (a_i, b_i)，这样对于其他桥 (a_j >, b_j) 以下之一成立：

• a_i < a_j 和 b_i > b_j
• a_i > a_j 和 b_{i bj}

第一个情况表示有一座桥，其顶部城市比桥的起点更靠右，而底部城市比桥的终点更靠左，并且第二种情况处理相反的情况。

鉴于需要保持此属性，我们需要确保对于每组桥，我们都具有以下两个属性之一对于任何桥对 (a_i, b _i), (a_j, b_j):

• a_i ≤ a_j 并且b_i ≤ b_j

或

• a_i ≥ a_j 且 b_i ≥ b_j

换句话说，如果我们要对桥进行排序通过它们的第一个坐标，第二个坐标组将始终增加。同样，如果我们按照第二个坐标对桥进行排序，则第一个坐标将始终增加。

我们刚刚定义的属性定义了桥集上的部分排序 ≤_both，其中我们说 (a_i, b_i) ≤_两者 (a_j, b_j) 如果 a_i ≤ a_{j 和 bi ≤ bj。请注意，这不是全排序 - 例如，(1, 2) 与 (2, 1) 无法比较 - 但它是偏排序，因为它是自反的、反对称的和传递的。}

鉴于此，问题的目标是找到可以通过这种关系完全排序的最大元素集，因为如果我们有一个包含两个不可比较元素的集合，这些元素必然代表过桥。换句话说，我们想要找到偏序中最长的链。实现此目的的一种方法是在 O(n²) 时间内将每个元素与其他元素进行比较，并查看哪些元素可以按 ≤_both 排序。这会产生一个有向无环图，其中对 (a_i, b_i) 具有到 (a_j, b _j) iff (a_i, b_i) ≤_两者 (a_j, b<子>j）。一旦我们有了这个有向无环图，我们就可以找到图中的最长路径找到可通过 ≤_both 进行比较的最大元素集，然后给出问题的解决方案。因此，总体运行时间为 O(n²)。

然而，我们可以做得比这更好。上述算法的问题在于，我们无法轻易判断元素如何相互比较，因此我们必须明确地将每个城市与其他城市进行比较。

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) 解决方案！

哇！希望这个答案能够详细解释！

Answer 2

首先考虑对：(2,6), (5, 4), (8, 1), (10, 2)，根据对的第一个元素对其进行排序（在本例中已经排序）并计算对的第二个元素的列表，从而计算 6 4 1 2 上的 LIS，即 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_;
            }
        }

    }

Answer 4

这是一个动态规划问题，甚至可以建模为最长子序列问题。考虑河以北城市的坐标为a1,a2,a3..aN。现在找到河南对应的城市，并将它们也标记为a1,a2,a3..aN。
问题的解决方案将是由河流北部和南部的人工智能形成的串的最长公共子序列。

Answer 5

这是针对上述问题的 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;
}

Answer 6

对一个列表进行排序并在其他中找到LIS。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;
}

Answer 7

这是不允许跨越的建桥问题，可以使用以下三个步骤来解决。

• 按该对的第一个值的升序对数组进行排序。如果两个第一个值相同，例如我们有 (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)]

第 2 步：[2, 6, 4< 的 LIS /strong>, 3, 5, 7, 8, 1] = [2, 4, 5, 7, 8]

步骤3：输出为长度 ([2, 4, 5, 7, 8]) = 5