algorithm - guia - Encuentra la secuencia creciente más larga

qgis manual

Question

Se te da una secuencia de números y necesitas encontrar una subsecuencia creciente más larga a partir de la entrada dada (no es necesaria en forma continua).

Encontré el enlace a esto (la subsecuencia creciente más larga en Wikipedia ) pero necesito más explicación.

Si alguien puede ayudarme a comprender la implementación de O (n log n), será realmente útil. Si pudieras explicar el algo con un ejemplo, eso será muy apreciado.

Vi las otras publicaciones también y lo que no entendí es: L = 0 para i = 1, 2, ... n: búsqueda binaria para el mayor j positivo ≤ L tal que X [M [j]] <X [i] (o establecer j = 0 si no existe tal valor) instrucción anterior, ¿desde dónde comenzar la búsqueda binaria? cómo inicializar M [], X []?

Answer 1

A continuación se muestra la implementación de subsecuencia creciente más larga O (NLogN):

// search for the index which can be replaced by the X. as the index can''t be
//0 or end (because if 0 then replace in the findLIS() and if it''s greater than the 
//current maximum the just append)of the array "result" so most of the boundary 
//conditions are not required.
public static int search(int[] result, int p, int r, int x)
{
    if(p > r) return -1;
    int q = (p+r)/2;
    if(result[q] < x && result[q+1]>x)
    {
        return q+1;
    }
    else if(result[q] > x)
    {
        return search(result, p, q, x);
    }
    else
    {
        return search(result, q+1, r, x);
    }
}
    public static int findLIS(int[] a)
    {
        int[] result = new int[a.length];
        result[0] = a[0];
        int index = 0;
        for(int i=1; i<a.length; i++)
        {
            int no = a[i];
            if(no < result[0]) // replacing the min number
            {
                result[0] = no;
            }
            else if(no > result[index])//if the number is bigger then the current big then append
            {
                result[++index] = no;
            }
            else
            {
                int c = search(result, 0, index, no);
                result[c] = no;
            }
        }
        return index+1;
    }

Answer 2

Basado en la respuesta de @fgb, implementé el algoritmo usando c ++ para encontrar la subsecuencia más larga y estrictamente creciente. Espero que esto sea de alguna manera útil.

M [i] es el índice del último elemento de la secuencia cuya longitud es i, P [i] es el índice del elemento anterior de i en la secuencia, que se utiliza para imprimir toda la secuencia.

main () se usa para ejecutar el caso de prueba simple: {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}.

#include <vector>
using std::vector;
int LIS(const vector<int> &v) {
  int size = v.size(), max_len = 1;
  // M[i] is the index of the last element of the sequence whose length is i
  int *M = new int[size];
  // P[i] is the index of the previous element of i in the sequence, which is used to print the whole sequence
  int *P = new int[size];
  M[0] = 0; P[0] = -1;
  for (int i = 1; i < size; ++i) {
    if (v[i] > v[M[max_len - 1]]) {
      M[max_len] = i;
      P[i] = M[max_len - 1];
      ++max_len;
      continue;
    }
    // Find the position to insert i using binary search
    int lo = 0, hi = max_len - 1;
    while (lo <= hi) {
      int mid = lo + ((hi - lo) >> 1);
      if (v[i] < v[M[mid]]) {
        hi = mid - 1;
      } else if (v[i] > v[M[mid]]) {
        lo = mid + 1;
      } else {
        lo = mid;
        break;
      }
    }
    P[i] = P[M[lo]];  // Modify the previous pointer
    M[lo] = i;  
  }
  // Print the whole subsequence
  int i = M[max_len - 1];
  while (i >= 0) {
    printf("%d ", v[i]);
    i = P[i];
  }
  printf("/n");
  delete[] M, delete[] P;
  return max_len;
}
int main(int argc, char* argv[]) {
  int data[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
  vector<int> v;
  v.insert(v.end(), data, data + sizeof(data) / sizeof(int));
  LIS(v);
  return 0;
}

Answer 3

Tarde en la fiesta, pero aquí hay una implementación de JavaScript para acompañar a los demás ... :)

var findLongestSubsequence = function(array) {
  var longestPartialSubsequences = [];
  var longestSubsequenceOverAll = [];

  for (var i = 0; i < array.length; i++) {
    var valueAtI = array[i];
    var subsequenceEndingAtI = [];

    for (var j = 0; j < i; j++) {
      var subsequenceEndingAtJ = longestPartialSubsequences[j];
      var valueAtJ = array[j];

      if (valueAtJ < valueAtI && subsequenceEndingAtJ.length > subsequenceEndingAtI.length) {
        subsequenceEndingAtI = subsequenceEndingAtJ;
      }
    }

    longestPartialSubsequences[i] = subsequenceEndingAtI.concat();
    longestPartialSubsequences[i].push(valueAtI);

    if (longestPartialSubsequences[i].length > longestSubsequenceOverAll.length) {
      longestSubsequenceOverAll = longestPartialSubsequences[i];
    }
  }

  return longestSubsequenceOverAll;
};

Answer 4

Un problema más simple es encontrar la longitud de la subsecuencia creciente más larga. Puedes enfocarte en entender ese problema primero. La única diferencia en el algoritmo es que no usa el conjunto P.

x es la entrada de una secuencia, por lo que se puede inicializar como: x = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

