Reconstrucción de un árbol a partir de consultas de separador

18

Supongamos que es un árbol de grado constante cuya estructura no conocemos. El problema es generar el árbol haciendo preguntas de la forma: "¿El nodo encuentra en la ruta del nodo al nodo ?". Suponga que cada consulta puede ser respondida en tiempo constante por un oráculo. Conocemos el valor de , el número de nodos en el árbol. El objetivo es minimizar el tiempo necesario para generar el árbol en términos de .T x a b n nTTxabnn

¿Existe un algoritmo para el problema anterior?o(n2)

Suponga que el grado de cualquier nodo en es como máximo 3.T


Lo que yo sé

La caja de diámetro acotado es fácil . Si el diámetro del árbol es , entonces podemos obtener un algoritmo de divide y vencerás:D

Cualquier árbol binario tiene un buen separador que divide el árbol en componentes de tamaño no menor a 1 / 3n.

  1. Elige cualquier vértice x. Si es un buen separador etiqueta eso y recurse.
  2. Encuentra los 3 vecinos de x.
  3. Muévase en la dirección del vecino que tiene el mayor número de nodos. Repita el paso 2 con el vecino.

Dado que encontrar el separador toma en la mayoría de los pasos , obtenemos un algoritmo .O ( n D log n )DO(nDlogn)

Un algoritmo aleatorioO(nlog2n) . (movido de los comentarios a continuación)

Elige dos vértices x e y al azar. Con 1/9 de probabilidad, se acostarán en los lados opuestos de un separador. Elija el nodo central de la ruta de a . Vea si es un separador, si no, haga una búsqueda binaria.yxy

tarda el tiempo esperado en encontrar el separador. Entonces obtenemos un algoritmo aleatorio .O ( nO(nlogn)O(nlog2n)


Antecedentes. Aprendí sobre este problema de un amigo que trabaja en modelos gráficos probabilísticos. El problema anterior corresponde aproximadamente al aprendizaje de la estructura de un árbol de unión usando un oráculo que, dadas tres variables aleatorias X, Y y Z, puede indicar el valor de la información mutua entre X e Y dado el valor de Z. Si el valor está cerca a cero, podemos suponer que Z se encuentra en el camino de X a Y.

Jagadish
fuente
77
Por favor, revele lo que ya sabe sobre el problema, para que no perdamos nuestro tiempo reinventando la rueda.
Jeffε
@ Jɛ ff E He editado mi pregunta.
Jagadish

Respuestas:

5

No. La siguiente estrategia adversa simple implica que cualquier algoritmo para reconstruir un árbol de nodos requiere al menos consultas de "intermediación".n(n12)=n(n1)/2

Etiquete arbitrariamente los nodos . El adversario responde todas las consultas como si el árbol fuera una estrella con el vértice en el centro; piense en como la raíz y los otros nodos como sus hijos.0,1,2,,n100

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

Ahora suponga que el algoritmo se detiene después de realizar menos de consultas. Entonces debe haber dos vértices y , ninguno igual a cero, de modo que el algoritmo no haya consultado ninguna permutación del triple . Si el algoritmo afirma que el árbol no es una estrella con centro , el adversario revela su entrada, demostrando que el algoritmo está equivocado. El adversario luego revela que es en realidad el único hijo de , lo que demuestra que el algoritmo está equivocado nuevamente.n(n1)/2yz(0,y,z)0xy

Actualización: Vaya, acabo de notar la restricción de grado. Afortunadamente, este no es un obstáculo importante. Reemplace el nodo con su árbol binario favorito, con los otros nodos como hojas en un orden desconocido, y luego revele este subárbol al algoritmo de reconstrucción. La reconstrucción del árbol binario resultante -nodo todavía requiere al menos consultas. De manera equivalente, la reconstrucción de un árbol binario -node requiere al menos consultas. (Estoy seguro de que una construcción más sutil mejoraría la constante).0n1(2n3)n(n1)/2m(m+3)(m+2)/8 Como señala Jagadish, esta generalización no funciona; Las consultas sobre nodos internos en el árbol imponen un orden en las hojas, lo que reduce el número de consultas necesarias.

Jeffε
fuente
Mi pregunta es sobre árboles de grado constante. Este argumento no funciona para ese caso, ¿verdad?
Jagadish
2
@Jagadish: (1) No creo que esta prueba de un límite inferior funcione para algoritmos aleatorios. El adversario aún puede construir un ejemplo fallido, pero eso no contradice la hipótesis de que el algoritmo aleatorio funciona correctamente con alta probabilidad. (2) Por cierto, parece que hiciste la pregunta sabiendo la respuesta. ¿Para qué hiciste eso?
Tsuyoshi Ito
2
Veo. ¡Gracias por la explicación, y también por editar la pregunta!
Tsuyoshi Ito
44
Si tiene un algoritmo aleatorio, entonces tiene un algoritmo. El determinismo está sobrevalorado.
Jeffε
1
Este problema me recuerda la clasificación / combinación de tuercas y tornillos. Un algoritmo aleatorio que se ejecuta en tiempo con alta probabilidad es fácil: es solo una selección rápida aleatoria . Hay un algoritmo determinista de tiempo , pero es realmente no trivial . O(nlogn)O(nlogn)
Jeffε
5

Anindya Sen y yo tenemos un artículo en ALT '13 donde damos un algoritmo para este problema. No sabemos si es posible un mejor algoritmo.O~(nn)

Jagadish
fuente