Reconstruindo uma árvore a partir de consultas separadoras

18

Suponha que é uma árvore de grau constante cuja estrutura não conhecemos. O problema é produzir a árvoreTT , solicitando consultas no formulário: "O nó x fica no caminho do nó a ao nó b ?". Suponha que cada consulta possa ser respondida em tempo constante por um oráculo. Sabemos o valor de n , o número de nós na árvore. O objetivo é minimizar o tempo necessário para produzir a árvore em termos de n .

Existe um algoritmo o(n2) para o problema acima?

Suponha que o grau de qualquer nó em T seja no máximo 3.


O que eu sei

A caixa com diâmetro limitado é fácil . Se o diâmetro da árvore for D , podemos obter um algoritmo de dividir e conquistar:

Qualquer árvore binária possui um bom separador que divide a árvore em componentes de tamanho não inferior a 1 / 3n.

  1. Escolha qualquer vértice x. Se é um bom separador rotule isso e recorra.
  2. Encontre todos os 3 vizinhos de x.
  3. Mova na direção do vizinho que possui o maior número de nós. Repita a etapa 2 com o vizinho.

Como encontrar o separador leva no máximo D etapas, obtemos um algoritmo O(nDlogn) .

Um O(nlog2n) algoritmo aleatório. (movido dos comentários abaixo)

Escolha dois vértices x e y aleatoriamente. Com 1/9 de probabilidade, eles ficarão do lado oposto de um separador. Escolha o nó do meio do caminho de x a y . Veja se é um separador, se não fizer pesquisa binária.

Leva O(nlogn) tempo esperado para encontrar o separador. Então obtemos umO(nlog2n) algoritmo aleatório.


Fundo. Aprendi sobre esse problema com um amigo que trabalha em modelos gráficos probabilísticos. O problema acima corresponde aproximadamente a aprender a estrutura de uma árvore de junção usando um oráculo que, dadas três variáveis ​​aleatórias X, Y e Z, pode dizer o valor da informação mútua entre X e Y, dado o valor de Z. Se o valor estiver próximo para zero, podemos supor que Z esteja no caminho de X a Y.

Jagadish
fonte
7
Revele o que você já sabe sobre o problema, para não perdermos tempo reinventando a roda.
21412 Jefferson
@ Jɛ ff E editei minha pergunta.
21712 Jagadish

Respostas:

5

Não. A seguinte estratégia simples de adversário implica que qualquer algoritmo para reconstruir uma árvore de nodos requer pelo menos ( n - 1nconsultas "intermediárias".(n12)=n(n1)/2

Rotule arbitrariamente os nós . O adversário responde a todas as perguntas como se a árvore fosse uma estrela com o vértice 0 no centro; pense em 0 como raiz e os outros nós como filhos.0,1,2,,n100

Between?(a,x,b)
    if x=0 return TRUE else return FALSE

n(n1)/2yz(0,y,z)0xy

0n1(2n3)n(n1)/2m(m+3)(m+2)/8

Jeffε
fonte
Minha pergunta é sobre árvores de grau constante. Esse argumento não funciona para esse caso, certo?
Jagadish
2
@ Jagadish: (1) Eu não acho que essa prova de um limite inferior funcione para algoritmos aleatórios. O adversário ainda pode construir um exemplo falho, mas isso não contradiz a hipótese de que o algoritmo aleatório funcione corretamente com alta probabilidade. (2) A propósito, parece que você fez a pergunta sabendo a resposta. Por que você fez isso?
Tsuyoshi Ito
2
Entendo. Obrigado pela explicação, e também obrigado por editar a pergunta!
Tsuyoshi Ito
4
Se você tem um algoritmo aleatório, então você tem um algoritmo. O determinismo é superestimado.
Jeffε
1
O(nlogn)O(nlogn)
5

O~(nn)

Jagadish
fonte