Поиск в ширину

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

Алгоритм поиска в ширину

Поиск в ширину исследует пространство состояний по уровням. Если состояний на данном ходе больше нет, алгоритм переходит к следующему уровню.

ПЦР ОЦР

Дата добавления: 2015-07-10