Suponha que é uma árvore de grau constante cuja estrutura não conhecemos. O problema é produzir a árvore , solicitando consultas no formulário: "O nó fica no caminho do nó ao nó ?". Suponha que cada consulta possa ser respondida em tempo constante por um oráculo. Sabemos o valor de , o número de nós na árvore. O objetivo é minimizar o tempo necessário para produzir a árvore em termos de .
Existe um algoritmo para o problema acima?
Suponha que o grau de qualquer nó em seja no máximo 3.
O que eu sei
A caixa com diâmetro limitado é fácil . Se o diâmetro da árvore for , 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 etapas, obtemos um algoritmo .
Um 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 a . Veja se é um separador, se não fizer pesquisa binária.
Leva tempo esperado para encontrar o separador. Então obtemos um 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.
Respostas:
Não. A seguinte estratégia simples de adversário implica que qualquer algoritmo para reconstruir uma árvore de nodos requer pelo menos ( n - 1n consultas "intermediárias".(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−1 0 0
fonte
fonte