algorithm - recursividad - laberinto recursivo c++

Teoría de programación: resolver un laberinto

Question

¿Cuáles son las formas posibles de resolver un laberinto?
Tengo dos ideas, pero creo que no son muy elegantes.

Situación base: tenemos una matriz, y los elementos en esta matriz están ordenados de una manera que representa un laberinto, con una entrada y otra salida.

Mi primera idea fue enviar un robot a través del laberinto, siguiendo un lado, hasta que salga del laberinto. Creo que esta es una solución muy lenta.

El segundo pasa a través de cada elemento sucesivo marcado con 1, comprueba dónde puede ir (arriba, derecha, abajo, izquierda) elige un camino y continúa su camino allí. Esto es incluso más lento que el primero.

Por supuesto, es un poco más rápido si hago los dos bots de subprocesos múltiples en cada cruce, pero tampoco es la mejor manera.

Es necesario que haya mejores soluciones para enviar un bot a través de un laberinto.

EDITAR
Primero: ¡Gracias por las buenas respuestas!

La segunda parte de mi pregunta es: ¿Qué hacer en el caso si tenemos un gráfico multidimensional? ¿Hay prácticas especiales para eso o la respuesta de Justin L. también es útil para eso?
Creo que no es la mejor manera para este caso.

La tercera pregunta:
¿Cuál de estos algoritmos de resolución de laberinto es / son los más rápidos? (Puramente hipotético)

Answer 1

¿Qué le parece crear un gráfico de su matriz y utilizar la primera búsqueda de ancho, la primera búsqueda de profundidad o el algoritmo de Dijkstras?

Answer 2

Esta es una representación muy simple para simular laberintos en C ++ :)

#ifndef vAlgorithms_Interview_graph_maze_better_h
#define vAlgorithms_Interview_graph_maze_better_h

static const int kMaxRows = 100;
static const int kMaxColumns = 100;

class MazeSolver
    {
private:
    char m_matrix[kMaxRows][kMaxColumns]; //matrix representation of graph
    int rows, cols; //actual rows and columns

    bool m_exit_found;
    int m_exit_row, m_exit_col;
    int m_entrance_row, m_entrance_col;

    struct square //abstraction for data stored in every verex
        {
        pair<int, int> m_coord; //x and y co-ordinates of the matrix
        square* m_parent; //to trace the path backwards

        square() : m_parent(0) {}
        };

    queue<square*> Q;

public:
    MazeSolver(const char* filename)
        : m_exit_found(false)
        , m_exit_row(0)
        , m_exit_col(0)
        , m_entrance_row(0)
        , m_entrance_col(0)
        {
        ifstream file;
        file.open(filename);

        if(!file)
            {
            cout << "could not open the file" << endl << flush;
            // in real world, put this in second phase constructor
            }
        init_matrix(file);
        }
    ~MazeSolver()
        {
        }
    void solve_maze()
        {
        //we will basically use BFS: keep pushing squares on q, visit all 4 neighbors and see
        //which way can we proceed depending on obstacle(wall)

        square* s = new square();
        s->m_coord = make_pair(m_entrance_row, m_entrance_col);

        Q.push(s);

        while(!m_exit_found && !Q.empty())
            {
            s = Q.front();
            Q.pop();

            int x = s->m_coord.first;
            int y = s->m_coord.second;
            //check if this square is an exit cell
            if(x == m_exit_row && y == m_exit_col)
                {
                m_matrix[x][y] = ''>''; // end of the path
                m_exit_found = true;
                //todo: try breaking? no= queue wont empty
                }
            else
                {
                //try walking all 4 neighbors and select best path
                //NOTE: Since we check all 4 neighbors simultaneously,
                //      the path will be the shortest path
                walk_path(x-1, y, s);
                walk_path(x+1, y, s);
                walk_path(x, y-1, s);
                walk_path(x, y+1, s);
                }
            } /* end while */

        clear_maze(); //unset all previously marked visited shit

        //put the traversed path in maze for printing
        while(s->m_parent)
            {
            m_matrix[s->m_coord.first][s->m_coord.second] = ''-'';
            s = s->m_parent;
            } /* end while */
        }

    void print()
        {
        for(int i=0; i<rows; i++)
            {
            for(int j=0; j<cols; j++)
                cout << m_matrix[i][j];
            cout << endl << flush;
            }
        }

private:
    void init_matrix(ifstream& file)
        {
        //read the contents line-wise
        string line;
        int row=0;
        while(!file.eof())
            {
            std::getline(file, line);
            for(int i=0; i<line.size(); i++)
                {
                m_matrix[row][i] = line[i];
                }
            row++;
            if(line.size() > 0)
                {
                cols = line.size();
                }
            } /* end while */
        rows = row - 1;

        find_exit_and_entry();
        m_exit_found = false;
        }

    //find and mark ramp and exit points
    void find_exit_and_entry()
        {
        for(int i=0; i<rows; i++)
            {
            if(m_matrix[i][cols-1] == '' '')
                {
                m_exit_row = i;
                m_exit_col = cols - 1;
                }
            if(m_matrix[i][0] == '' '')
                {
                m_entrance_row = i;
                m_entrance_col = 0;
                }
            } /* end for */
        //mark entry and exit for testing
        m_matrix[m_entrance_row][m_entrance_col] = ''s'';
        m_matrix[m_exit_row][m_exit_col] = ''e'';
        }

    void clear_maze()
        {
        for(int x=0; x<rows; x++)
            for(int y=0; y<cols; y++)
                if(m_matrix[x][y] == ''-'')
                    m_matrix[x][y] = '' '';
        }
        // Take a square, see if it''s the exit. If not, 
        // push it onto the queue so its (possible) pathways
        // are checked.
    void walk_path(int x, int y, square* parent)
        {
        if(m_exit_found) return;
        if(x==m_exit_row && y==m_exit_col)
            {
            m_matrix[x][y] = ''>'';
            m_exit_found = true;
            }
        else
            {
            if(can_walk_at(x, y))
                {
                //tag this cell as visited
                m_matrix[x][y] = ''-'';

                cout << "can walk = " << x << ", " << y << endl << flush;

                //add to queue
                square* s = new square();
                s->m_parent = parent;
                s->m_coord = make_pair(x, y);
                Q.push(s);
                }
            }
        }

    bool can_walk_at(int x, int y)
        {
        bool oob = is_out_of_bounds(x, y);
        bool visited = m_matrix[x][y] == ''-'';
        bool walled = m_matrix[x][y] == ''#'';

        return ( !oob && !visited && !walled);
        }
    bool is_out_of_bounds(int x, int y)
        {
        if(x<0 || x > rows || y<0 || y>cols)
            return true;
        return false;
        }
    };


