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

Question

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

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

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

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

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

2 5 8 10 
6 4 1 2 

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

Спасибо!

Answer 1

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

Давайте посмотрим, когда это может произойти. Предположим, что мы сортируем все мосты, построенные их первым городом. Если пересечь два моста, то мы должны иметь, что есть некоторый мост (а _я, б _я) такой, что для некоторого другого моста (а _J, б _J) один из следующих условий:

• _я < _J и б _я> б _J
• _я> а _J и б _я < б _J

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

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

• _я ≤ _J и б _я ≤ б _J

или

• _я ≥ _J и б _я ≥ б _J

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

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

Учитывая это, задача состоит в том, чтобы найти самый большой набор элементов, которые мы можем, которые могут быть полностью упорядочены этим отношением, поскольку, если у нас есть набор, содержащий два несравнимых элемента, эти элементы обязательно должны представлять собой пересекающиеся мосты. Другими словами, мы хотим найти самую длинную цепочку в частичном порядке. Один из способов сделать это - в O (n) время, сравнить каждый элемент друг с другом и посмотреть, какие элементы можно заказать по ≤ _и. Это создает ориентированный ациклический граф, где пара (а _я, б _я) имеет кромку (а _J, б _J) тогда и только тогда (а _я, б _я) ≤ _оба (a _j, b _j).Как только мы получим этот ациклический граф, мы сможем найти longest path in the graph, чтобы найти самый большой набор элементов, которые являются сопоставимыми по ≤ _и, что затем дает решение проблемы. Таким образом, общее время работы 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

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

Answer 4

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

    } 

Answer 6

Сортировать один список и найти LIS в other.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; 
}