Suponha que é uma árvore de grau constante cuja estrutura não conhecemos. O problema é produzir a árvoreTTTT , solicitando consultas no formulário: "O nó xx fica no caminho do nó aa ao nó bb ?". Suponha que cada consulta possa ser respondida em tempo constante por um oráculo. Sabemos o valor de nn , o número de nós na árvore. O objetivo é minimizar o tempo necessário para produzir a árvore em termos de nn .
Existe um algoritmo o(n2)o(n2) para o problema acima?
Suponha que o grau de qualquer nó em TT seja no máximo 3.
A caixa com diâmetro limitado é fácil . Se o diâmetro da árvore for DD , 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.
Escolha qualquer vértice x. Se é um bom separador rotule isso e recorra.
Encontre todos os 3 vizinhos de x.
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 DD etapas, obtemos um algoritmo O(nDlogn)O(nDlog⁡n) .
Um O(nlog2n)O(nlog2⁡n) 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 xx a yy . Veja se é um separador, se não fizer pesquisa binária.
Leva O(nlogn)O(nlog⁡n) tempo esperado para encontrar o separador. Então obtemos umO(nlog2n)O(nlog2⁡n) 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.
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
Não. A seguinte estratégia simples de adversário implica que qualquer algoritmo para reconstruir uma árvore de nodos requer pelo menos ( n - 1nnconsultas "intermediárias".(n−12)=n(n−1)/2(n−12)=n(n−1)/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,…,n−10,1,2,…,n−10000
n(n−1)/2n(n−1)/2yyzz(0,y,z)(0,y,z)00xxyy
00n−1n−1(2n−3)(2n−3)n(n−1)/2n(n−1)/2mm(m+3)(m+2)/8(m+3)(m+2)/8
Minha pergunta é sobre árvores de grau constante. Esse argumento não funciona para esse caso, certo?
@ 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?