Материал: АиСД. Проектная работа

1.2.4 Примеры лабиринтов

Следующие лабиринты сгенерированы алгоритмами генерации неидеальных лабиринтов файла-программы imperfect_maze.py (см. раздел «Код программы»).

31

2. ПОИСК КРАТЧАЙШЕГО ПУТИ В ЛАБИРИНТАХ

2.1 Алгоритм итеративного поиска в ширину Алгоритм итеративного поиска в ширину для матрицы — алгоритм поиска

кратчайшего пути в матрице (лабиринте).

Алгоритм:

1.Пусть — стартовая ячейка, — конечная ячейка, — пустой ассоциативный массив родителей, — очередь.

2.Начинаем со стартовой ячейки .

3.Добавляем в стартовую ячейку с ассоциативным значением самой стартовой ячейки. [ ] = .

4.Добавляем в очередь стартовую ячейку .

5.Пока очередь не пуста:

•Берём элемент из очереди (с удалением) — текущий элемент.

•Если он является конечной ячейкой , то выходим из цикла.

•Для каждого соседа вокруг текущей ячейки:

oЕсли сосед не ограждён стеной и не был посещён ранее (его нет в), то добавляем его в очередь , а также добавляем его вв качестве ключа со значением текущей ячейки

[ ] = .

6.Пусть — путь от начальной к конечной ячейке (т. е. список ячеек).

7.Если текущая ячейка является конечной ячейкой , то

•Добавляем в текущую ячейку .

•Пока текущая ячейка не является начальной ячейкой:

oТекущей ячейкой становится [ ]. oДобавляем в текущую ячейку .

8. Возвращаем в реверсивном (обратном) порядке.

Причём: алгоритм можно упростить так, что реверс в конце не потребуется: следует начать не со стартовой ячейки, а с конечной, и идти к стартовой.

Свойства алгоритма:

•Эвристики отсутствуют: может искать там, где не нужно.

•Поиск происходит методом полного обхода в ширину.

Примеры работы алгоритма можно посмотреть в «2.4 Примеры поиска».

2.2 Алгоритм Дейкстры Алгоритм Дейкстры для матрицы — алгоритм поиска кратчайшего пути в

битовой матрице (лабиринте).

Алгоритм:

1.Пусть — стартовая ячейка, — конечная ячейка, — пустой ассоциативный массив родителей, — пустой ассоциативный массив стоимостей, — приоритетная очередь (по возрастанию стоимостей).

2.Начинаем со стартовой ячейки .

3.Добавляем в стартовую ячейку с ассоциативным значением самой стартовой ячейки. [ ] = .

4.Добавляем в стартовую ячейку с ассоциативным значением 0.

5.Добавляем в очередь стартовую ячейку с приоритетным значением 0.

6.Пока очередь не пуста:

32

•Берём элемент из очереди (с удалением) — текущий элемент.

•Если он является конечной ячейкой , то выходим из цикла.

•Новая стоимость = [ ] + 1.

•Для каждого соседа вокруг текущей ячейки:

oЕсли сосед не ограждён стеной и стоимость меньше стоимости

[ ] (или не содержит ), то устанавливаем [ ] равным , обновляем соседа вв качестве ключа со значением текущей ячейки

[ ] = , добавляем соседа в очередь с

приоритетным значением .

7.Пусть — путь от начальной к конечной ячейке (т. е. список ячеек).

8.Если текущая ячейка является конечной ячейкой , то

•Добавляем в текущую ячейку .

•Пока текущая ячейка не является начальной ячейкой:

oТекущей ячейкой становится [ ]. oДобавляем в текущую ячейку .

9. Возвращаем в реверсивном (обратном) порядке.

Причём: алгоритм можно упростить так, что реверс в конце не потребуется: следует начать не со стартовой ячейки, а с конечной, и идти к стартовой.

Свойства алгоритма:

•Эвристики отсутствуют: может искать там, где не нужно.

•Поиск происходит методом полного обхода в ширину (с дополнительными

затратами), так как задано независимое отношение =[ ] + 1. Вместо этого можно сделать зависимое отношение

= [ ] + (, ), где — функция,

возвращающая неотрицательную стоимость между первой и второйячейкой. Т. е. добавляются возможности по управлению поиском в соответствии с разными стоимостями для разных путей (может быть полезно, если работать с 2D лабиринтом как с 3D со спусками и подъёмами). Следовательно, при независимом отношении выигрыша по времени работы не будет по сравнению с временем работы алгоритма поиска в ширину.

