Problema de programación dinámica

Question

Un hombre está en una habitación, con $n$ pasajes que conducen. Para el paso $i$, $i = 1,...,n$, hay probabilidad de $p_i$ de escape, $q_i$ de los asesinados y $r_i$ de regreso a la habitación, donde $p_i + q_i + r_i = 1$. El orden en que debe el hombre trate de los pasajes, así como para maximizar sus posibilidades de llegar a escapar?

Estoy tratando de formular esto como un problema de programación dinámica, pero no estoy seguro de cómo asociar los costos con ella. No estoy seguro de si tengo que usar el descuento de la "muerte" en el escenario.

Cualquier ayuda sería muy apreciada.

Answer 1

Si sólo tiene dos pasos, su posibilidad de escapar es $p_a+r_ap_b$ o $p_b+r_bp_a$.
% De uso $r_a=1-p_a-q_a$, esto es $p_a+p_b-q_ap_b-p_ap_b$ o $p_a+p_b-p_ap_b-q_bp_a$.
Así que elija paso $A$ si % o $q_ap_b<p_aq_b$ $p_a/q_a>p_b/q_b$.
Esto significa que debe seleccionar en orden decreciente de $p_i/q_i$.

Answer 2

Los resultados de este proceso son las cadenas de $P_i$, $Q_i$, $R_i$, donde $P_i$ medios de escapar a través de pasaje $i$, $Q_i$ significa morir a través del pasaje $i$, e $R_i$ significa retorno a través del pasaje $i$. La cadena termina tan pronto como llegamos a $P_i$ o $Q_i$.

Por lo que un resultado típico, si $n=4$, podría parecerse a $R_1 R_3 R_4 R_2 Q_2$. Si asociamos $P_i$ $p_i$ y así sucesivamente, entonces, por la independencia, la probabilidad de cada resultado es simplemente la cadena interpretarse como un producto: $$\Pr(R_1 R_3 R_4 R_2 Q_2) =r_1 r_3 r_4 r_2 q_2. $$

(También es posible tener una infinita cadena de $r$'s, pero si $r_i<1$ por cada $i$, entonces la probabilidad de que estos son todos 0.)

Ahora vamos a pedir a todas las maneras en que se nos puede escapar en la mayoría de los 2 movimientos. Que todas las cadenas de la $P_i$ y todas las cadenas de la $R_iP_j$. Estos par en los dos escapar de los resultados de las estrategias de $(i,j)$ donde $(i,j)$ significa que primero pruebe con el $i$th paso, a continuación, intente la $j$th pasaje. Ahora la probabilidad de escape con la estrategia de $(i, j)$ es $$\Pr(P_i)+\Pr(R_iP_j) = p_i + r_i p_j. $$

Por el mismo razonamiento, la probabilidad de escape con la estrategia de $(i_1, i_2, i_3, i_4, \ldots)$ es $$ p_{i_1} + r_{i_1} p_{i_2} + r_{i_1} r_{i_2} p_{i_3} + r_{i_1} r_{i_2} r_{i_3} p_{i_4} +\cdots, $$ una serie infinita. Así que en general, el problema parece un poco difíciles para mí.

Si cada paso, que sólo puede ser tratado de una vez, entonces usted necesita considerar sólo a $(1, 2, 3, \ldots, n)$ y todas sus permutaciones. Un programa de ordenador puede calcular todas aquellas sumas y seleccione el valor máximo. Sin embargo, como $n$ aumenta el número de este tipo de estrategias ($n!$) aumenta muy rápidamente.

Answer 3

Se trata de un Markov / enfoque de la matriz a la cuestión de la transición.

Cada puerta tiene la siguiente matriz de transición:

$$M_i =\begin{array} {c|ccc} & \text{Room} & \text{Escaped} & \text{Dead} \\ \hline \text{Room} & R_i & P_i & Q_i \\ \text{Escaped} & 0 & 1 & 0 \\ \text{Dead} & 0 & 0 & 1 \\ \end{matriz} =\begin{bmatrix} T_i & F_i \\ 0 & I \end{bmatrix} $$

El estado estacionario de cada puerta es:

$$S_i = (I - T_i)^{-1}F_i = \begin{bmatrix} \frac{P_i}{1 - R_i} & \frac{Q_i}{1 - R_i} \end{bmatrix}$$

Así que la posibilidad de escapar si elige repetidamente la puerta $i$ $\frac{P_i}{1 - R_i}$ y la posibilidad de morir $\frac{Q_i}{1 - R_i}$.

Es observable implica de que $P_i + Q_i + R_i = 1$ $\frac{P_i}{1 - R_i} + \frac{Q_i}{1 - R_i} = 1$.