obtener rata fuera de un laberinto

Question

Una rata se coloca en un laberinto en una posición desconocida en el laberinto.

Todo lo que podemos ir es en direcciones arriba, abajo, derecha o izquierda. Y tenemos dos métodos:

• tryMove (< dirección >) que devuelve false si hay una pared y verdadero si podemos mover.
• bool hasLadder(): que devuelve verdadero si hay una escalera para escapar.

Tenemos que escribir una función explorar que devuelve verdadero si encontramos la salida o falso si no hay manera.

Este es un problema de gráfico simple y puede resolverse usando bfs o un algoritmo dfs si podemos encontrar marcar estos lugares. Si no podemos marcar estos lugares, podemos movernos en ciclos visitando los mismos lugares. ¿Puede alguien ayudarme a salir del laberinto por favor si no está marcado? ¿Es posible?

Answer 1

Tanto la primera búsqueda de anchura como la de profundidad requieren memoria y un algoritmo ingenuo puede enlazar indefinidamente. Una rata probablemente solo tiene O (1) memoria.

Una forma de resolverlo sin recordar dónde has estado es elegir una dirección al azar. El tiempo de resolución será extremadamente largo, pero eventualmente debería llegar a cada cuadrado alcanzable. Esto está relacionado con la caminata 2D random.

Sorprendentemente, se ha demostrado que en una red bidimensional, un paseo aleatorio tiene una probabilidad de unidad de llegar a cualquier punto (incluyendo el punto de partida) como el número de pasos se aproxima al infinito.

Answer 2

Debe ejecutar algoritmos BFS. El único problema que veo es cómo definir el gráfico. Se puede definir con von Neumann neighborhood. El nodo se define como X, par Y. pseudo código debe ser similar:

BFS 
while (!Q.empty()){ 
    v = Q.top() 
    neighbours = get_adj_list(v) 
    foreach (w in neighbours){ 
     if (isWall(w) || isOutsideMaze(w)) skip 
     if (isTerminal(w)) printPathAndExit 
     if (dist[v] + 1 < dist[w]) 
      dist[w] = dist[v] + 1 
      Q.push(w) 
    } 
} 

GEN_NEIGHBOURS 
dx = {-1,1} 
dy = {-1,1} 

get_adj_list(v) 
    adj_list = [] 
    for (i in dx) 
     for (j in dy) 
      adj_list << node(v.x-i,v.y-j) 
    return adj_list 

EDITAR: ahora leo el límite de memoria es O (1). Así que supongo que debes seguir el método anterior para girar siempre hacia la derecha y eventualmente saldrás del laberinto o volverás a la posición de inicio.

Edit2: desde Corn Maze consejos:

Como con cualquier laberinto, si siempre se tenga derecho o virajes a la izquierda, es muy probable que encontrar una salida. Pasar el dedo por la pared del laberinto sin levantarlo lo mantendrá en el camino correcto.

Answer 3

Este es un problema clásico que a menudo se utiliza como tarea.

Prueba esto:

1. puede saber si usted está en el camino de salida ahora?
2. Una vez que tenga eso, ¿qué debe hacer para saber si se encuentra a un solo paso del camino de salida?
3. ¿Qué tal si estás a 2 movimientos de la salida?

...

Como Mark notes, las versiones más simples del algoritmo que estoy tratando de dar lugar a que pueden quedar encerrado en un bucle. ¿Cómo puedes resolver este problema?

Answer 4

Si no recuerdo mal, tuve una tarea de recursión como esta hace mucho tiempo, sin embargo, no se limitaba a la memoria O (1). Simplemente no pudimos construir 'mapas' de donde hemos estado y tuvimos que recurrir a la recursión ... Supongo que esto usaría memoria O (n), donde n es la distancia más corta a la escalera desde el principio.

while(1) 
    { 
    if(search(MOVE_LEFT, i) || 
     search(MOVE_UP, i) || 
     search(MOVE_RIGHT, i) || 
     search(MOVE_DOWN, i)) 
     { 
     return TRUE; 
     } 
    i++; 
    } 