Примеры работы алгоритма можно посмотреть в «2.4 Примеры поиска».

2.3 Алгоритм A*

Алгоритм A* для матрицы — алгоритм поиска кратчайшего пути в битовой матрице (лабиринте).

Алгоритм:

1.Пусть — стартовая ячейка, — конечная ячейка, — пустой ассоциативный массив родителей, — пустой ассоциативный массив стоимостей, — приоритетная очередь (по возрастанию стоимостей).

2.Начинаем со стартовой ячейки .

3.Добавляем в стартовую ячейку с ассоциативным значением самой стартовой ячейки. [ ] = .

4.Добавляем в стартовую ячейку с ассоциативным значением 0.

5.Добавляем в очередь стартовую ячейку с приоритетным значением 0.

6.Пока очередь не пуста:

33

•Берём элемент из очереди (с удалением) — текущий элемент.

•Если он является конечной ячейкой , то выходим из цикла.

•Новая стоимость = [ ] + 1.

•Для каждого соседа вокруг текущей ячейки:

oЕсли сосед не ограждён стеной и стоимость меньше стоимости

[ ] (или не содержит ), то устанавливаем [ ] равным , обновляем соседа вв качестве ключа со значением текущей ячейки

[ ] = , добавляем соседа в очередь с приоритетным значением + (, ), где

(( 1, 1), ( 2, 2)) — функция эвристики, возвращающая абсолютное (неотрицательное) значение*.

7.Пусть — путь от начальной к конечной ячейке (т. е. список ячеек).

8.Если текущая ячейка является конечной ячейкой , то

•Добавляем в текущую ячейку .

•Пока текущая ячейка не является начальной ячейкой:

oТекущей ячейкой становится [ ]. oДобавляем в текущую ячейку .

9. Возвращаем в реверсивном (обратном) порядке.

Причём: алгоритм можно упростить так, что реверс в конце не потребуется: следует начать не со стартовой ячейки, а с конечной, и идти к стартовой.

* (, ). Функция, которая возвращает абсолютное значение расстояния между текущей ячейкой и конечной ячейкой .

Свойства алгоритма:

•Эвристики присутствуют: ищет там, где ближе всего может находится конечная ячейка.

•Поиск происходит методом полного обхода в ширину с учётом стоимостей, так

поиском в соответствии с разными стоимостями для разных путей (может быть полезно, если работать с 2D лабиринтом как с 3D со спусками и подъёмами), добавляется возможность строго направленного поиска. Следовательно, выигрыш будет по сравнению с поиском в ширину только в случае неидеальных лабиринтов с большим количеством свободных ячеек.

Возможные эвристики:

•Расстояние Евклида (прямая линия).

Расстояние измеряется по прямой линии от начальной до конечной точки. Аналог в шахматах: пешка (может ходить только в одну сторону).

√(2 − 1)2 + ( 2 − 1)2

•Расстояние Манхэттена L1 (4 направления).

Расстояние измеряется 4 направлениями от начальной до конечной точки. Аналог в шахматах: ладья (может ходит только по 4 направлениям).

| 2 − 1| + | 2 − 1|

•Расстояние «Октиль» (Octile) (диагонали).

Расстояние измеряется диагоналями от начальной до конечной точки.

34

Аналог в шахматах: слон (может ходить только по диагоналям).

max(| 2 − 1|, | 2 − 1|) + (√2 − 1) min(| 2 − 1|, | 2 − 1|)

•Расстояние Чебышёва (4 направления и диагонали).

Расстояние измеряется 4 направлениями и диагоналями (шахматными проходами) от начальной до конечной точки.

Аналог в шахматах: ферзь (может ходить по 4 направлениям и диагоналям).

max(| 2 − 1|, | 2 − 1|)

Алгоритм А* имеет важное достоинство по сравнению с другими: можно задавать эвристическую функцию, которая может либо концентрироваться на прямолинейном пути (если какую-либо эвристику возвести в приемлемую степень), либо работать как поиск в ширину (возвращать -1 при любых входных данных) или алгоритм Дейкстры (возвращать 0 при любых входных данных), что даёт большие возможности для корректировки поиска.

Примеры работы алгоритма можно посмотреть в «2.4 Примеры поиска».

35