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

Ответ 1

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

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

• a _i < a _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

Теперь, здесь действительно классное наблюдение. Если у нас есть элементы, отсортированные по их нижней строке, то мы можем сказать, могут ли две пары упорядочиваться через & le; _какпросматривая их позиции в верхнем ряду. Если первая пара находится слева от второй пары, мы сразу же знаем, что второй элемент первой пары меньше второго элемента второй пары, так как мы отсортировали их по второй координате. Затем мы получаем, что пару элементов можно построить вместе, если первый элемент первой пары меньше первого элемента второй пары. Следовательно, если мы хотим найти набор мостов, которые можно построить вместе, мы будем искать возрастающую подпоследовательность верхней строки, так как в этом случае как первый, так и второй элементы пар увеличиваются по мере того, как мы переходим от слева направо. Нахождение самой длинной возрастающей подпоследовательности затем решает эту проблему. Поскольку мы можем сортировать пары по их второму полю в O (n log n) и находить самую длинную возрастающую подпоследовательность в O (n log n), это решение O (n log n) для задачи!

Уф! Надеюсь, что этот ответ подробно объяснит подробности!

Ответ 2

Сначала рассмотрим пары: (2,6), (5, 4), (8, 1), (10, 2), отсортируйте его по первому элементу пар (в этом случае уже отсортированы) и вычислите список во втором элементе пар, таким образом вычислив LIS на 6 4 1 2, то есть 1 2. Поэтому неперекрывающиеся строки, которые вы ищете, это (8, 1) и (10, 2).

Ответ 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_;
            }
        }

    }

Ответ 4

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

Ответ 5

Это рабочий код в С++ для указанной проблемы.

#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;
}