Применение поиска на графах для решения задач о лабиринте Дегтярев Юрий гр. 3057/2

2 Постановка задачи Задан конечный 4-связный лабиринт. Необходимо найти кратчайший путь из А в B или установить, что такого пути не существует Задача о лабиринте

3 Замечания 1)Сложность алгоритма А1 – O(n), n – кол-во клеток в лабиринте 2)Если отказаться от построения графа и использовать информацию о проходимости напрямую, то получим волновой алгоритм 3)Применение – поиск кратчайших путей в 4-связном пространстве Алгоритм A1 1)Построить граф следующим образом: каждой клетке сопоставляется вершина; если соседние клетки x, y не разделяет стенка, то в граф добавляется ребро (x, y) 2)Запустить поиск в ширину [1] из вершины A 3)Если в процессе поиска в ширину достигнута вершина B, восстановить по подграфу предшествования путь из А в B и завершить работу 4)Если поиск в ширину завершил работу и вершина B не была посещена, то пути не существует Построенный граф Серым отмечен искомый путь

4 Постановка задачи Задан конечный лабиринт. Необходимо найти кратчайший путь из А в B или установить, что такого пути не существует, при условии, что перемещение может осуществляться только от одной границы до другой Задача о шарике в лабиринте

5 Алгоритм A2 1)Построить граф следующим образом: каждой клетке сопоставляется вершина; ребро соединяет вершины, если у обеих клеток, соответствующих вершинам находятся стенки, перпендикулярные ребру и не пересекающие его 2)Запустить поиск в ширину [1] из вершины A 3)Если в процессе поиска в ширину достигнута вершина B, восстановить по подграфу предшествования путь из А в B и завершить работу 4)Если поиск в ширину завершил работу и вершина B не была посещена, то пути не существует Замечания 1)Сложность алгоритма А2 – O(n), n – кол-во клеток в лабиринте 2)Алгоритм А2 отличается от алгоритма А1 только этапом построения графа (пункт 1) Построенный граф Серым отмечен искомый путь

6 Задача о лабиринте (модификация) Постановка задачи Постановка задачи аналогична задаче о лабиринте, но стенки могут быть проходимы в одну сторону

7 Серым отмечен искомый путь Построенный орграф Замечание 1)Сложность алгоритма А3 – O(n), n – кол-во клеток в лабиринте Алгоритм A3 1)Построить орграф следующим образом: каждой клетке сопоставляется вершина; если соседние клетки x, y не разделяет стенка, то в орграф добавляются дуги (x, y) и (y, x). Если соседние клетки x, y разделяет проходимая стенка, то добавляется дуга (x, y) или (y, x) в зависимости от направления проходимости 2)Запустить поиск в ширину из вершины A 3)Если в процессе поиска в ширину достигнута вершина B, восстановить по подграфу предшествования путь из А в B и завершить работу 4)Если поиск в ширину завершил работу и вершина B не была посещена, то пути не существует

8 Постановка задачи Задан конечный 4-связный лабиринт. Необходимо найти путь для агента из А в B или установить, что такого пути не существует Задача об агенте в лабиринте Алгоритм A4 1)Отметить начальную клетку A какпосещенную (запомнить ее координаты, добавить в список посещенных клеток ) 2)Для начальной клетки выбрать соседнюю клетку так, чтобы она была не посещенной и чтобы начальную и выбираемую клетку не разделяла стенка. Если такой клетки нет, то пути не существует, завершение алгоритма 3)Перейти в выбранную клетку. Сделать выбранную клетку текущей, запомнить для текущей клетки предыдущую. Отметить текущую клетку как посещенную. Если текущая клетка - B, то завершить алгоритм Стрелочками показаны предыдущие клетки ( откуда пришли )

9 Алгоритм А4 ( продолжение ) 4)Для текущей клетки выбрать соседнюю клетку так, чтобы она была не посещенной и чтобы текущую и выбираемую клетку не разделяла стенка. Если такая клетка существует, то перейти к пункту 3), иначе к пункту 5) 5)Если предыдущая клетка - А, то пути не существует, завершение алгоритма. Иначе перейти в предыдущую клетку. Перейти к пункту 4) Замечания 1)Алгоритм работает подобно поиску в глубину [2] для графа, построенного для данного лабиринта 2)В худшем случае агент пройдет по каждой связи по два раза ( связью назовем переход между соседними клетками, не разделенными стенкой ) 3)Сложность алгоритма А4 – O(n), n – кол- во клеток в лабиринте Пунктиром отмечен возврат из тупика

10 Вывод 1)В рассмотренных задачах граф может быть задан неявно – информацией о проходимости в каждой клетке. Таким образом, можно отказаться от построения графа, и использовать эту информацию напрямую 2)Для решения задачи о лабиринте, в качестве алгоритма поиска на графе, лучше применять алгоритм A* [3], при условии отсутствия нуль-переходов (ребер нулевого веса) 3)При наличии нуль-переходов лучше применять поиск в ширину [1]

11 Литература 1)Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. Издание 2-е. Гл. 22 п.2, стр )Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. Издание 2-е. Гл. 22 п.3, стр )Нильсон Н. Искусственный интеллект. Методы поиска решений. Гл. 3 п.8 стр. 70