Читайте также:
|
Поиск с возвратами - это метод систематической проверки различных путей в пространстве состояний. Версия поиска с возвратами на примере поиска в глубину реализована на языках Prolog и Lisp. Алгоритм поиска с возвратами запускается из начального состояния и следует по некоторому пути до тех пор, пока не достигнет цели либо не упрется в тупик. Если цель достигнута, поиск завершается и в качестве решения задачи возвращается путь к цели. Если же поиск привел в тупиковую вершину, то алгоритм возвращается в ближайшую из пройденных вершин и исследует все ее вершины братья. А затем спускается по одной из ветвей, ведущих от вершины брата. Этот процесс описывается след-м рекурсивным правилом: если исходное состояние S не удовлетворяет требованиям цели, то из списка его потомков выбираем первый и к этой вершине рекурсивно применяем процедуру поиска с возвратами. Если в результате поиска с возвратами в подграфе Child1 цель не найдена, то повторяем процедуру для вершины брата Child2. эта процедура продолжается до тех пор, пока один из потомков, рассматриваемой вершины не окажется целевым узлом, либо не выяснится, что рассмотрены уже все вершины братья (возможные потомки). Если же ни одна из вершин братьев вершины S не привела к цели необходимо вернуться к предку вершины S и повторить процедуру с вершиной братом S и так далее. Этот алгоритм работает до тех пор, пока не достигнет цели либо не исследует все пространство состояний. Алгоритм поиска с возвратами осуществляет поиск в глубину.
Алгоритм поиска в глубину
При поиске в глубину необходимо оценить всех потомков и их потомки, а затем исследовать любую из вершин братьев. Если дальнейшие потомки состояний не найдены, то рассматриваются вершины братьев.
Дата добавления: 2015-07-10; просмотров: 96 | Нарушение авторских прав