/* recursive function */ 
bool search(move_type move, long int length) 
{ 

doMove(move); /* actually move the rat to requested place */ 

if(hasLadder()) 
    return TRUE; 

if(0 == length) 
    return FALSE; 

switch(move) /* check each and return rat to previous place */ 
    { 
    case MOVE_LEFT: 
     if(tryMove(MOVE_LEFT) && search(MOVE_LEFT, length - 1)) return TRUE; 
     if(tryMove(MOVE_UP) && search(MOVE_UP, length - 1)) return TRUE; 
     if(tryMove(MOVE_DOWN) && search(MOVE_RIGHT, length - 1)) return TRUE;  
     doMove(MOVE_RIGHT); break; 
    case MOVE_UP: 
     if(tryMove(MOVE_LEFT) && search(MOVE_LEFT, length - 1)) return TRUE; 
     if(tryMove(MOVE_UP) && search(MOVE_UP, length - 1)) return TRUE; 
     if(tryMove(MOVE_RIGHT) && search(MOVE_RIGHT, length - 1)) return TRUE; 
     doMove(MOVE_DOWN); break; 
    case MOVE_RIGHT: 
     if(tryMove(MOVE_UP) && search(MOVE_UP, length - 1)) return TRUE; 
     if(tryMove(MOVE_RIGHT) && search(MOVE_RIGHT, length - 1)) return TRUE; 
     if(tryMove(MOVE_DOWN) && search(MOVE_RIGHT, length - 1)) return TRUE;  
     doMove(MOVE_LEFT); break; 
    case MOVE_DOWN: 
     if(tryMove(MOVE_LEFT) && search(MOVE_LEFT, length - 1)) return TRUE; 
     if(tryMove(MOVE_RIGHT) && search(MOVE_RIGHT, length - 1)) return TRUE; 
     if(tryMove(MOVE_DOWN) && search(MOVE_RIGHT, length - 1)) return TRUE;  
     doMove(MOVE_UP); break; 
    } 

return FALSE; 

} /* search() */ 

Answer 5

Determinar si hay una salida me suena a problema de detención. Puede resolverse para todos los casos triviales y muchos no triviales, pero para muchos mapas, a menos que pueda marcar dónde ha estado, no puede probar que el mapa no es infinito.

http://en.wikipedia.org/wiki/Halting_problem

Answer 6

Sin recuerdos, la única solución es el al azar y es terrible. Si sabes que el laberinto solo está conectado por separado, puedes utilizar un enfoque de seguimiento de pared, pero eso puede entrar en un ciclo infinito si el laberinto contiene un bucle.

Answer 7

El algoritmo es básicamente USTCON (no dirigido st-conectividad): dado un grafo no dirigido G, determinar si existe un camino desde (posición de inicio de la rata) nodo s al nodo t (la salida) . Este problema está en complexity class L, lo que significa que requiere un logarithmic amount of memory. Entonces, a menos que tenga un límite superior en el tamaño del laberinto, o esté dispuesto a aproximarse, es imposible con espacio constante.

Answer 8

Gracioso que @mousey preguntaría por una rata ... anwyay.

He visto este problema arrastrarse un número de veces ya.

La primera (e ingenua) solución es seguir la pared izquierda (o derecha), sin embargo, es posible crear laberintos específicos donde la rata termina corriendo en círculos.

De hecho, para cada orden determinista de movimientos (como 2L, 1R, 2L, 1R, ...) que probé (estar en la escuela secundaria tenía tiempo) podíamos llegar a un laberinto que haría el rata corre en círculos. Por supuesto, cuanto más complicado es el ciclo, más complicado es el laberinto.

Por lo tanto, si tiene memoria O (1), la única solución para salir del laberinto parece ser una caminata aleatoria, como lo propone Mark Byers. Lamentablemente, no se puede demostrar que sea imposible salir del laberinto con un algoritmo de ese tipo.

Por otro lado, si tiene memoria O (N), se reduce a crear un mapa (de alguna manera). La estrategia con la que finalmente se me ocurrió en ese momento fue dejar el feromón (incrementando el contador) en cada caso que aprobé, y al tener una opción en un movimiento, elegir entre los casos menos visitados. Sin embargo, siempre fue posible salir, así que nunca tuve que pensar en una condición de terminación en caso de que no haya salida.

También puede usar un algoritmo de relleno de inundación ... Por supuesto, fue antes de conocer el término BFS. Esto tiene la ventaja de que tiene una condición de terminación (cuando no le queda ningún caso por explorar).