Subseqüência crescente mais longa - Longest increasing subsequence

Em ciência da computação , o problema da subsequência crescente mais longa é encontrar uma subsequência de uma dada sequência na qual os elementos da subsequência estão em ordem classificada, do menor para o maior, e na qual a subsequência é a maior possível. Esta subsequência não é necessariamente contígua ou única. Mais longas subsequências crescentes são estudados no contexto de várias disciplinas relacionadas com a matemática , incluindo algorithmics , teoria matriz aleatória , a teoria da representação , e física . O maior problema de subseqüência crescente pode ser resolvido no tempo O ( n log n ), onde n denota o comprimento da seqüência de entrada.

Exemplo

Nos primeiros 16 termos da sequência binária de Van der Corput

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

uma subsequência crescente mais longa é

0, 2, 6, 9, 11, 15.

Esta subsequência tem comprimento seis; a sequência de entrada não tem subsequências crescentes de sete membros. A maior subsequência crescente neste exemplo não é a única solução: por exemplo,

0, 4, 6, 9, 11, 15

0, 2, 6, 9, 13, 15

0, 4, 6, 9, 13, 15

são outras subseqüências crescentes de igual comprimento na mesma seqüência de entrada.

Relações com outros problemas algorítmicos

O maior problema de subsequência crescente está intimamente relacionado ao problema de subsequência comum mais longo , que tem uma solução de programação dinâmica de tempo quadrático : a maior subsequência crescente de uma sequência S é a maior subsequência comum de S e T , onde T é o resultado da classificação S . No entanto, para o caso especial em que a entrada é uma permutação dos inteiros 1, 2, ..., n , essa abordagem pode ser muito mais eficiente, levando a limites de tempo da forma O ( n log log n ).

O maior clique em um gráfico de permutação corresponde à subsequência decrescente mais longa da permutação que define o gráfico (assumindo que a sequência original não permutada é classificada do valor mais baixo para o mais alto). Da mesma forma, o conjunto independente máximo em um gráfico de permutação corresponde à maior subsequência não decrescente. Portanto, os algoritmos de subsequência crescente mais longos podem ser usados ​​para resolver o problema do clique de forma eficiente em grafos de permutação.

Na correspondência de Robinson-Schensted entre permutações e tableaux de Young , o comprimento da primeira linha do tableau correspondente a uma permutação é igual ao comprimento da subsequência crescente mais longa da permutação, e o comprimento da primeira coluna é igual ao comprimento da mais longa subseqüência decrescente.

Algoritmos eficientes

O algoritmo descrito abaixo resolve o problema de subsequência crescente mais longo de forma eficiente com matrizes e busca binária . Ele processa os elementos da sequência em ordem, mantendo a maior subsequência crescente encontrada até agora. Denote os valores da sequência como etc. Então, após o processamento, o algoritmo terá os valores armazenados em duas matrizes: ${\ displaystyle X [0], X [1], \ ldots,}$${\ displaystyle X [i],}$

• ${\ displaystyle M [j]}$- armazena o índice do menor valor de forma que haja uma subsequência crescente de comprimento terminando no intervalo (é necessário tornar esta declaração mais clara ). Portanto, se denota o conjunto de todos os índices de modo que e existe uma subsequência crescente de comprimento terminando em (isto é, existem índices terminando em tal que ), então é o índice para o qual o seguinte é válido: e (ou equivalentemente, e para todo ). Observe que porque representa o comprimento da subsequência crescente e representa o índice de sua terminação.${\ displaystyle k}$${\ displaystyle X [k]}$${\ displaystyle j}$${\ displaystyle X [k]}$${\ displaystyle k \ leq i}$${\ displaystyle K_ {i, j}}$${\ displaystyle k}$${\ displaystyle k \ leq i}$${\ displaystyle j}$${\ displaystyle X [k]}$${\ displaystyle j}$${\ displaystyle l_ {1} <l_ {2} <\ cdots <l_ {j} = k}$${\ displaystyle k}$${\ displaystyle X \ left [l_ {1} \ right] \ leq X \ left [l_ {2} \ right] \ leq \ cdots \ leq X \ left [k \ right]}$${\ displaystyle M [j]}$${\ displaystyle M [j] \ in K_ {i, j}}$${\ displaystyle X [M [j]] = \ min _ {k \ in K_ {i, j}} X [k]}$${\ displaystyle M [j] \ in K_ {i, j}}$${\ displaystyle k \ in K_ {i, j},}$ ${\ displaystyle X [M [j]] \ leq X [k]}$${\ displaystyle j \ leq i + 1,}$${\ displaystyle j \ geq 1}$${\ displaystyle k \ geq 0}$
• ${\ displaystyle P [k]}$- armazena o índice do predecessor de na subsequência crescente mais longa terminando em${\ displaystyle X [k]}$${\ displaystyle X [k].}$

Além disso, o algoritmo armazena uma variável L representando o comprimento da maior subsequência crescente encontrada até agora. Como o algoritmo abaixo usa numeração baseada em zero , para maior clareza é preenchido com o que não é usado de modo que corresponda a uma subsequência de comprimento. Uma implementação real pode pular e ajustar os índices de acordo. ${\ displaystyle M}$${\ displaystyle M [0],}$${\ displaystyle M [j]}$${\ displaystyle j.}$${\ displaystyle M [0]}$