void run_test_graph_maze_better()
        {
        MazeSolver m("/Users/vshakya/Dropbox/private/graph/maze.txt");
        m.print();
        m.solve_maze();
        m.print();
        }


#endif

Answer 3

Este algoritmo de azkaban también podría ayudarlo, http://journals.analysisofalgorithms.com/2011/08/efficient-maze-solving-approach-with.html

Answer 4

Este es uno de mis algoritmos favoritos alguna vez ...

1) Move forward
2) Are you at a wall?
2a) If yes, turn left
3) Are you at the finish?
3a) If no, go to 1
3b) If yes, solved

Answer 5

Existen muchos algoritmos de resolución de laberintos:

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

http://www.astrolog.org/labyrnth/algrithm.htm#solve

Para un robot, el algoritmo de Tremaux parece prometedor.

Answer 6

La mejor manera de resolver un laberinto es usar un algoritmo de conectividad, como union-find, que es un algoritmo de tiempo casi lineal asumiendo que se realiza la compresión de ruta.

Union-Find es una estructura de datos que le indica si dos elementos de un conjunto están conectados de manera transitiva.

Para utilizar una estructura de datos de unión-unión para resolver un laberinto, primero se utilizan los datos de conectividad de vecinos para construir la estructura de datos de unión-encuentro. Entonces, el hallazgo de unión está comprimido. Para determinar si el laberinto es solvente, se comparan los valores de entrada y salida. Si tienen el mismo valor, entonces están conectados y el laberinto es solvente. Finalmente, para encontrar una solución, comienza con la entrada y examina la raíz asociada con cada uno de sus vecinos. Tan pronto como encuentre un vecino no visitado previamente con la misma raíz que la celda actual, visite esa celda y repita el proceso.

La principal desventaja de este enfoque es que no le indicará la ruta más corta a través del laberinto, si hay más de una ruta.

Answer 7

La misma respuesta que todas las preguntas sobre desbordamiento de pila;)

Use vi!

http://www.texteditors.org/cgi-bin/wiki.pl?Vi-Maze

Es realmente fascinante ver un editor de texto resolver un ascii-maze, estoy seguro de que los chicos de emacs tienen un equivalente ...

Answer 8

No específicamente para su caso, pero me he encontrado con varias preguntas sobre el concurso de programación en las que encontré el algoritmo de Lee bastante útil para codificar rápidamente. No es el más eficiente para todos los casos, pero es fácil de poner en marcha. Aquí hay one que pirateé para un concurso.

Answer 9

Puedes pensar en tu laberinto como un árbol.

A / / / / B C / / / / D E F G / / / H I J / / L M / / ** O (which could possibly represent) START + +---+---+ | A C G | +---+ + + + | D B | F | J | +---+---+ +---+---+ | L H E I | +---+ +---+---+ | M O | + +---+ FINISH (ignoring left-right ordering on the tree)

