Теория программирования: решить лабиринт - PullRequest
67 голосов
/ 23 июня 2010

Каковы возможные способы решения лабиринта?
У меня есть две идеи, но я думаю, что они не очень элегантные.

Базовая ситуация: У нас есть матрица, и элементы в этой матрице упорядочены таким образом, что она представляет собой лабиринт с одним входом и одним выходом.

Моей первой идеей было отправить робота через лабиринт, следуя за одной стороной, пока он не выйдет из лабиринта. Я думаю, что это очень медленное решение.

Второй проходит через каждый последующий элемент, отмеченный 1, проверяет, куда он может пойти (вверх, вправо, вниз, влево), выбирает один путь и продолжает свой путь там. Это даже медленнее, чем первый.

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

Должны быть лучшие решения для отправки бота через лабиринт.

EDIT
Первое: спасибо за хорошие ответы!

Вторая часть моего вопроса: Что делать в случае, если у нас есть многомерный граф? Существуют ли специальные методы для этого, или ответ Джастина Л. можно использовать и для этого?
Я думаю, что это не лучший способ для этого случая.

Третий вопрос:
Какой из этих алгоритмов решения лабиринта является / является самым быстрым? (Чисто гипотетически)

Ответы [ 14 ]

157 голосов
/ 23 июня 2010

Вы можете думать о своем лабиринте как о дереве.

     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)

Где каждый узел является соединением путей. D, I, J, L и O - тупики, а ** - цель. Конечно, в вашем реальном дереве каждый узел может иметь до трех дочерних элементов.

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

Глядя на дерево, довольно легко увидеть ваше правильное решение, просто "проследив" от ** в самой глубокой части дерева:

A B E H M **

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

Теперь давайте посмотрим на ваше первое упомянутое решение, примененное к этому дереву.

Ваше первое решение - это, по сути, Поиск в глубину , что на самом деле не так уж и плохо. На самом деле это довольно хороший рекурсивный поиск. По сути, он гласит: «Всегда сначала выбирай самый правый подход. Если там ничего нет, возвращайся назад до первого места, куда ты можешь идти прямо или налево, а затем повтори».

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

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

Обратите внимание, что вы можете остановиться, как только найдете **.

Однако, когда вы на самом деле кодируете поиск в глубину, использование рекурсивного программирования делает все намного проще. Даже итерационные методы тоже работают, и вам никогда не придется явно программировать, как откатываться назад. Проверьте связанную статью для реализаций.

Другим способом поиска дерева является решение Breadth-First , которое ищет по деревьям по глубине. Он будет искать через указанное дерево в следующем порядке:

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

Обратите внимание, что из-за характера лабиринта ширина в ширину имеет гораздо большее среднее количество узлов, которые он проверяет. В ширину легко реализовать, имея очередь путей для поиска, и каждая итерация выталкивает путь из очереди, «взрывая» его, получая все пути, в которые он может превратиться после одного шага, и помещая эти новые пути в конце очереди. В коде нет явных команд «следующего уровня», и они просто были там, чтобы помочь в понимании.

Фактически, существует целый обширный список способов поиска дерева . Я только что упомянул два самых простых, самых простых способа.

Если ваш лабиринт очень, очень длинный и глубокий, имеет петли и сумасшествия, и является сложным, я предлагаю алгоритм A *, который является стандартным алгоритмом поиска пути который объединяет поиск по ширине с эвристикой ... вроде как «интеллектуальный поиск по ширине».

В основном это работает так:

  1. Поместите один путь в очередь (путь, по которому вы идете только один шаг прямо в лабиринт). У пути есть «вес», определяемый его текущей длиной + прямолинейным расстоянием от конца (которое может быть вычислено математически)
  2. Выведите путь с наименьшим весом из очереди.
  3. «Взрывайте» путь на каждом пути, каким он может быть после одного шага. (т. е. если ваш путь - справа налево, слева направо, то ваши разнесенные пути - это R L L R R и R L L R L, не считая нелегальных, проходящих через стены)
  4. Если у одного из этих путей есть цель, тогда Победа! В противном случае:
  5. Рассчитайте вес взорванных путей и поместите все их обратно в очередь (не включая исходный путь)
  6. Сортировка очереди по весу, сначала самая низкая. Затем повторите с шага № 2

И это A *, который я представляю специально выделенным, потому что это более или менее стандартный отраслевой алгоритм поиска путей для всех приложений поиска путей, включая перемещение от одного края карты другому, избегая бездорожья или гор, и т. д. Он работает так хорошо, потому что использует эвристический алгоритм кратчайшего расстояния , который придает ему «интеллект». A * настолько универсален, потому что, учитывая любую проблему, если у вас есть эвристика минимально возможного расстояния (у нас это просто - прямая линия), вы можете применить ее.

НО очень важно отметить, что A * является не вашим единственным вариантом.

Фактически, категория алгоритмов обхода дерева содержит только 97! (лучшее все еще будет на этой странице ссылка ранее)

Извините за длину = P (я склонен бродить)

13 голосов
/ 23 июня 2010

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

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

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

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

11 голосов
/ 23 июня 2010

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

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

4 голосов
/ 23 июня 2010

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

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
4 голосов
/ 23 июня 2010

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

3 голосов
/ 18 сентября 2014

Это очень простое представление для симуляции лабиринта в 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
2 голосов
/ 23 июня 2010

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

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

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

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

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


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

1 голос
/ 03 декабря 2013

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

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

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

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

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

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

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

1 голос
/ 23 июня 2010

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

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 как начало и конец.

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

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