Теория программирования: решить лабиринт
Каковы возможные способы решить лабиринт?
У меня есть две идеи, но я думаю, что они не очень элегантны.
Базовая ситуация: у нас есть матрица, и элементы в этой матрице упорядочены таким образом, что она представляет лабиринт с одним входом и одним выходом.
Моей первой идеей было отправить робота через лабиринт, следуя по одной стороне, пока он не выйдет из лабиринта. Я думаю, что это очень медленное решение.
Второй проходит через каждый последующий элемент, отмеченный 1, проверяет, куда он может пойти (вверх, вправо, вниз, влево), выбирает один путь и продолжает свой путь там. Это даже медленнее, чем первый.
Конечно, будет немного быстрее, если я сделаю двух ботов многопоточными на каждом перекрестке, но это тоже не лучший способ.
Должны быть лучшие решения для отправки бота через лабиринт.
РЕДАКТИРОВАТЬ
Первое: спасибо за хорошие ответы!
Вторая часть моего вопроса: что делать в случае, если у нас есть многомерный граф? Существуют ли специальные методы для этого, или ответ Джастина Л. можно использовать и для этого?
Я думаю, что это не лучший способ для этого случая.
Третий вопрос:
Какой из этих алгоритмов решения лабиринта является / является самым быстрым? (Чисто гипотетически)
14 ответов
Вы можете думать о своем лабиринте как о дереве.
/ \
/ \
До нашей эры
/ \ / \
D E F G
/ \ \
H I J
/ \
L M
/ \
** O
(который мог бы представлять)
НАЧНИТЕ
+ +---+---+
| A C G |
+---+ + + +
| БД | F | J |
+---+---+ +---+---+
| L H E I |
+---+ +---+---+
| МО |
+ +---+
КОНЕЦ
(игнорируя левый-правый порядок на дереве)
Где каждый узел - это соединение путей. 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
Обратите внимание, что вы можете остановиться, как только найдете **.
Однако, когда вы на самом деле кодируете поиск в глубину, использование рекурсивного программирования делает все намного проще. Даже итерационные методы тоже работают, и вам никогда не придется явно программировать, как откатываться назад. Проверьте связанную статью для реализаций.
Другим способом поиска дерева является решение " Ширина вначале", которое ищет по деревьям по глубине. Он будет искать через вышеуказанное дерево в следующем порядке:
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 (я склонен бродить)
Существует множество алгоритмов решения лабиринтов:
http://en.wikipedia.org/wiki/Maze_solving_algorithm
http://www.astrolog.org/labyrnth/algrithm.htm
Для робота алгоритм Тремо выглядит многообещающим.
Интересный подход, по крайней мере мне он показался интересным, заключается в использовании клеточных автоматов. Короче говоря, "космическая" ячейка, окруженная 3 "настенными" ячейками, превращается в "настенную" ячейку. В конце остаются только космические ячейки на пути к выходу.
Если вы посмотрите на дерево, которое Джастин вставил в свой ответ, то увидите, что узлы листьев имеют 3 стены. Чернослив дерево, пока у вас нет пути.
Это один из моих любимых алгоритмов когда-либо....
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
У меня была похожая проблема в одном из моих университетов 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 быть началом и концом.
Со всем, что не следует за стеной, вы в конечном итоге должны вести список мест, где вы были, чтобы вы могли вернуться в случае необходимости, когда вы попали в тупик, и чтобы вас не поймали в петле. Если вы следуете за стеной, нет необходимости отслеживать, где вы были. Хотя вы не найдете наиболее оптимальный путь через лабиринт, вы всегда будете проходить через него.
Как насчет построения графика из вашей матрицы и использования поиска по ширине, поиска по глубине или алгоритма Дейкстры?
Это очень простое представление для моделирования лабиринта в 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, которые имеют несколько непрерывных дорог таким образом:
-от начала до некоторой точки
или - от какой-то точки до конца
Мы запускаем нового бота поколения 1 в новых случайных точках, затем пытаемся соединить дороги ботов поколения 1 с таковыми из поколения 0 и посмотреть, получим ли мы непрерывную дорогу от начала до конца.
Поэтому для genn мы пытаемся соединиться с ботами вида gen0, gen1, ..., genn-1.
Конечно, поколение длится лишь конечное количество времени.
Я не знаю, окажется ли цвет алгоритма практичным для небольших наборов данных.
Также алгоритм предполагает, что мы знаем начальную и конечную точки.
несколько хороших сайтов для идей:
http://citeseerx.ist.psu.edu/
http://arxiv.org/
Тот же ответ, что и на все вопросы о переполнении стека;)
Используйте vi!
http://www.texteditors.org/cgi-bin/wiki.pl?Vi-Maze
Действительно интересно видеть, как текстовый редактор решает ascii-лабиринт, я уверен, что у ребят из Emacs есть аналог...
Есть много алгоритмов и множество различных настроек, которые определяют, какой алгоритм лучше. это всего лишь одна идея об интересной обстановке:
давайте предположим, что у вас есть следующие свойства...
- Вы перемещаете робота и хотите минимизировать его перемещение, а не использование процессора.
- этот робот может либо осматривать только свои соседние клетки, либо смотреть по коридорам, либо видя, либо не видя перекрестки.
- у него есть GPS.
- он знает координаты своего пункта назначения.
тогда вы можете создать AI, который...
- рисует карту - каждый раз, когда он получает новую информацию о лабиринте.
- вычисляет минимальные известные длины пути между всеми ненаблюдаемыми позициями (и самим собой, и пунктом назначения).
- может расставить приоритеты для ненаблюдаемых позиций для проверки на основе окружающих структур. (если невозможно добраться до места назначения в любом случае...)
- может расставить приоритеты для ненаблюдаемых позиций для проверки на основе направления и расстояния до места назначения.
- может расставить приоритеты для ненаблюдаемых позиций для проверки на основе опыта сбора информации. (Как далеко он может видеть в среднем и как далеко он должен идти?)
- может расставить приоритеты для ненаблюдаемых позиций, чтобы найти возможные ярлыки. (опыт: много ли петель?)
Не специально для вашего случая, но я натолкнулся на несколько вопросов о конкурсе по программированию, где я нашел алгоритм Ли весьма удобным для быстрого кодирования. Это не самый эффективный для всех случаев, но легко провернуть. Вот один, который я взломал для конкурса.
Этот алгоритм Азкабана может также помочь вам, http://journals.analysisofalgorithms.com/2011/08/efficient-maze-solving-approach-with.html
Лучший способ решить лабиринт - использовать алгоритм связности, такой как union-find, который представляет собой квазилинейный алгоритм времени, предполагающий, что сжатие пути выполнено.
Union-Find - это структура данных, которая сообщает, транзитивно ли связаны два элемента в наборе.
Чтобы использовать структуру данных объединения-поиска для решения лабиринта, сначала используются данные о соединении соседей, чтобы построить структуру данных объединения-поиска. Тогда союзная находка сжимается. Чтобы определить, является ли лабиринт разрешимым, сравниваются входные и выходные значения. Если они имеют одинаковое значение, то они связаны, и лабиринт разрешим. Наконец, чтобы найти решение, вы начинаете со входа и изучаете корень, связанный с каждым из его соседей. Как только вы найдете ранее не посещенного соседа с тем же корнем, что и текущая ячейка, вы посещаете эту ячейку и повторяете процесс.
Основным недостатком этого подхода является то, что он не скажет вам кратчайший маршрут через лабиринт, если существует более одного пути.