Donde cada nodo es una unión de caminos. D, I, J, L y O son callejones sin salida, y ** es el objetivo. Por supuesto, en su árbol actual, cada nodo tiene la posibilidad de tener hasta tres hijos.

Su objetivo ahora es simplemente encontrar qué nodos atravesar para encontrar el final. Cualquier viejo algoritmo de búsqueda arbórea lo hará.

Al mirar el árbol, es bastante fácil ver la solución correcta simplemente "rastreando" desde ** en la parte más profunda del árbol:

A B E H M **

Tenga en cuenta que este enfoque se vuelve un poco más complicado cuando tiene "bucles" en su laberinto (es decir, cuando es posible, sin retroceder, vuelve a ingresar un pasaje que ya ha recorrido). Compruebe los comentarios de una buena solución.

Ahora, veamos tu primera solución que mencionaste, aplicada a este árbol.

Su primera solución es básicamente una búsqueda en profundidad , que realmente no es tan mala. En realidad es una muy buena búsqueda recursiva. Básicamente, dice: "Siempre tome el enfoque más a la derecha primero. Si no hay nada allí, retroceda hasta el primer lugar, puede ir derecho o izquierdo, y luego repita.

Una búsqueda en profundidad buscará en el árbol de arriba en este orden:

A B D (backtrack) E H L (backtrack) M ** (backtrack) O (backtrack thrice) I
(backtrack thrice) C F (backtrack) G J

Tenga en cuenta que puede detenerse tan pronto como encuentre el **.

Sin embargo, cuando realmente codifica una búsqueda en profundidad, el uso de programación recursiva hace que todo sea mucho más fácil. Incluso los métodos iterativos también funcionan, y nunca tiene que programar explícitamente cómo retroceder. Consulte el artículo vinculado para ver las implementaciones.

Otra forma de buscar un árbol es la solución Breadth-First , que busca a través de los árboles por profundidad. Buscaría a través del árbol de arriba en este orden:

A (next level) B C (next level) D E F G (next level)
H I J (next level) L M (next level) ** O

Tenga en cuenta que, debido a la naturaleza de un laberinto, el ancho primero tiene una cantidad promedio de nodos mucho mayor que verifica. Breadth-first se implementa fácilmente teniendo una cola de rutas de búsqueda, y cada iteración saca una ruta de una cola, "explotando" obteniendo todas las rutas en las que puede convertirse después de un paso, y poniendo esas nuevas rutas al final de la cola No hay comandos explícitos de "siguiente nivel" para codificar, y esos solo estaban ahí para ayudar a la comprensión.

De hecho, hay una lista completa de maneras de buscar un árbol . Acabo de mencionar las dos formas más simples y directas.

Si su laberinto es muy, muy largo y profundo, y tiene lazos y locuras, y es complicado, sugiero el algoritmo A* , que es el algoritmo de identificación de ruta estándar de la industria que combina una búsqueda de Breadth-First con heurística ... algo así como una "búsqueda inteligente de amplitud".

Básicamente funciona así:

1. Pon un camino en una cola (el camino donde solo caminas un paso directo al laberinto). Un camino tiene un "peso" dado por su longitud actual + su distancia en línea recta desde el final (que puede calcularse matemáticamente)
2. Abre el camino con el peso más bajo de la cola.
3. "Explotar" la ruta en cada ruta que podría ser después de un paso. (es decir, si su ruta es Derecha Izquierda Izquierda Derecha, entonces sus rutas explotadas son RLLRR y RLLRL, sin incluir las ilegales que atraviesan paredes)
4. Si uno de estos caminos tiene el objetivo, entonces ¡Victoria! De otra manera:
5. Calcule los pesos de las rutas explotadas y vuelva a colocarlas en la cola (sin incluir la ruta original)
6. Ordene la cola por peso, la más baja primero. Luego repite desde el paso n. ° 2

Y eso es A * , que presento resaltado especialmente porque es más o menos el algoritmo de identificación de ruta estándar de la industria para todas las aplicaciones de pathfinding, incluido el movimiento de un extremo del mapa a otro mientras se evitan caminos fuera de la carretera o montañas, etc. Funciona muy bien porque usa la heurística de distancia más corta posible , lo que le da su "inteligencia". A * es tan versátil porque, dado cualquier problema, si tiene disponible una heurística de distancia lo más corta posible (la nuestra es fácil, la línea recta), puede aplicarla.

PERO es de gran valor notar que A * no es su única opción.

De hecho, la categoría wikipedia de algoritmos de recorrido de árbol lista solo a 97! (lo mejor será en esta página vinculada anteriormente)

Perdón por la longitud = P (tiendo a divagar)

Answer 10

