Реализация дерева для лабиринта для использования в DFS, BFS

Question

Реализация дерева для лабиринта для использования в DFS, BFS

Моя программа принимает массив символов в качестве входных данных из файла. Массив выглядит так:

"#########",
"# #     #",
"# ##  # #",
"#     # #",
"### # ###",
"#   # # #",
"# # #####",
"#   #   #",
"#########",

Я реализую DFS и BFS, чтобы решить этот лабиринт, начиная с [1,1] и заканчивая [ширина — 1, высота — 1].

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

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

    for (int i = 0; i < width; i++)
{
for (int j = 0; j < height; j++)
{
if (isEmpty(maze[i][j]))
{
putChildren(maze[i-1][j], maze[i][j+1], maze[i+1][j]);
//this will check if it's a wall first
}
}

Это жизнеспособная тактика для реализации дерева, как это, а затем использовать его для обхода дерева с DFS и BFS, или я должен пойти на это другим путем?

6

breadth-first-search c++depth-first-search tree

Решение

Другие решения

Ваша идея хороша и довольно проста, но я думаю, что вы неправильно поняли дерево с графиком.

Прежде всего, нет необходимости создавать дерево из графа лабиринта — вы можете запустить BFS, DFS, A* , ... на общем графике.

Более того, не каждый лабиринт можно представить как дерево.

Давайте посмотрим на пример:

"#####",
"#   #",
"# # #",
"#   #",
"#####",

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

1

Источник

Accepted Answer

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

3