Antecedentes
Un árbol de decisión binario es un árbol enraizado donde cada nodo interno (y raíz) está etiquetado por un índice modo que ninguna ruta de raíz a hoja repita un índice, las hojas están etiquetados por salidas en , y cada borde está etiquetado por para el hijo izquierdo y para el hijo derecho. Para aplicar un árbol a una entrada :j ∈ { 1 , . . . , n } { A , B } 0 1 x
- Comience en la raíz
- si está en la hoja, imprime la etiqueta de la hoja o y termina
- Lea la etiqueta de su nodo actual, si luego muévase al hijo izquierdo y si luego muévase al hijo derecho.
- saltar al paso (2)
El árbol se usa como una forma de evaluar funciones, en particular decimos que un árbol representa una función total si para cada tenemos . La complejidad de la consulta de un árbol es su profundidad, y la complejidad de la consulta de una función es la profundidad del árbol más pequeño que lo representa.
Problema
Dado un árbol de decisión binario T, sale un árbol de decisión binario T 'de profundidad mínima de tal manera que T y T' representan la misma función.
Pregunta
¿Cuál es el algoritmo más conocido para esto? ¿Se conocen límites inferiores? ¿Qué pasa si sabemos que la ? ¿Qué pasa si solo requerimos que tenga aproximadamente una profundidad mínima?
Enfoque ingenuo
El enfoque ingenuo se da para enumerar de forma recursiva todos los árboles de decisión binarios de profundidad d - 1 mientras se prueba si se evalúan a lo mismo que t . Esto parece requerir O ( d 2 n n !pasos (suponiendo que se necesitandpasos para verificar quéT(x)evalúa para unaxarbitraria). ¿Hay un mejor enfoque?
Motivación
Esta pregunta está motivada por una pregunta previa sobre el equilibrio entre la complejidad de la consulta y la complejidad del tiempo . En particular, el objetivo es limitar la separación de tiempo para las funciones totales. Podemos hacer un árbol partir de un algoritmo de tiempo óptimo con tiempo de ejecución t , y luego nos gustaría convertirlo en un árbol T ' para un algoritmo de consulta óptimo. Desafortunadamente, si t ∈ O ( n ! / ( N - d ) ! ) (Y a menudo d ∈ Θ ( n )) el cuello de botella es la conversión. ¡Sería bueno si pudiéramos reemplazar por algo como 2 d .
fuente
Respuestas:
Tengo 3 respuestas, todas dando resultados de dureza algo diferentes.
Sea alguna función.f:{0,1}n→{0,1}
respuesta 1
Dado un árbol de decisión calcula fy un número, es NP-difícil saber si existe un árbol de decisión T 'que computa f de tamaño como máximo ese número.T f T′ f ( Zantema y Bodlaender '00 )
Respuesta 2
Dado un árbol de decisión computa f , es NP difícil aproximar el árbol de decisión más pequeño que computa f a cualquier factor constante.T f f ( Sieling '08 )
Respuesta 3
Sea el tamaño del árbol de decisión más pequeño que computa f . Dado un árbol de decisión T que calcula f , suponiendo N P ⊊ D T I M E ( 2 n ϵ ) para algunos ϵ < 1 , no se puede encontrar un árbol de decisión equivalente T ' de tamaño s k para cualquier k ≥ 0 .s f T f NP⊊DTIME(2nϵ) ϵ<1 T′ sk k≥0
Creo que esta respuesta más sólida (que se basa en una suposición más débil) puede hacerse a partir de resultados conocidos en la teoría del aprendizaje de algoritmos de Occam para árboles de decisión, a través del siguiente argumento:
Estos dos resultados parecen implicar un resultado de dureza para su problema. Por un lado (1), podemos encontrar un gran árbol de decisión; por otro lado (2), no deberíamos poder minimizarlo para obtener un equivalente "pequeño", de tamaño , incluso cuando exista uno de tamaño s .sk s
fuente