Si el robot puede realizar un seguimiento de su ubicación, por lo que sabe si ha estado en una ubicación antes, entonces la búsqueda de profundidad es el algoritmo obvio. Puede demostrar mediante un argumento contradictorio que no es posible obtener un mejor rendimiento en el peor de los casos que la búsqueda en profundidad.

Si tiene a su disposición técnicas que no pueden ser implementadas por robots, la búsqueda de amplitud puede ser mejor para muchos laberintos, al igual que el algoritmo de Dijkstra para encontrar el camino más corto en un gráfico.

Answer 11

Solo una idea. ¿Por qué no arrojar algunos bots allí al estilo monte carlo? Vamos a llamar a la primera generación de bots gen0. Solo mantenemos los bots de gen0 que tienen algunos caminos continuos de esta manera:
-desde el comienzo hasta cierto punto
o -desde algún punto hasta el final

Ejecutamos una nueva gen1 de bots en nuevos puntos aleatorios, luego tratamos de conectar las carreteras de los bots de gen1 con las de gen0 y ver si obtenemos un camino continuo de principio a fin.

Entonces, para Genn tratamos de conectarnos con los bots de gen0, gen1, ..., genn-1.

Por supuesto, una generación solo dura una cantidad finita de tiempo.

No sé si el aspecto del algoritmo resultará práctico para pequeños conjuntos de datos.
Además, el algoritmo supone que conocemos los puntos de inicio y finalización.

algunos buenos sitios para ideas:
http://citeseerx.ist.psu.edu/
http://arxiv.org/

Answer 12

Tuve un problema similar en uno de mis Comp Universidad. Sci. cursos. La solución que se nos ocurrió fue seguir la pared de la mano izquierda (la pared de la mano derecha funcionará igual de bien). Aquí hay un pseudocódigo

While Not At End
    If Square To Left is open,
        Rotate Left
        Go Forward
    Else
        Rotate Right
    End If
Wend

Eso es básicamente eso. La parte compleja es mantener un registro de la dirección hacia la que se orienta, y averiguar qué posición de la cuadrícula está a su izquierda en función de esta dirección. Funcionó para cualquier caso de prueba que yo haya presentado. Bastante interesante la solución de los profesores fue algo así como:

While Not At End
    If Can Go North
        Go North
    ElseIf Can Go East
        Go East
    ElseIf Can Go South
        Go South
    ElseIf Can Go West 
        Go West
    EndIf
Wend

Lo cual funcionará bien para la mayoría de los laberintos simples, pero falla en un laberinto que se ve así:

SXXXXXXXXXXXXX
   X         X
   X         X
   X         X
 XXX         X
 X X         X
 X XXXXXXXXXXX     XXXE
 X                 X
 XXXXXXXXXXXXXXXXXXX

S y E son el principio y el final.

Con algo que no sigue el muro, terminas teniendo que mantener una lista de los lugares en los que has estado, para que puedas retroceder si es necesario, cuando caigas en un callejón sin salida, y para que no te atrapen. en un bucle Si sigues el muro, no hay necesidad de hacer un seguimiento de dónde has estado. Aunque no encontrarás el camino más óptimo a través del laberinto, siempre lo atravesarás.

Answer 13

Un enfoque interesante, al menos me pareció interesante, es usar autómatas celulares. En resumen, una celda "espacial" rodeada por 3 celdas de "pared" se convierte en una celda de "pared". Al final, las únicas celdas espaciales que quedan son las que están en ruta hacia la salida.

Si miras el árbol que Justin puso en su respuesta, entonces puedes ver que los nodos de las hojas tienen 3 paredes. Pode el árbol hasta que tenga un camino.

Answer 14

hay muchos algoritmos y muchas configuraciones diferentes que especifican qué algoritmo es el mejor. esta es solo una idea sobre un entorno interesante:

supongamos que tiene las siguientes propiedades ...

• Mueves un robot y quieres minimizar su movimiento , no su uso de CPU.
• ese robot puede inspeccionar solo las celdas vecinas o mirar a lo largo de los corredores ya sea que vea o no cruce de caminos.
• tiene GPS .
• conoce las coordenadas de su destino.

entonces puedes diseñar una IA que ...

• dibuja un mapa, cada vez que recibe nueva información sobre el laberinto.
• calcula las longitudes mínimas conocidas de la ruta entre todas las posiciones no observadas (y ella misma y el destino).
• puede priorizar las posiciones no observadas para la inspección en función de las estructuras circundantes . (si es imposible llegar al destino desde allí de todos modos ...)
• puede priorizar las posiciones no observadas para la inspección en función de la dirección y la distancia hasta el destino.
• puede priorizar puestos no observados para inspección basados ​​en la experiencia de recopilar información . (¿Qué tan lejos puede ver en promedio y qué tan lejos debe caminar?)
• puede priorizar posiciones no observadas para encontrar posibles atajos . (experiencia: ¿hay muchos bucles ?)