algorithm - problems - Problema de construcción de puentes: ¿cómo aplicar la subsecuencia cada vez mayor?
dynamic programming problems (6)
Aquí hay una implementación de Java del problema.
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_;
}
}
}
El problema de la construcción de puentes se explica a continuación:
Hay un río que corre horizontalmente a través de un área. Hay un conjunto de ciudades por encima y por debajo del río. Cada ciudad sobre el río se empareja con una ciudad debajo del río, y se le da esta coincidencia como un conjunto de pares.
Está interesado en construir un conjunto de puentes a través del río para conectar el mayor número de pares de ciudades, pero debe hacerlo de manera que no haya dos puentes que se crucen entre sí.
Diseñe un algoritmo para resolver este problema de la manera más eficiente posible.
He escuchado que este problema está relacionado con el problema de subsecuencias en aumento más largo , pero no veo cómo usarlo aquí. Por ejemplo, si nos dan las parejas.
2 5 8 10
6 4 1 2
Entonces, ¿qué secuencia consideramos para LIS?
¡Gracias!
Este es un código de trabajo en c ++ para el problema anterior.
#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;
}
Este es un problema de programación dinámica, que se puede modelar incluso como un problema de subsecuencia más largo. Considere las coordenadas de las ciudades al norte del río como a1, a2, a3..aN. Ahora encuentre las ciudades correspondientes en el sur del río y márquelas como a1, a2, a3..aN también. La solución al problema será la subsecuencia común más larga de las cuerdas formadas por los AI en el norte y sur del río.
Ordena una lista y encuentra LIS en otro. Código de 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;
}
Para desarrollar la forma en que usaría el algoritmo de subsecuencias cada vez más largas para resolver este problema, comencemos con algo de intuición y luego construyamos una solución. Ya que solo puedes construir puentes entre ciudades en índices coincidentes, puedes pensar en el conjunto de puentes que terminas construyendo como el mayor conjunto de pares que puedes encontrar que no contienen ningún cruce. Entonces, ¿bajo qué circunstancia tendrías un cruce?
Veamos cuando esto puede suceder. Supongamos que ordenamos todos los puentes construidos por su primera ciudad. Si dos puentes se cruzan, entonces debemos tener que hay algún puente (a i , b i ) tal que para algún otro puente (a j , b j ) se cumpla uno de los siguientes:
- a i <a j y b i> b j
- a i > a j y b i <b j
Este primer caso dice que hay un puente cuya ciudad superior está más a la derecha que el comienzo de nuestro puente y cuya ciudad inferior está más a la izquierda que el final de nuestro puente, y el segundo caso se encarga del caso opuesto.
Dado que esta propiedad debe mantenerse, debemos asegurarnos de que para cada conjunto de puentes, tenemos exactamente una de las dos propiedades siguientes para cualquier par de puentes (a i , b i ), (a j , b j ) : ya sea
- a i ≤ a j y b i ≤ b j
o
- a i ≥ a j y b i ≥ b j
En otras palabras, si tuviéramos que ordenar los puentes por su primera coordenada, el conjunto de segundas coordenadas siempre aumentaría. De manera similar, si tuviéramos que ordenar los puentes por su segundo coordinador, la primera coordenada siempre estaría aumentando.
La propiedad que acabamos de definir define un orden parcial ≤ ambos en el conjunto de puentes, donde decimos que (a i , b i ) ≤ ambos (a j , b j ) si a i ≤ a j y b i ≤ b j Tenga en cuenta que este no es un pedido total, por ejemplo, (1, 2) es incomparable con (2, 1), pero es un pedido parcial porque es reflexivo, antisimétrico y transitivo.
Teniendo en cuenta esto, el objetivo del problema es encontrar el mayor conjunto de elementos que podemos ordenar por esta relación, ya que si tenemos un conjunto que contiene dos elementos incomparables, esos elementos deben representar necesariamente puentes cruzados. En otras palabras, queremos encontrar la cadena más larga en el orden parcial. Una forma de hacer esto es, en tiempo O (n 2 ), comparar cada elemento entre sí y ver qué elementos pueden ser ordenados por ≤ ambos . Esto produce un gráfico acíclico dirigido, donde el par (a i , b i ) tiene un borde a (a j , b j ) iff (a i , b i ) ≤ ambos (a j , b j ). Una vez que tenemos este gráfico acíclico dirigido, podemos encontrar el camino más largo en el gráfico para encontrar el conjunto más grande de elementos que se pueden comparar con ≤ ambos , lo que luego da la solución al problema. El tiempo de ejecución global es, por tanto, O (n 2 ).
Sin embargo, podemos hacerlo sustancialmente mejor que esto. El problema con el algoritmo anterior es que no podemos saber fácilmente cómo se comparan los elementos entre sí, por lo que tenemos que comparar explícitamente cada ciudad con otra ciudad.
2 5 8 10
6 4 1 2
Vamos a ordenar las ciudades por la fila inferior:
8 10 5 2
1 2 4 6
Ahora, aquí está la observación realmente genial. Si tenemos los elementos ordenados por su fila inferior, podemos decir si dos pares se pueden ordenar por ≤ ambos mirando sus posiciones en la fila superior. Si el primer par está a la izquierda del segundo par, inmediatamente sabemos que los segundos elementos del primer par son menores que el segundo elemento del segundo par, ya que los hemos ordenado por la segunda coordenada. Luego tenemos que el par de elementos se pueden construir juntos si el primer elemento del primer par es menor que el primer elemento del segundo par. Por consiguiente, si queremos encontrar un conjunto de puentes que puedan construirse juntos, estamos buscando una subsecuencia creciente de la fila superior, ya que en ese caso tanto el primer como el segundo elemento de los pares aumentan a medida que avanzamos desde el Izquierda a la derecha. Encontrar la subsecuencia cada vez más larga resuelve este problema. Ya que podemos clasificar los pares por su segundo campo en O (n log n) y encontrar la subsecuencia con el aumento más largo en O (n log n), ¡esta es una solución O (n log n) para el problema!
¡Uf! Espero que esta respuesta explique las cosas en detalle!
Primero considere los pares: (2,6), (5, 4), (8, 1), (10, 2) , ordénelos según el primer elemento de los pares (en este caso ya están ordenados) y calcule los Haga una lista en el segundo elemento de los pares, así calcule el LIS en 6 4 1 2 , que es 1 2 . Por lo tanto, las líneas no superpuestas que busca son (8, 1) y (10, 2) .