Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Рекурсивная процедура поиска в ширинуПоиск в глубину хорошо работает в таких пространствах состояний, где и тупики, и решения удалены примерно на одно и то же расстояние от начала поиска. Наиболее плохой случай для поиска в глубину следующий: какая-то ветвь графа состояний очень протяженная или бесконечная, а решения находятся на других ветках, на небольшом расстоянии от начала поиска. Для таких пространств более эффективен поиск в ширину. Если в глубине на каждом шаге имеется ровно один путь-кандидат в решение, то в ширине таких путей-кандидатов несколько. Рассмотрим поиск в ширину на модельном графе (рис. 2).
Начнем поиск в ширину из вершины 1 — имеем начальный путь [1]. Просмотрели вершины 2, 3, 4 смежные с вершиной 1 — получили пути-кандидаты [2, 1], [3, 1], [4, 1]. Каждый из них в свою очередь может дать несколько продолжений и т.д. Будем на каждом шаге хранить список путей-кандидатов. Новой будет считаться любая вершина, не содержащаяся в текущем пути, поэтому, добавив к главной цели fail можно сгенерировать все пути в порядке возрастания их длин. Первым аргументом процедуры width будет текущий список путей-кандидатов, вторым — окончательный путь-решение. Каждый новый путь становится головой списка путей кандидатов. width(Ways,Sol), где Ways — список путей, Sol — решение. Граничное условие рекурсии width([[Z|Was]|T],[Z|Was]):- end(Z). [Z|Was] — путь-решение, который окончился целевой вершиной Z. width([[X|Was]|T],Sol):- findall(Way,continue(X,Was,Way),LC), conc(T,LC,T1),!, width(T1,Sol). Findall собирает в список LC все продолжения пути [X|Was] на один шаг, и ширина вызывается с новым списком путей T1. Продолжение пути на один шаг производится в процедуре continue. continue(X,T,[Y,X|T]):- go(X,Y), not(member(Y,T)). Если вершина X тупиковая, то findall вернет список LC=[]. Путь [X|Was] будет удален из списка путей-кандидатов и произойдет вызов width с T1=T. Если все пути-кандидаты тупиковые и не содержат целевых вершин, то width будет вызвана с пустым списком и вернет неудачу. Так как отсечение блокирует возвраты, то неудачу вернет и самый первый вызов width из solve.
|