Теория программирования: решите лабиринт

существует множество алгоритмов решения лабиринтов:

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

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

для робота, алгоритм Тремо выглядит многообещающе.

интересный подход, по крайней мере, я нашел его интересным, заключается в использовании клеточных автоматов. Короче говоря," пространственная "ячейка, окруженная 3" стеновыми "ячейками, превращается в" стеновую " ячейку. В конце остаются только те ячейки пространства, которые находятся на пути к выходу.

Если вы посмотрите на дерево, которое Джастин поставил в своем ответе, то вы можете увидеть, что листовые узлы имеют 3 стены. Подрежьте дерево, пока у вас есть путь.

Как насчет построения графика из вашей матрицы и использования широты первого поиска, глубины первого поиска или алгоритма Dijkstras?

Это один из моих любимых алгоритмов никогда....

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

Это очень простое представление для имитации лабиринта в 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

просто идея. Почему бы не бросить туда несколько ботов в стиле Монте-Карло. Назовем первое поколение ботов gen0. Мы только сохраняем ботов из gen0, которые имеют некоторые непрерывные дороги таким образом:
- от начала до некоторой точки
или-от какой-то точки до конца

мы запускаем новый gen1 ботов в новых случайных точках, затем мы пытаемся соединить дороги ботов gen1 с теми из gen0 и посмотреть, получим ли мы непрерывную дорогу от начала до конца.

Так для genn мы пытаемся соединиться с ботами формы gen0, gen1, ..., genn-1.

конечно, поколение длится только определенное количество времени.

Я не знаю, будет ли цвет алгоритма практичным для небольших наборов данных.
также алгоритм предполагает, что мы знаем начальную и конечную точки.

хороших сайтов для идей:
http://citeseerx.ist.psu.edu/
http://arxiv.org/

у меня была аналогичная проблема в одном из моих университетских компов. Научный. курсы. Решение, которое мы придумали, состояло в том, чтобы следовать за левой стеной (правая стена будет работать так же хорошо). Вот какой-то псевдокод

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

вот в принципе и все. Сложная часть отслеживает, в каком направлении ваша облицовка, и выясняет, какая позиция сетки находится слева от вас на основе этого направления. Это сработало для любого теста, который я поставил против него. Достаточно интересным было решение профессоров что-то вроде:

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

который будет хорошо работать для большинства простых лабиринтов, но терпит неудачу в лабиринте, который выглядит следующим образом:

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

С S и E быть началом и концом.

со всем, что не следует за стеной, вам в конечном итоге придется вести список мест, где вы были, чтобы вы могли вернуться, если это необходимо, когда вы попадаете в тупик, и чтобы вы не попали в петлю. Если вы будете следовать за стеной, нет нужно следить за тем, где вы были. Хотя вы не найдете самый оптимальный путь через лабиринт, вы всегда будете получать через него.

Если робот может отслеживать свое местоположение, поэтому он знает, Был ли он в месте раньше, то поиск по глубине является очевидным алгоритмом. Вы можете показать с помощью состязательного аргумента, что невозможно получить лучшую производительность в худшем случае, чем поиск по глубине.

Если у вас есть доступные вам методы, которые не могут быть реализованы роботами, то поиск по ширине может работать лучше для многих лабиринтов, как и алгоритм Дейкстры для поиска кратчайшего пути в диаграмма.

есть много алгоритмов и много различные настройки это указывает, какой алгоритм лучше. это всего лишь одна идея о интересной настройке:

предположим, у вас есть следующие свойства...

• вы двигаете робота, и вы хотите, чтобы минимизировать его движения, а не ЦП.
• этот робот может либо проверять только свои соседние клетки, либо смотреть вдоль коридоры либо видеть, либо не видеть перекрестные пути.
• это GPS.
• он знает координаты места назначения.

тогда вы можете создать A. I. который...

• рисует карту – каждый раз, когда он получает новую информацию о лабиринте.
• вычисляет минимальное известное путь длиной между все ненаблюдаемыми должности (и сам и назначения).
• определить приоритеты ненаблюдаемыми позиции для проверки на основе окружающие структуры. (если невозможно добраться до места назначения оттуда в любом случае...)
• может приоритизировать ненаблюдаемые позиции для проверки на основе направлении и на расстоянии до места назначения.
• может приоритизировать ненаблюдаемые позиции для проверки на основе опыт сбора информации. (как далеко он может видеть в среднем и как далеко он должен пешком?)
• может приоритизировать ненаблюдаемые позиции до найти возможные пути. (опыт: есть ли много петли?)

тот же ответ, что и на все вопросы о переполнении стека;)

использовать vi!

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

Это действительно увлекательно видеть, как текстовый редактор решает ascii-лабиринт, я уверен, что у парней emacs есть эквивалент ..

этот алгоритм Азкабана также может помочь вам, http://journals.analysisofalgorithms.com/2011/08/efficient-maze-solving-approach-with.html

лучший способ решить лабиринт-использовать алгоритм связности, такой как union-find, который является квазилинейным алгоритмом времени, предполагающим сжатие пути.

Union-Find-это структура данных, которая сообщает вам, являются ли два элемента в наборе транзитивно связанными.

чтобы использовать структуру данных union-find для решения лабиринта, сначала для построения структуры данных union-find используются данные соседних соединений. Затем находка объединения сжимается. Чтобы определить, является ли лабиринт разрешим значения входа и выхода сравниваются. Если они имеют одинаковое значение, то они связаны и лабиринт разрешима. Наконец, чтобы найти решение, вы начинаете с входа и изучаете корень, связанный с каждым из его соседей. Как только вы найдете ранее не посещенный сосед с тем же корнем, что и текущая ячейка, вы посетите эту ячейку и повторите процесс.

основным недостатком этого подхода является то, что он не скажет вам кратчайшие маршрут через лабиринт, Если есть более одного пути.

не специально для вашего случая, но я столкнулся с несколькими вопросами конкурса программирования, где я нашел ли довольно удобно кодировать быстро. Его не самый эффективный для всех случаев, но легко провернуть. Вот это один я взломал для конкурса.