Observe que, em qualquer ponto do algoritmo, a sequência

está aumentando. Pois, se há uma subseqüência crescente de comprimento terminando em, então há também uma subsequência de comprimento terminando em um valor menor: a saber, aquela que termina em Assim, podemos fazer pesquisas binárias nesta sequência em tempo logarítmico. ${\ displaystyle j \ geq 2}$${\ displaystyle X [M [j]],}$${\ displaystyle j-1}$${\ displaystyle X [P [M [j]]].}$

O algoritmo, então, procede da seguinte forma:

P = array of length N
M = array of length N + 1

L = 0
for i in range 0 to N-1:
    // Binary search for the largest positive j ≤ L
    // such that X[M[j]] < X[i]
    lo = 1
    hi = L + 1
    while lo < hi:
        mid = lo + floor((hi-lo)/2)
        if X[M[mid]] < X[i]:
            lo = mid+1
        else:
            hi = mid

    // After searching, lo is 1 greater than the
    // length of the longest prefix of X[i]
    newL = lo

    // The predecessor of X[i] is the last index of 
    // the subsequence of length newL-1
    P[i] = M[newL-1]
    M[newL] = i
    
    if newL > L:
        // If we found a subsequence longer than any we've
        // found yet, update L
        L = newL

// Reconstruct the longest increasing subsequence
S = array of length L
k = M[L]
for i in range L-1 to 0:
    S[i] = X[k]
    k = P[k]

return S

Como o algoritmo realiza uma única pesquisa binária por elemento de sequência, seu tempo total pode ser expresso usando a notação Big O como O ( n  log  n ). Fredman (1975) discute uma variante desse algoritmo, que ele credita a Donald Knuth ; na variante que ele estuda, o algoritmo testa se cada valor pode ser usado para estender a sequência crescente mais longa atual, em tempo constante, antes de fazer a busca binária. Com esta modificação, o algoritmo usa no máximo n log ₂ n - n log ₂ log ₂ n + O ( n ) comparações no pior caso, que é ótimo para um algoritmo baseado em comparação até o fator constante no O ( n ) termo. ${\ displaystyle X [i]}$

Limites de comprimento

De acordo com o teorema de Erdős-Szekeres , qualquer sequência de n ² +1 inteiros distintos tem uma subsequência crescente ou decrescente de comprimento n + 1. Para entradas em que cada permutação da entrada é igualmente provável, o comprimento esperado do maior aumento subsequência é aproximadamente 2 √ n . No limite, conforme n se aproxima do infinito, o comprimento da maior subsequência crescente de uma sequência permutada aleatoriamente de n itens tem uma distribuição que se aproxima da distribuição Tracy-Widom , a distribuição do maior autovalor de uma matriz aleatória no conjunto unitário gaussiano .

Algoritmos online

A subsequência crescente mais longa também foi estudada na configuração de algoritmos online , em que os elementos de uma sequência de variáveis ​​aleatórias independentes com distribuição contínua F - ou alternativamente os elementos de uma permutação aleatória - são apresentados um de cada vez a um algoritmo que deve decidir se deseja incluir ou excluir cada elemento, sem conhecimento dos elementos posteriores. Nesta variante do problema, que permite aplicações interessantes em diversos contextos, é possível conceber um procedimento de seleção ótimo que, dada uma amostra aleatória de tamanho n como entrada, irá gerar uma sequência crescente com comprimento máximo esperado de tamanho aproximadamente √ 2n . O comprimento da subsequência crescente selecionada por este procedimento ótimo tem variância aproximadamente igual a √ 2n / 3 , e sua distribuição limite é assintoticamente normal após a centralização e escalonamento usuais. Os mesmos resultados assintóticos são válidos para limites mais precisos para o problema correspondente na configuração de um processo de chegada de Poisson. Um refinamento adicional na configuração do processo de Poisson é dado por meio da prova de um teorema do limite central para o processo de seleção ótimo que se mantém, com uma normalização adequada, em um sentido mais completo do que se esperaria. A prova produz não apenas o teorema do limite funcional "correto", mas também a matriz de covariância (singular) do processo tridimensional resumindo todos os processos em interação.

Aplicativo

• Parte do sistema MUMmer (localizador de correspondência máxima única) para alinhar genomas inteiros.
• Usado em sistemas de controle de versão como Git etc.
• Usado no Patience Diff, um algoritmo de diffing (calcula e exibe as diferenças entre o conteúdo dos arquivos), que é usado no “Bazaar” (Bazaar é um sistema de controle de versão que ajuda a rastrear o histórico do projeto ao longo do tempo e a colaborar facilmente com outros ..)

Veja também

• Classificação de paciência , uma técnica eficiente para encontrar o comprimento da subsequência crescente mais longa
• Monóide plático , um sistema algébrico definido por transformações que preservam o comprimento da maior subsequência crescente
• Anatoly Vershik , um matemático russo que estudou as aplicações da teoria dos grupos às subsequências crescentes mais longas
• Subseqüência comum mais longa
• Subsequência alternada mais longa

Referências

links externos

• Subseqüência mais longa e crescente do algoritmo
• Subseqüência de aumento mais longa simplificada
• Encontrando a contagem das subsequências aumentadas mais longas
• Dieta de poldo