m realiza un seguimiento de la mejor subsecuencia de cada longitud encontrada hasta el momento. El mejor es el que tiene el valor final más pequeño (lo que permite agregar un rango más amplio de valores después). La longitud y el valor final son los únicos datos que se deben almacenar para cada subsecuencia.

Cada elemento de m representa una subsecuencia. Para m [j] ,

• j es la longitud de la subsecuencia.
• m [j] es el índice (en x ) del último elemento de la subsecuencia.
• entonces, x [m [j]] es el valor del último elemento de la subsecuencia.

L es la longitud de la subsecuencia más larga encontrada hasta ahora. Los primeros valores L de m son válidos, el resto no están inicializados. m puede comenzar con el primer elemento siendo 0, el resto sin inicializar. L aumenta a medida que se ejecuta el algoritmo, y también lo hace el número de valores inicializados de m .

Aquí hay un ejemplo de ejecución. x [i] , ym al final de cada iteración se da (pero los valores de la secuencia se usan en lugar de índices).

La búsqueda en cada iteración está buscando dónde colocar x [i] . Debería estar lo más a la derecha posible (para obtener la secuencia más larga) y ser mayor que el valor a la izquierda (por lo que es una secuencia creciente).

 0:  m = [0, 0]        - ([0] is a subsequence of length 1.)
 8:  m = [0, 0, 8]     - (8 can be added after [0] to get a sequence of length 2.)
 4:  m = [0, 0, 4]     - (4 is better than 8. This can be added after [0] instead.)
 12: m = [0, 0, 4, 12] - (12 can be added after [...4])
 2:  m = [0, 0, 2, 12] - (2 can be added after [0] instead of 4.)
 10: m = [0, 0, 2, 10]
 6:  m = [0, 0, 2, 6]
 14: m = [0, 0, 2, 6, 14]
 1:  m = [0, 0, 1, 6, 14]
 9:  m = [0, 0, 1, 6, 9]
 5:  m = [0, 0, 1, 5, 9]
 13: m = [0, 0, 1, 5, 9, 13]
 3:  m = [0, 0, 1, 3, 9, 13]
 11: m = [0, 0, 1, 3, 9, 11]
 7:  m = [0, 0, 1, 3, 7, 11]
 15: m = [0, 0, 1, 3, 7, 11, 15]

Ahora sabemos que hay una subsecuencia de longitud 6, que termina en 15. Los valores reales en la subsecuencia se pueden encontrar almacenándolos en la matriz P durante el ciclo.

Recuperando la mejor subsecuencia:

P almacena el elemento anterior en la subsecuencia más larga (como un índice de x), para cada número, y se actualiza a medida que avanza el algoritmo. Por ejemplo, cuando procesamos 8, sabemos que viene después de 0, así que almacena el hecho de que 8 está después de 0 en P. Puede trabajar hacia atrás desde el último número como una lista enlazada para obtener toda la secuencia.

Entonces, para cada número, sabemos el número que vino antes. Para encontrar la subsecuencia que termina en 7, miramos a P y vemos que:

7 is after 3
3 is after 1
1 is after 0

Entonces tenemos la subsecuencia [0, 1, 3, 7].

Las subsecuencias que terminan en 7 o 15 comparten algunos números:

15 is after 11
11 is after 9
9 is after 6
6 is after 2
2 is after 0

Así que tenemos las subsecuencias [0, 2, 6, 9, 11] y [0, 2, 6, 9, 11, 15] (la subsecuencia que aumenta más tiempo)

Answer 5

Una de las mejores explicaciones para este problema es el sitio MIT. http://people.csail.mit.edu/bdean/6.046/dp/

Espero que aclare todas tus dudas.

Answer 6

basado en la respuesta de FJB, implementación de Java:

public class Lis {

private static int[] findLis(int[] arr) {
    int[] is = new int[arr.length];
    int index = 0;
    is[0] = index;

    for (int i = 1; i < arr.length; i++) {
        if (arr[i] < arr[is[index]]) {
            for (int j = 0; j <= index; j++) {
                if (arr[i] < arr[is[j]]) {
                    is[j] = i;
                    break;
                }
            }
        } else if (arr[i] == arr[is[index]]) {

        } else {
            is[++index] = i;
        }
    }

    int[] lis = new int[index + 1];
    lis[index] = arr[is[index]];

    for (int i = index - 1; i >= 0; i--) {
        if (is[i] < is[i + 1]) {
            lis[i] = arr[is[i]];
        } else {
            for (int j = is[i + 1] - 1; j >= 0; j--) {
                if (arr[j] > arr[is[i]] && arr[j] < arr[is[i + 1]]) {
                    lis[i] = arr[j];
                    is[i] = j;
                    break;
                }
            }
        }
    }

    return lis;
}

public static void main(String[] args) {
    int[] arr = new int[] { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11,
            7, 15 };
    for (int i : findLis(arr)) {
        System.out.print(i + "-");
    }
    System.out.println();

    arr = new int[] { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 };
    for (int i : findLis(arr)) {
        System.out.print(i + "-");
    }
    System.out.println();
}

}

Answer 7

podemos implementarlo en dos 2d array como secuencia es

 8    2     4
 0    7     1
 3    7     9

y LIS es 0 -> 2 -> 4 -> 7 -> 8 y ¿qué es el algoritmo para esto?