Buscando bolas etiquetadas bajo restricciones

Question

(Esta es una modificación de este problema.)

Ha $k$ bolas blancas y $k$ bolas negras, y saben que exactamente uno de cada color es radiactivo. Usted puede colocar cualquier número de bolas de su elección en un detector de radiación que se revela sólo si $0$, $1$ o $2$ medido bolas son radiactivos.

Especificar un algoritmo que identifica los dos radiactivos bolas en el menor número de mediciones, tales como sea posible en el peor de los casos.

---

Algunas ideas:

La incertidumbre total en el sistema inicial, en bits, es $\log_2 k + \log_2 k = 2 \log_2 k = \log_2 k^2$.

(Generado por un comentario por @leonbloy.) La selección es un proceso de Bernoulli y la mayoría de la información que se puede obtener es $3/2$ bits. Por lo tanto, en principio, el número total de medidas necesarias está delimitada por:

$$\left\lceil \frac{2\log_2 k}{3/2}\right \rceil.$$

Aquí es un árbol de decisión para el pequeño estuche $k=2$. Etiquetamos las bolas $b_1, b_2, w_1, w_2$ y la primera medida $b_1$ con $w_1$. (Estoy bastante seguro de que pruebas uno negro y uno blanco proporciona el máximo de información). Los arcos indican el resultado de la medición. En el caso de $0$ o $2$ detectado radiactivos bolas, hemos terminado y el rojo en caja hojas son nuestras respuestas.

Si el resultado es $1$, a continuación, medir $b_1 w_2$ que sólo puede dar un $0$ o $2$ salida, y nuestras conclusiones finales se muestran en la parte inferior de sus hojas.

El número esperado de las mediciones es ${\cal E}[m] = \frac{1}{2} \cdot 1 + \frac{1}{2} \cdot 2 = 1.5$.

Por supuesto que hay otras maneras de garantizar una respuesta en dos mediciones, por ejemplo, una medición en un solo negro, luego una medición en un único blanco. Pero que el algoritmo garantiza que usted tendrá dos mediciones, yo.e, ${\cal E}[m] = 2$. (Hay que admitir que ambos algoritmos tienen el mismo peor de los casos el rendimiento.) El árbol de decisión de arriba te da una respuesta la mitad del tiempo con un solo de medición--explota más de las tres vías de respuesta que una de dos vías de respuesta.

(Tengo la sensación de que este problema ha sido resuelto en la literatura, pero no lo pude encontrar en SÍ, ni con una rápida búsqueda en línea).

Answer 1

El siguiente algoritmo encuentra radiactivos bolas en $\mathcal O(\log_\phi k)=\mathcal O(1.44\log_2 k)$ pruebas, en el peor. Cada prueba se elimina $2/1.44\approx 1.39$ bits de incertidumbre en promedio.

Supongamos primero que $k=F_n$ es un número de Fibonacci. Deje $S_n$ ser el estado donde hay $F_n$ bolas blancas y $F_n$ bolas negras que podría ser radiactivos.

Si usted está en el estado $S_n$, la prueba de $F_{n-1}$ bolas negras y $F_{n-1}$ bolas blancas.

• Si hay dos radiactivos bolas, nos movemos en el estado de $S_{n-1}$.

• Si hay cero radiactivos bolas, nos movemos en el estado de $S_{n-2}$.

• Si hay una radiactivos pelota, entonces no se $2 \times F_{n-1}\times F_{n-2}$ posibilidades. Las bolas blancas y bolas negras se dividen en grupos de tamaño $F_{n-1}$ e $F_{n-2}$ , de manera que un color tiene su radiactivos pelota en el gran conjunto, y el otro tiene su radiactivos de la bola en el pequeño conjunto. Llaman a este estado $T_{n-1}$.

Supongamos que usted está en el estado de $T_{n}$, por lo que la bola blanca y negra bolas en dos partes de tamaño $F_n$ e $F_{n-1}$, de modo que uno radiactivos de bola es en gran parte una de la otra en una pequeña parte. Prueba de $F_{n-1}$ bolas blancas de la gran parte, todas las bolas negras de la parte pequeña, y $F_{n-2}$ bolas negras de la gran parte (ver el diagrama para una buena visualización).

• Si hay dos radiactivos bolas, nos movemos en el estado de $S_{n-1}$.

• Si hay cero radiactivos bolas, nos movemos en el estado de $S_{n-1}$.

