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

Ответ 1

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

     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)

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

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

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

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 *, который является стандартным алгоритмом поиска пути, который объединяет поиск по методу "Ширина-Первый" с эвристикой... вроде как "интеллектуальный поиск по ширине".

В основном он работает следующим образом:

• Поместите один путь в очередь (путь, по которому вы только пройдите один шаг прямо в лабиринт). Путь имеет "вес", определяемый его текущей длиной + его прямым расстоянием от конца (который можно вычислить математически)
• Введите путь с наименьшим весом из очереди.
• "Взорвать" путь на каждый путь, который может быть после одного шага. (т.е. если ваш путь находится справа слева влево, то ваши взорванные пути: R L L R R и R L L R L, не считая незаконных, которые проходят через стены).
• Если у одного из этих путей есть цель, то Победа! В противном случае:
• Рассчитайте весы взорванных путей и поместите все их обратно в очередь (не включая исходный путь)
• Сортировка очереди по весу, сначала самая низкая. Затем повторите шаг 2.

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

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

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

Извините за длину = P (я имею тенденцию бегать)

Ответ 2

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

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

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

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

Ответ 3

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

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

Ответ 4

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

Ответ 5

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

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

Ответ 6

Это очень простое представление для моделирования лабиринта в С++:)

#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 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

Ответ 7

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

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

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

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

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

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

Ответ 8

У меня была аналогичная проблема в одном из моих университетских 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 являются началом и концом.

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

Ответ 9

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

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

Ответ 10

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

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

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

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

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

Ответ 11

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

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

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

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

Ответ 12

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

Ответ 13

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

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

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

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

Ответ 14

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