Построение дерева из массива для решателя DFS
Я делаю решатель лабиринтов, используя DFS, и я хочу реализовать дерево поиска для него, но я немного новичок в искусственном интеллекте, и я хочу немного помочь в этом вопросе.
Позвольте мне привести пример лабиринта:
char maze[5][9] =
"#########",
"# # #",
"# ## # #",
"# # #",
"#########",
Поэтому мое дерево поиска для DFS должно выглядеть примерно так:
"#########",
"#12#15 10 11 #",
"#3##14 9 #12 #",
"#456 7 8 #13 #",
"#########",
1-й ребенок родителя -> Правая ячейка, если она пуста
2-й ребенок родителя -> Нижняя ячейка, если она пуста
3-й ребенок родителя -> Левая ячейка, если она пуста
4-й ребенок родителя -> Верхняя ячейка, если она пуста
Мой решатель получит в качестве аргумента мой массив лабиринтов. У меня такие вопросы:
1-й вопрос: действительно ли так будет посещаться узлы моим актером?
2-й вопрос: нужно ли в коде объявлять 15 как ребенка от 10? (также в других случаях, таких как 9 с 14)
Третий вопрос: когда мой решатель получает массив, мне нужно сделать предварительную обработку массива и построить дерево из массива, или мой актер построит его по ходу дела?
Решение
Я также предполагаю правило «не включать узел в дерево решений, если он уже был в дереве»? Потому что это точно помогает.
Обычно дерево неявно, и вы строите только те части дерева, которые вы на самом деле посещаете, часто снося вещи вниз, когда вы откатываете их назад.
Ваш решатель отслеживает текущие шаги вдоль дерева. Вы, вероятно, также хотите отслеживать, какие клетки вы исследовали в лабиринте. Если лабиринт имеет только # а также персонажи, использовать * чтобы указать, что вы посетили ячейку в этом решателе.
Вы начинаете в каком-то месте. Если это местоположение действительно, вы отмечаете его * так что вы не возвращаетесь к нему и не добавляете это местоположение (скажем, (1,1)) к вашему «стеку» вашего пути.
Теперь вы следуете правилам, которые вы написали выше. Проверьте ячейку под вашим текущим местоположением. Это пусто? (не # или *) Если это так, повторяйте, спрашивая, найдет ли это выход.
Если он находит выход, возьмите найденный путь, добавьте текущий узел и верните этот путь как выход.
Если этого не произойдет, выполните поиск в соседней ячейке (в порядке, указанном выше).
Наконец, оберните вышеупомянутую рекурсивную процедуру функцией, которая ее вызывает, затем удалите * отметки от карты.
Дерево, по которому вы идете, неявно закодировано. Построение дерева вынуждает вас посещать каждый узел, и вы хотите построить только те части, которые вам нужны.
Это может быть оптимизировано несколькими способами. Вы можете избежать записи на карту, работая над «призрачной» копией. Вы можете избежать предварительной подготовки, передавая стек рекурсивным версиям, которые тщательно удаляют любые дополнительные узлы, если они выходят из строя, и оставляют их включенными в случае успеха. Или вы можете использовать реальный стек и кодировать путь назад, с функцией обертывания, которая (после того, как вся работа сделана) переворачивает путь, чтобы он находился в более обычном порядке.
Другие решения
Других решений пока нет …
detector