Hay una 8*8 laberinto, y un jugador de partida en (0, 0) quiere llegar a (7, 7) en un mínimo de movimientos.
Para cada ronda (ronda puede contener varios movimientos), el obstáculo será aleatoriamente en una cuadrícula no se ha establecido antes, también, que no sea (0, 0) o (7, 7).
Después de que el obstáculo es el conjunto (aunque el jugador no tiene idea de dónde está en esta ronda), el jugador tiene que dar una distribución de probabilidad de su movimiento en esta ronda, por ejemplo: 0.5, abajo: 0.2 izquierda: 0.2, derecho: 0.1, entonces su movimiento se genera en función de la distribución. Si se tropieza con el obstáculo o se sale del laberinto (por ejemplo, mover a la derecha cuando él está en (7, 0)), él tiene que permanecer en la red actual, y otro movimiento será generado. El proceso continúa hasta que se traslada a una posible red.
Cuando finaliza la ronda, el jugador va a saber donde está el obstáculo fue en la última ronda. Para ser claro, se supone que el jugador está en la enésima ronda, luego de que él se podrá conocer la historia del obstáculo desde la primera ronda hasta la (n-1)th ronda.
Mi pregunta es, dada la historia del obstáculo y la posición actual del jugador, es que hay una estrategia para minimizar la espera se mueve desde una perspectiva probabilística?
EDITAR
Yo he escrito un programa de simulación, e intentado varias estrategias con ella. Definir una estrategia que consta de cuatro valores reales, lo que representa la probabilidad de moverse hacia arriba, abajo, izquierda y derecha, respectivamente.Los ingenuos [0.25, 0.25, 0.25, 0.25] obtuvo un promedio de 73 mueve.
Otra de las estrategias que se definen a continuación:
si arriba y derecha sean seguros, retorno [0.5, 0, 0, 0.5]
si es seguro, regresar [1, 0, 0, 0]; si la derecha es seguro, retorno [0, 0, 0, 1]
si en el derecho de la mayoría de línea, retorno [0.5, 0, 0.5, 0]; si en la mayor parte de la línea, retorno [0, 0.5, 0, 0.5]
otra cosa, volver [0.5, 0, 0.5, 0]
En la final, la segunda estrategia, es necesario 18.4573 se mueve en promedio. (10000 ensayos)
Es un gran éxito cuando se comparan con los ingenuos, pero estoy luchando con acercando a la teoría mínimo de 14 movimientos. Agradezco cualquier consejo o sugerencia.
La confirmación
Hay un $(X,Y)=(0:N-1,0:N-1) \in \mathbb{R}^2, N=8$ laberinto
Sí
No hay paredes interiores o caminos en el laberinto (Entonces no es un laberinto??),
Sí, me llamó un laberinto tan sólo porque no es una sola al azar que aparecen obstáculo.
Las posiciones no puede quedar fuera del dominio, por lo tanto, evidentemente, el movimiento tendrá que ser debidamente restringido,
Sí, si la intención de mover generado por la distribución de probabilidad hará que el jugador a salir del laberinto, el número de movimientos que se incrementará en uno, y el jugador tiene que permanecer en la posición actual hasta un factible movimiento es generado.
Hay un cambio de obstáculo a un desconocido de la posición $(x^o,y^o)$, para cada tiempo de $t$,
Sí
La posición del obstáculo en $t=n-1$ es conocido en $t=n$,
Sí
Para cada tiempo de $n$, el obstáculo cambiar sus coordenadas según una distribución uniforme en $(X,Y)$. Por lo tanto, el obstáculo puede "saltar" a su nueva posición,
Sí
El obstáculo no tome una anterior de coordenadas. Por lo tanto la distribución uniforme es de más de $(X,Y)-(X^o,Y^o)$, $(X^o,Y^o)={(x^o(t),y^o(t),t=1...n-1)}$. De ahí el obstáculo toma su último movimiento en $t=N^2$ y luego desaparece (??),
El obstáculo no se establece en la que indica el punto y el punto final, por lo que el jugador perderá el juego si no puede llegar a la salida en $N^2 - 2$ rondas
El jugador de la posición $(x(t),y(t))$ uno de los cuadrados (arriba, abajo, izquierda o derecha) por el tiempo,
Sí
El jugador no puede pasar, por lo tanto no hacen mover a todos (??),
No estoy seguro de lo que usted se refiere.
Si el obstáculo se golpea al jugador por un movimiento del jugador o un obstáculo cambio, el jugador pierde,
Si el obstáculo se golpea al jugador por un movimiento del jugador, como he dicho en mi problema, Si se tropieza con el obstáculo o se sale del laberinto (por ejemplo, mover a la derecha cuando él está en (7, 0)), él tiene que permanecer en la red actual, y otro movimiento será generado. El proceso continúa hasta que se traslada a una posible red. En resumen, el jugador pierde el juego si no puede llegar a la salida en $N^2 - 2$ rondas. Si el obstáculo se golpea al jugador por un obstáculo cambio, asumimos que el jugador es lo suficientemente fuerte como para levantar el obstáculo, por lo que con seguridad puede quedarse con el obstáculo de la misma cuadrícula.
Si el reproductor de llegar a la salida, el jugador gana.
Sí
