Generalizações de pesquisa binária para posets?

28

Suponha que eu possua um poset "S" e um predicado monotônico "P" em S. Quero encontrar um ou todos os elementos máximos de S satisfazendo P.

EDIT : Estou interessado em minimizar o número de avaliações do P .

Quais algoritmos existem para esse problema e quais propriedades e operações adicionais eles exigem no S?

E os casos especiais importantes, como:

  • S é uma ordem linear - então a pesquisa binária regular funciona, desde que você tenha uma operação "find middle"
  • S é uma treliça
  • S é uma rede de subconjuntos
  • S é uma rede multiset
  • ...

Os dois últimos casos parecem particularmente importantes, por exemplo, para o experimento - você tem um conjunto de parâmetros booleanos ou reais e deseja encontrar a menor combinação possível deles que reproduza um padrão específico (por exemplo, um teste que falhou).

jkff
fonte
1
O que é a estrutura 'multiset'?
Suresh Venkat
1
É a rede cujos elementos são mapeamentos X -> N, meet é elemently min e join é elementwise max. Pode ser generalizado para qualquer rede em vez de N como o codomain.
JKFF

Respostas:

15

Não pensei muito nisso, por favor, corrija-me se estiver errado.

Digamos que é a largura do poset.w

  1. Para o poset que é a união de cadeias disjuntas, você precisa de pelo menos w log n avaliações de P aplicando apenas o limite inferior padrão na complexidade da consulta da pesquisa binária em cada cadeia.wwlognP

  2. Como você faz comparações gratuitamente, é possível calcular uma decomposição em cadeia do poset em cadeias gratuitamente. Fazer busca binária em cada cadeia para identificar o primeiro elemento que satisfaz P . Depois, revise os elementos identificados e remova os dominados. O número de avaliações de P é O ( w log n ) . Isso identifica todos os elementos máximos, pois pode haver no máximo um elemento máximo por cadeia.wPPO(wlogn)


ADICIONADO: Na verdade, estou vendo um algoritmo recursivo simples para fazer muito melhor ( ) para a rede dos subconjuntos 2 [ n ] ( EDIT : domotor descreveu a estratégia geral em sua resposta). Aqui estou assumindo que P é monotônico para baixo (ou seja, os subconjuntos { X : P ( X ) = 1 } formam um conjunto inferior), que é o que você quer dizer. Então, aqui está o algoritmo para encontrar um membro do conjunto inferior:O(n)2[n]P{X:P(X)=1}

a) Teste . Se 0, então pare.P()

b) Teste . P({n})

bi) Se 0, repita em (OK, pois nenhum conjunto contendo n pode estar no conjunto inferior).2[n1]n

b.ii) Se 1, existe um membro do conjunto inferior no sub-retículo . Esse sublatismo é isomórfico para 2 [ n - 1 ], para que mais uma vez possamos recuar. Mais precisamente, podemos executar o algoritmo para 2 [ n - 1 ] , mas quando o algoritmo pede para avaliar P ( Y ) , avaliamos P ( X ) onde X = Y { n } .{X:nX}2[n1]2[n1]P(Y)P(X)X=Y{n}

Assim, em cada passo, recessamos em um sublático que é metade do tamanho do original. No geral, precisamos avaliar no máximo 2 n vezes (na verdade, você pode implementar o algoritmo para avaliar o predicado n + 1 vezes, como Yoshio aponta, já que você só precisa verificar uma vez).P2nn+1

