Проблема построения мостов - как применить самую длинную возрастающую подпоследовательность?

Question

Задача построения мостов сформулирована следующим образом:

Есть река, которая течет горизонтально через область. Есть множество городов выше и ниже реки. Каждый город над рекой сопоставляется с городом под рекой, и вы получаете это соответствие в виде пары пар.

Вы заинтересованы в строительстве набора мостов через реку для соединения наибольшего числа совпадающих пар городов, но вы должны сделать это так, чтобы никакие два моста не пересекались друг с другом.

Разработайте алгоритм для максимально эффективного решения этой проблемы.

Я слышал, что эта проблема связана с проблемой самой длинной возрастающей подпоследовательности , но я не вижу, как ее здесь использовать. Например, если нам даны пары

2  5  8  10
6  4  1  2

Тогда какую последовательность мы рассмотрим для LIS?

Спасибо!

Answer 1

Чтобы понять, как вы будете использовать самый длинный алгоритм увеличения подпоследовательности для решения этой проблемы, давайте начнем с некоторой интуиции, а затем перейдем к решению. Поскольку вы можете строить мосты между городами только по совпадающим индексам, вы можете думать о наборе мостов, который вы в итоге построите, как о самом большом наборе пар, которое вы можете найти, и в котором нет пересечения. Так при каких обстоятельствах у вас будет переход?

Посмотрим, когда это может произойти. Предположим, что мы сортируем все мосты, построенные их первым городом. Если два моста пересекаются, то мы должны иметь некоторый мост (a _i , b _i ) такой, что для какого-то другого моста (a _j , b _j ) выполняется одно из следующих действий:

• a _i j и b _i > b _j
• a _i > a _j и b _i j

Этот первый случай говорит о том, что существует мост, верхний город которого находится правее, чем начало нашего моста, а нижний город дальше слева, чем конец нашего моста, а второй случай обрабатывает противоположный случай. .

Учитывая, что это свойство должно храниться, мы должны убедиться, что для каждого набора мостов у нас есть одно из двух следующих свойств для любой пары мостов (a _i , b _i ), (a _j , b _j ): либо

• a _i & le; a _j и b _i & le; б _J

или

• a _i & ge; a _j и b _i & ge; б _J

Другими словами, если бы мы сортировали мосты по их первой координате, набор вторых координат всегда увеличивался бы. Точно так же, если бы мы сортировали мосты по их вторым координатам, первая координата всегда увеличивалась бы.

Свойство, которое мы только что определили, определяет частичное упорядочение & le; _обоих на множестве мостов, где мы говорим, что (a _i , b _i ) & le; _оба (a _j , b _j ), если a _i & le; a _j и b _i & le; б _J . Обратите внимание, что это не полное упорядочение - например, (1, 2) несопоставимо с (2, 1) - но это частичное упорядочение, потому что оно рефлексивно, антисимметрично и транзитивно.

Учитывая это, цель задачи состоит в том, чтобы найти самый большой набор элементов, который мы можем, который может быть полностью упорядочен этим соотношением, поскольку если у нас есть набор, содержащий два несопоставимых элемента, эти элементы обязательно должны представлять собой пересекающиеся мосты. Другими словами, мы хотим найти самую длинную цепочку в частичном порядке. Один из способов сделать это состоит в том, чтобы за O (n ² ) сравнить каждый элемент с каждым другим элементом и посмотреть, какие элементы можно упорядочить с помощью & le; _обоих . Это создает ориентированный ациклический граф, где пара (a _i , b _i ) имеет ребро к (a _j , b _j ) iff (a _i , b _i ) & le; _Оба (a _j , b _j ) , Получив этот ориентированный ациклический граф, мы можем найти самый длинный путь в графе , чтобы найти самый большой набор элементов, которые сравнимы по вызовам с помощью & le; _обоих , что затем дает Решение проблемы. Таким образом, общее время выполнения 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_;
            }
        }

    }

Answer 4

Это проблема динамического программирования, которую можно смоделировать даже как проблему самой длинной подпоследовательности. Рассмотрим координаты городов к северу от реки a1, a2, a3..aN. Теперь найдите соответствующие города на юге реки и отметьте их как a1, a2, a3..aN. Тогда решением проблемы будет самая длинная общая последовательность последовательностей, образованных аи на севере и юге реки.

Answer 5

Сортировка одного списка и поиск 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 6

Это рабочий код в 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;
}