7619
Комментарий:
|
← Версия 6 от 2018-10-28 15:18:36 ⇥
7677
|
Удаления помечены так. | Добавления помечены так. |
Строка 25: | Строка 25: |
'''Алгоритм решения''': | === Алгоритм решения === |
Строка 31: | Строка 31: |
1. Устанавливаем в этой вершине текущий шаг разведки | 1. Устанавливаем в этой вершине текущий шаг просмотра |
Строка 33: | Строка 33: |
1. Если ребро ведёт в проходимую вершину с нулевым шагом разведки (неразведанную): | 1. Если ребро ведёт в проходимую вершину с нулевым шагом просмотра (неразведанную): |
Строка 35: | Строка 35: |
1. Если шаг разведки у вершины выхода нулевой, то пути нет | 1. План разведки пуст. Если шаг просмотра у вершины-выхода нулевой, то пути нет |
Строка 38: | Строка 38: |
'''Определение минимального пути''' | === Определение минимального пути === |
Строка 40: | Строка 40: |
Иногда требуется не только оценить длину пути, но и вывести его. Это легко сделать с помощью поля «шаг разведки», ''в случае неориентированного графа'', т. е. когда связь ''A→B'' означает также и связь ''B→A'' . Построим путь с конца: | Иногда требуется не только оценить длину пути, но и вывести его. Это легко сделать с помощью поля «шаг просмотра», ''в случае неориентированного графа'', т. е. когда связь ''A→B'' означает также и связь ''B→A'' . Построим путь с конца: |
Строка 42: | Строка 42: |
1. Пока шаг разведки текущего поля больше '''1''' (т. е. оно не вход): 1. Из всех рёбер, ведущих ''в'' текущее поле выберем любое, шаг разведки которого на '''1''' меньше текущего шага разведки. Такое поле есть по построению. |
1. Пока шаг просмотра текущего поля больше '''1''' (т. е. оно не вход): 1. Из всех рёбер, ведущих ''в'' текущее поле выберем любое, шаг просмотра которого на '''1''' меньше текущего шага просмотра. Такое поле есть по построению. |
Строка 48: | Строка 48: |
'''Немного анализа''': | === Немного анализа === |
Строка 50: | Строка 50: |
Вычислительная сложность:: Количество просмотров атрибута проходимости и поля «шаг разведки» сопоставимо с произведением количества объектов и максимального количества связей, которое может иметь один объект. Количество операций добавления и снятия со стека, как и количество модификаций поля «шаг разведки», не больше количества объектов. | Вычислительная сложность:: Количество просмотров атрибута проходимости и поля «шаг просмотра» сопоставимо с произведением количества объектов и максимального количества связей, которое может иметь один объект. Количество операций добавления и снятия со стека, как и количество модификаций поля «шаг просмотра», не больше количества объектов. |
Задача «обход лабиринта»
Задача обхода лабиринта — неформальное название частного случая задачи «проверка связности неориентированного графа». Случай этот частный, потому что (как правило) в задаче требуется либо проверить достижимость одной вершины графа из другой, либо вдобавок найти минимальный путь.
- Классическая формулировка
Лабиринт задан массивом M×N, каждый элемент массива соответствует участку лабиринта, проходимые участки отмечены, скажем, 1, непроходимые — 0. Перемещаться можно только по соседним по вертикали или горизонтали проходимым участкам. Требуется, допустим, проверить, можно ли добраться из левого верхнего участка лабиринта в правый нижний (или указать минимальный путь).
Задача имеет множество маскировочных вариаций: лабиринт может быть многомерный или треугольный, вместо карты лабиринта может предлагаться таблица связности, ограничиваться направление и т. д.
Все эти формулировки имеют в себе вот такое общее:
- В задаче фигурируют объекты и связи между ними; требуется проверить, ведёт и цепочка связей от одного заданного объекта к другому
Собственно, это и есть граф, объекты — его вершины, а связи — рёбра
Связи объектов заданы явно: объём входных данных сопоставим с количеством связей и количеством объектов
- Например, «классическая формулировка» ограничивает количество объектов, а таблица связности — количество связей.
- Ни связи, ни объекты не изменяются после их задания
⇒ Понятие «состояние» при обходе графа включает в себя только идентификатор текущей вершины (объекта)
Предлагаемое решение, называемое в народе «методом заливки», является упрощённым алгоритмом Дейкстры. Это название возникло оттого, что изначально при его работе модифицировались исходные данные — по принципу, сходному с алгоритмом закрашивания связной области пикселей растрового изображения.
Для решения нам понадобится:
- Копия исходных данных или новая структура на их основе:
- Каждая вершина имеет служебное поле «шаг просмотра», которое изначально нулевое и модифицируется алгоритмом
- «План разведки»:
- Изначально пустой стек, способный хранить идентификаторы вершин
Алгоритм решения
Добавляем в план разведки идентификатор вершины-входа в лабиринт; её шаг просмотра делаем равным 1
- Производим разведку, пока план разведки не пуст:
Увеличиваем шаг просмотра на 1
- Забираем очередную вершину из плана разведки (её там не остаётся)
- По всем рёбрам, исходящим из данной вершины:
- Устанавливаем в этой вершине текущий шаг просмотра
- Если ребро ведёт в выход, успешно заканчиваем разведку
- Если ребро ведёт в проходимую вершину с нулевым шагом просмотра (неразведанную):
- Добавляем её в план разведки
- План разведки пуст. Если шаг просмотра у вершины-выхода нулевой, то пути нет
Если он ненулевой — это длина минимального пути (+1, да )
Определение минимального пути
Иногда требуется не только оценить длину пути, но и вывести его. Это легко сделать с помощью поля «шаг просмотра», в случае неориентированного графа, т. е. когда связь A→B означает также и связь B→A . Построим путь с конца:
- Назначим поле-выход «текущим», путь сделаем пустым списком
Пока шаг просмотра текущего поля больше 1 (т. е. оно не вход):
Из всех рёбер, ведущих в текущее поле выберем любое, шаг просмотра которого на 1 меньше текущего шага просмотра. Такое поле есть по построению.
- Добавим в начало пути ребро между выбранным и текущим полем
- Назначим выбранное поле текущим
В случае ориентированного графа нам понадобится ещё одно поле вершины — «обратный путь» — в которое при добавлении в план разведки мы будем записывать идентификатор предыдущей вершины.
Немного анализа
- Расход памяти
- Копия исходных данных плюс план разведки, сравнимый по объёму с количеством объектов.
- Вычислительная сложность
- Количество просмотров атрибута проходимости и поля «шаг просмотра» сопоставимо с произведением количества объектов и максимального количества связей, которое может иметь один объект. Количество операций добавления и снятия со стека, как и количество модификаций поля «шаг просмотра», не больше количества объектов.