Sasho Nikolov
fonte
Uau, uma ideia tão simples! Graças - Eu vou dar um pouco sobre se este parece ideal ou não :)
JKFF
Na verdade, é ainda menor que w log n, já que a soma dos comprimentos da corrente é n. Eu acho que o máximo é em torno de w log (n / w).
Jkff #
OK, para ordens lineares, isso fornece pesquisa binária, para uma rede de subconjuntos, isso fornece C (n, n / 2) log (2 ^ n / C (n, n / 2)) ~ exp (n) * n. Não é muito rápido, mas também não parece ótimo, pois pode haver muitas respostas. No entanto, para encontrar um subconjunto maximal, você precisa de pesquisa binária em apenas qualquer uma cadeia - isso é ótimo e eu agora me chamar estúpido por não ter pensado nisso. Obrigado novamente!
JKFF
2
Eu acho que cadeias disjuntas fornecem um limite inferior de pelo menos w + log n (para algoritmos determinísticos). Pense em um adversário que "oculta" uma solução única na última cadeia consultada. Um limite inferior aleatório de Ω ( w ) deve seguir o princípio minimax de Yao. Encontrar um único elemento com complexidade w + log n pode ser interessante. ww+lognΩ(w)w+logn
Sasho Nikolov
1
@YanKingYin Uma treliça não pode ser a união de (mais de uma) cadeias separadas, porque cada um dos dois elementos deve ter um supremo. Um poset é uma união de cadeias disjuntas se puder ser particionado para que elementos de diferentes partes sejam incomparáveis ​​e elementos dentro da mesma parte admitam uma ordem total.
Sasho Nikolov
8

Um artigo recente de Daskalakis et al. Mostra que, para um poset de tamanho e largura w , elementos mínimos podem ser encontrados no tempo O ( w n ) . O interessante é que, em seu resumo, eles dizemnwO(wn)

Também seria interessante encontrar estruturas de dados estáticas e dinâmicas eficientes que desempenham o mesmo papel para pedidos parciais que montes e árvores de pesquisa binária desempenham para pedidos totais.

Suresh Venkat
fonte
Heh, parece não muito inspirador em comparação com log (n) :) mas, de qualquer forma, obrigado!
JKFF
Mas esse é o ponto. Sem estruturas de dados, você não pode obter log n mesmo para um conjunto totalmente ordenado, porque tudo o que você pode fazer é verificar. Na verdade, é uma pergunta muito boa tentar encontrar um equivalente de BST.
precisa
Bem - eu estou falando sobre a complexidade em termos do número de avaliações do predicado P, não do predicado de comparação.
Jkff 11/11
1
De certa forma, sim, mas isso está longe de ser a resposta completa - por exemplo, não fornece bissecção para os casos 1d ou 2d :) o que você sugere fazer com as raízes?
Jkff #
1
Ainda não tenho certeza. Pensando alto. Mas é uma excelente pergunta.
precisa
4

Se S faz parte da entrada, o problema de encontrar um elemento máximo já se torna `` NP-hard '' (se pensarmos na estrutura de tal forma que seus elementos sejam n bits de cadeia longa), por exemplo, você pode dizer se CNF (x) não for verdadeiro e CNF (y) for verdadeiro para algum CNF fixo.x<y

Além disso, pode haver muitos elementos máximos que satisfazem P; portanto, mesmo a saída de todos eles pode demorar muito, então acho que há apenas esperança de encontrar um máximo.

Em geral, a pesquisa binária funciona se você puder selecionar recursivamente elementos de forma que, depois de ficar com os elementos acima, ou os elementos acima sejam excluídos, e em todos esses conjuntos uma proporção fixa dos elementos seja excluída.

Por exemplo. se S é uma grade dimensional fixa, existe um algoritmo rápido: sempre reduza pela metade uma coordenada enquanto mantém as outras mínimas; portanto, pergunte, por exemplo, na primeira etapa (n / 2,0, ..., 0).

nd

domotorp
fonte
Receio não entender o primeiro parágrafo. Na sua redução, você tem todas as seqüências de n bits no poset S e elas são fornecidas como parte da entrada? Nesse caso, podemos passar por todas as strings no tempo polinomial.
Yoshio Okamoto
1
@ YoshioOkamoto: Eu acho que a suposição nesse parágrafo é que a comparação em S é dada como um circuito booleano. (Mas isso não tem nada a ver com a busca de uma poset e, portanto, não é interessante para mim.)
Tsuyoshi Ito
@Tsuyoshi: Obrigado. Isso faz muito sentido.
Yoshio Okamoto
4

P2[n]nPP

a3nm
fonte