• Si hay una radiactivos pelota, nos movemos en el estado de $T_{n-1}$.

Comenzamos en el estado de $S_n$, y de $S_k$ o $T_k$ nos movemos a $S_{k-1}$ o $T_{k-1}$ en el peor. Por lo tanto, después de que en la mayoría de las $n-2$ pruebas, vamos a estar en cualquiera de las $S_2$, en cuyo caso hemos terminado, o $T_2$, caso en el cual una prueba más es suficiente. Por lo tanto, podemos solucionar $k=F_n$ en la mayoría de los $n-1$ pruebas.

En general, si $k$ no es un número de Fibonacci, entonces podemos agregar "dummy" de bolas para hacer de él un número de Fibonacci, por lo $n-1$ pruebas suficientes donde $n$ es el entero más pequeño para $F_n\ge k$.

Utilizando la aproximación de $F_n\approx \frac1{\sqrt 5}\phi^n$, se puede calcular el peor de los casos el número de pruebas como una función de la $k$ casi exactamente: \begin{align} F_{n-1}<k\le F_n &\implies \frac1{\sqrt5}\phi^{n-1}\lesssim k\lesssim\frac1{\sqrt5}\phi^{n} \\&\implies \log_\phi(k\sqrt{5})\lesssim n\lesssim \log_\phi(k\sqrt{5})+1 \\&\implies n \approx \Big\lceil \log_\phi k+\log_\phi\sqrt{5}\Big\rceil \\&\implies \text{# tests}=n-1 \approx \Big\lceil \log_\phi k+0.672\Big\rceil \end{align}

Answer 2

Sub-óptimo de los intentos. Esperemos que otros pueden mejorar estos...

Supongamos por ahora $k=2^m$, es decir, $k$ es una potencia de $2$.

Algoritmo de $A$ se basa en el $(1/4, 1/2, 1/4)$ split sugerido por @leonbloy. Mi aporte aquí es meramente a su vez la división en un algoritmo recursivo.

Desde $(1/4, 1/2, 1/4) \rightarrow 1.5$ bits, esto sugiere un promedio de no. de rondas de ${\log_2 k^2 \over 1.5} = {4\over 3} \log_2 k$. Desde el mayor subconjunto tiene el tamaño de $1/2$, esto también sugiere un peor de los casos no. de rondas de $\log_2 k^2 = 2 \log_2 k$. Sin embargo, estos dos son solo baja-límites -, su viabilidad depende de que la búsqueda de un real algoritmo.

Algoritmo de $A$ consigue ${3\over 2} \log_2 k$ promedio (peor que la ${4\over 3}$ unido), y $2 \log_2 k$ peor de los casos (igual a la de la envolvente).

Algoritmo: la Partición de las bolas blancas en dos mitades $W_1, W_2$ y las bolas negras en dos mitades $B_1, B_2$. Prueba de $W_1 \cup B_1$.

• Si el resultado de la prueba $=0$, sabemos que el radiactivos bolas en $W_2, B_2$. Hemos reducido el problema a la mitad el tamaño de la $k \rightarrow k/2$ en una prueba.

• Si el resultado de la prueba $=2$, sabemos que el radiactivos bolas en $W_1, B_1$. Hemos reducido el problema a la mitad el tamaño de la $k \rightarrow k/2$ en una prueba.

• Si el resultado de la prueba $=1$, luego probamos $W_1$. (Nota: este es un punto de ineficiencia.) Si el nuevo resultado de la prueba de $=1$, sabemos que el radiactivos bolas en $W_1, B_2$. Si el nuevo resultado de la prueba de $=0$, sabemos que el radiactivos bolas en $W_2, B_1$. En cualquier caso, hemos reducido el problema a la mitad el tamaño de la $k \rightarrow k/2$ en dos pruebas.

I. e., cuando la reducción de la $k \rightarrow k/2$, necesitamos $1$ prueba (prob $=1/2$) o $2$ pruebas (prob $=1/2$). Hay $m= \log_2 k$ tal "rondas", cada necesidad de $1$ o $2$ pruebas, y cada ronda es independiente. El promedio de casos ${3\over 2} m$ y el peor de los casos $2m$ seguir inmediatamente.

Si $k$ no es una potencia de $2$, entonces no. de rondas $m= \lceil log_2 k \rceil$. Resulta que (álgebra omitido), si dividimos las bolas tan uniformemente como sea posible, prob de la necesidad de $1$ prueba de $\ge 1/2 \ge$ prob de la necesidad de $2$ pruebas, por lo que el promedio-el caso es, de hecho, muy ligeramente mejor que el ${3\over 2} m$.

---

ACTUALIZACIÓN: Después de meditar durante una hora o así, he aquí un mejor Algoritmo de $B$.

Logra el peor de los casos de $1.63 \log_2 k$ y un promedio de caso de $1.32 \log_2 k$. Ambos de estos crecimientos son mejores (es decir, más lento) que el "menor de los límites" predicho por la $(1/4,1/2,1/4)$ divisiones ( $2 \log_2 k$ e ${4 \over 3} \log_2 k$ respectivamente) debido a que el algoritmo de $B$ consigue $(1/3, 1/3, 1/3)$ se divide en algunas de las pruebas.

Asumir de nuevo por ahora $k=2^m$.

Hay dos etapas. En la primera etapa, se ejecuta exactamente $m$ pruebas. Deja que el blanco bolas de ser nombrado por $m$-vectores de bits $\{0,1\}^m$, y lo mismo para las bolas negras.

Para $j \in \{1, 2, ..., m\}$, el número de la prueba $j$ tendrá todas las bolas (blanco y negro), cuyas $j$th bits es $1$. I. e. habrá la mitad de las bolas blancas y la mitad de las bolas negras, por lo tanto la implementación de un $(1/4, 1/2, 1/4)$ split.

• Si el resultado de la prueba $=0$, sabemos radiactiva de las pelotas tienen la $j$th bits $0$.

• Si el resultado de la prueba $=2$, sabemos radiactiva de las pelotas tienen la $j$th bits $1$.

• Si el resultado de la prueba $=1$, sabemos que los dos radiactivos bolas $j$th valores de los bits que son diferentes. I. e. la bola blanca ha $0$ y la bola negra ha $1$, o viceversa, en el $j$th poco.

Y el final de esta primera etapa (todos los $m$ pruebas), podemos recoger los resultados en un $m$-símbolo vector $\{0, 1, ?\}^m$. Por ejemplo: $01??1?0$. En este ejemplo, sabemos que el comienzo de dos bits se $01$, $5$th bits es $1$, y el último bit es $0$. No sabemos bits en las posiciones $j = 3, 4, 6$ pero sabemos que, cualquiera que estos valores son para el blanco radiactivos de la pelota, los valores para el color negro radiactivos bola son la negación bit a bit. E. g. si el blanco radiactivos de bolas resulta ser $01\color{red}{00}1\color{red}{1}0$ luego el negro radiactivos pelota debe ser $01\color{blue}{11}1\color{blue}{0}0$. Vamos a llamar dos bolas de socios -- ellos son radiactivos o no radiactivos.

Así que se puede ejecutar de una manera muy eficiente de la segunda etapa: Vamos a $X$ ser la número indeterminado de bits (número de $?$ símbolos). Deje $P =$ el conjunto de candidatos para radiactivos bolas blancas, e inicialmente $|P| = 2^X$. Divida $P$ en tres grupos iguales (tan iguales como sea posible) $A,B,C$. Prueba bolas blancas en $A \cup B$ y bolas negras que son socios de $A$.

• Si el resultado de la prueba $=2, 1, 0$ respectivamente, entonces la radiactivos bola blanca es $\in A, B, C$ respectivamente.

Así, podemos reducir el tamaño del conjunto candidato por un factor de $3$ cada vez.

Peor de los casos de análisis: En el peor de los casos, todos los $m$ pruebas de la primera etapa devuelven un $?$. A continuación, la segunda etapa se requiere de $\log_3 2^m = m \log_3 2$ pruebas. El total es de $m (1 + \log_3 2) \approx 1.63 m = 1.63 \log_2 k$.

Media-análisis de caso: yo no estoy absolutamente seguro de que el siguiente es ACEPTAR, pero aquí va... la segunda etapa se requiere de $\log_3 2^X = X \log_3 2$ pruebas, donde $X \sim Binomial(m, 1/2)$. Por lo tanto $E[X] = m/2$ y el promedio del número total de pruebas es $m + {m \over 2} \log_3 2 \approx 1.32 m = 1.32 \log_2 k$.

El hecho de que en algunas de las pruebas que no se dividen de forma regular (por ejemplo, en $A,B,C$)... me imagino que puede ser manejado por la adición de $O(1)$ a los crecimientos, pero soy demasiado perezoso para atrapar a los de abajo, por ahora.