Estoy considerando un problema que parece muy clásico pero no tengo idea de dónde encontrar los resultados relacionados. Cualquier ayuda o comentario será apreciado.
Dado un conjunto no vacío $S$ , un conjunto $Q$ de los subconjuntos de $S$ y un elemento fijo desconocido $x\in S$ Podemos hacer sólo un tipo de preguntas para determinar $x$ : es $x$ en $A$ ? ( $A\in Q$ que es un subconjunto de $S$ ).
Por ejemplo, dejemos que $S=\{1,2,3\},Q=\{\{1,2\},\{2,3\},\{1\}\},x=2$ entonces podemos ir de la siguiente manera,
- preguntar "¿es $x$ en $\{1,2\}$ ?", se le responde "sí"
- preguntar "¿es $x$ en $\{2,3\}$ ?", se le responde "sí"
Entonces sabemos $x$ debe ser 2 y detener el proceso de consulta.
Ahora bien, si $x\in S$ es una variable aleatoria asociada a una función de probabilidad $f$ definido en $S$ ¿Cuál es el árbol de consulta óptimo? Por ser óptimo, me refiero al árbol de consulta que tiene el mínimo número esperado de consultas antes de determinar la respuesta.
De hecho, si $Q$ es igual al conjunto de potencias de $S$ entonces el árbol de consulta óptimo es simplemente el Árbol de búsqueda binaria óptima . Lo difícil es saber cuál es el árbol de búsqueda óptimo si las preguntas que podemos hacer están limitadas a un determinado conjunto $Q$ ?
