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

Моя программа принимает массив символов в качестве входных данных из файла. Массив выглядит следующим образом:Реализация дерева для лабиринта для использования в 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, или я я должен идти на это по-другому?

источник

2013-11-06 Powerbyte

Какой язык вы используете? –

C++ (я его отредактирую) – Powerbyte

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

источник

2013-11-06 20:22:00 Esavier

Я на самом деле планирую реализацию A * позже, но сначала я хочу реализовать DFS и BFS. Я в значительной степени хочу реализовать их все, чтобы проявить свой ум и познакомиться с ними и вообще с искусственным интеллектом. – Powerbyte

Я много работаю в области ИИ, и если я могу дать совет, нет хорошего способа решения проблемы. То, что вам нужно сделать, - это подготовиться к тому, чтобы вам понадобились оба алгоритма для реализации и выбора лучшего для ситуации (после анализа проблем). Тем не менее, чтобы сделать решение лабиринта максимально возможным, вы должны разрешить свое «ощущающее» окружение. Также рассмотрите возможность создания 2D (с «посещенным» флагом bool) вместо графика. В некоторых случаях это проще, чем-то сложнее, но стоит реализовать над обычным графиком) – Esavier

следующий, даже если вы используете график, используйте флаг посещения, если вы будете в тупике, вы можете стереть их обратно. Ue жадный алгоритм, который найдет u самым быстрым решением и вернет его. Существует также хороший алгоритм (но должен был реализоваться), называемый маркировкой заполнения залива. Вы должны предположить, что в комнатах есть проходы между ними и отмечены только те отрывки в дереве, а также «начало» и «конец», заливка залива будет рассматривать только проходимые пути и должна отбрасывать любые шаги, такие как открытая комната или тупики. – Esavier

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

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

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

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

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

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

источник

2013-11-24 12:35:11 pkacprzak

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

ответ

Смежные вопросы