Питання Проблеми з будівництвом мостів - як застосувати найдовшу зростаючу підпослідовність?


Проблема будівництва мостів викладається наступним чином:

Є річка, яка проходить по горизонталі через територію. Є набір міст над і під річкою. Кожне місто над річкою поєднується з містом під річкою, і вам дано відповідність як набір пар.

Ви зацікавлені в створенні комплексу мостів через річку, щоб з'єднати найбільшу кількість відповідних пар міст, але ви повинні зробити це таким чином, щоб два мости не перетиналися один з одним.

Розробіть алгоритм для вирішення цієї проблеми якомога ефективніше.

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

2  5  8  10
6  4  1  2

Тоді яку послідовність ми розглядаємо для LIS?

Дякую!


27
2017-09-02 19:53


походження


Я не думаю, що проблема є загальновідомою, як ви можете підозрювати ... Чи можете ви описати це більш детально? - templatetypedef
Розглянемо 2-D карту з горизонтальною річкою, що проходить через її центр. На південному березі є російські міста з x-координатами a (1) ... a (n) і n містами на північному березі з x-координатами b (1) ... b (n). Ви хочете підключити якомога більше пари міст північ-південь з мостами таким чином, щоб не було двох мостів. Підключивши міста, ви можете лише підключити місто i до північного банку до міста i на південному березі - pranay
@ pranay- Чи міста на банку сортуються за координатами х? Чи вони в довільному порядку? - templatetypedef
@templatetypedef: вони можуть бути в довільному порядку або можуть бути відсортовані - pranay
Чи не ясно, що 2 5 8 10 є найдовшим між ними? - monn


Відповіді:


Для того, щоб вирішити цю проблему, використовуючи найдовший підсилювач для підпорядкування, давайте почнемо з інтуїції, а потім створимо рішення. Оскільки ви можете тільки будувати мости між містами за відповідними показниками, ви можете думати про набір мостів, які ви закінчуєте будівництво, як найбільший набір пар ви можете знайти, що не містять перехрестя. Так в якій обставині у вас буде перетинання?

Давайте подивимося, коли це станеться. Припустимо, що ми сортуємо всі мости, побудовані їх першим містом. Якщо два мости перетинаються, то ми повинні мати, що є якийсь міст (aя, бя) такий, що для деякого іншого мосту (aj, бj) виконує одну з таких дій:

  • aя <aj і бя > bj
  • aя > aj і бя <bj

У цьому першому випадку сказано, що існує міст, провідне місто якого знаходиться далі направо, ніж початок нашого мосту, а нижнє місто знаходиться далі вліво, ніж кінець нашого мосту, а другий - в протилежному випадку.

Оскільки ця властивість має триматися, ми повинні забезпечити, щоб для кожного набору мостів ми мали, що для будь-якої пари мостів існує рівно один з двох наступних властивостей (aя, бя), (аj, бj): або

  • aя ≤ aj і бя ≤ bj

або

  • aя ≥ aj і бя ≥ бj

Іншими словами, якщо б ми мали сортувати мости за їхньою першою координатою, набір других координат завжди був би збільшеним. Точно так само, якби ми мали сортувати мости за допомогою другого коордиєнта, перша координата завжди зростала.

Властивість, яку ми щойно визначили, визначає часткове замовлення ≤обидва на наборі мостів, де ми говоримо, що (ая, бя) ≤обидва (aj, бj) якщоя ≤ aj і бя ≤ bj. Зверніть увагу, що це не повне замовлення - наприклад, (1, 2) не можна порівняти з (2, 1) - але це часткове замовлення, оскільки воно є рефлексивним, антисиметричним і транзитивним.

З огляду на це, метою завдання є знайти найбільший набір елементів, які ми можемо повністю упорядковувати за допомогою цих відносин, оскільки якщо у нас є набір, що містить два незрівнянні елементи, то ці елементи повинні обов'язково представляти перехресні мости. Іншими словами, ми хочемо знайти найдовший ланцюг у частковому порядку. Один із способів зробити це є, в O (n2), порівнюйте кожен елемент з одним елементом і подивіться, які елементи можна замовити за допомогою ≤обидва. Це дає спрямований ациклічний граф, де пара (aя, бя) має край до (aj, бj) iff (aя, бя) ≤обидва (aj, бj) Як тільки ми отримаємо цей спрямований ациклічний граф, ми зможемо знайти найдовший шлях на графіку щоб знайти найбільший набір елементів, які називаються порівняними ≤обидва, який потім дає вирішення проблеми. Таким чином, загальна тривалість виконання є O (n2)

Однак ми можемо зробити суттєво краще, ніж це. Проблема з вищезгаданим алгоритмом полягає в тому, що ми не можемо легко сказати, як елементи порівнюються один з одним, тому ми повинні явно порівнювати кожне місто проти одного міста.

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) задачі!

Будь-ласка! Сподіваюся, що ця відповідь пояснює деталі!


49
2017-09-02 20:51



Велика інтуїція про даг - Simone
спасибі за чудове пояснення :) - pranay
Їй було більше 3-х років, оскільки ви написали цю відповідь .. Але все одно дуже корисно ..: D - coderzz027
@templatetypedef Неможливо вирішити її за допомогою LCS - Mohit Shah
@mohit Чи можете ви розробити? Яку дві послідовності ви б використовували? - templatetypedef


Спочатку розглянемо пари: (2,6), (5, 4), (8, 1), (10, 2), сортувати за першим елементом пар (у цьому випадку вони вже відсортовані) і обчислити список на другий елемент пар, таким чином обчислюючи LIS на 6 4 1 2, це 1 2. Тому без перетинання ліній ви шукаєте (8, 1) і (10, 2).


14
2017-09-02 20:36



ти ласкаво;) .. якщо ти цього ще не зробив, дай мені +1, будь ласка; D - Simone
Я це вже зробив :) - pranay
Красивий розв'язок. +1 від мене теж. :) - Vikas Gupta
Так, і від мене! краще, ніж прийнятий! короткий і солодкий - Kaushal28


Ось реалізація 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_;
            }
        }

    }

5
2017-12-27 18:27





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


4
2018-03-07 17:59



Відмінно. Просто відмінно. - Xunnamius


Сортувати один список і знайти 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;
}

1
2018-02-23 14:02





Це робочий код у 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;
}

0
2017-07-22 14:40



Але без пояснень чи коментарів пояснити, чому він працює. - Richard