Алгоритм поиска с возвращением

Оглавление

Алгоритм поиска с возвращением.. 1

Обходы ордерева в глубину и в ширину. 2

Обходы графа в глубину и в ширину. 3

Контрольные вопросы.. 4

 

Лекция №23

Алгоритм поиска с возвращением, их реализация с помощью рекурсий и динамических структур.

В качестве начального частичного решения берется пустой вектор ( ) и на основе имеющихся ограничений выясняется, какие элементы из А1являются… Общую схему алгоритма, осуществляющего поиск с возвращением для нахождения… k:=1; Вычислить S1(*например, в качестве S1взять А1 *); while k>0 do while не пусто Sk do (* Продвижение *) В…

Procedure ПОИСК (X: ВЕКТОР; i : Integer); begin if Х является решением then записать его end; if i <= r then Вычислить Si for all a from Si do ПОИСК (X || (a),i+1) end end end

Здесь || обозначает операцию конкатенации (соединения) двух векторов, т.е.
(а₁, а₂,… , а_n) || (b₁, b₂,… , b_m)= (а₁, а₂,… , а_n,,b₁, b₂,… , b_m) и () || (а₁) для любых а₁, а₂,… , а_n,,b₁, b₂,… , b_m.

Вызов ПОИСК((),1) находит все решения, причем все возвраты скрыты в механизме, регулирующем рекурсию.

Для иллюстрации того, как описанный метод применяется при решении конкретных задач, рассмотрим задачу нахождения таких расстановок восьми ферзей на шахматной доске, в которых ни один ферзь не атакует другого. Решение расстановки ферзей можно искать в виде вектора (а₁, а₂, а₃, а₄, а₅, а₆, а₇,

а₈), где а_i– номер вертикали, на которой стоит ферзь, находящийся в i-й горизонтали, т.е. А₁=А₂ =А₃=А₄ =А₅ =А₆ =А₇ =А₈ ={1,2,3,4,5,6,7,8} . Каждое частичное решение – это расстановка N ферзей (где 1£N£8) в первых N горизонталях таким образом, чтобы эти ферзи не атаковали друг друга. Заметим, что общая процедура поиска с возвращением при применении ее к задаче о расстановке ферзей уточняется таким образом, что в ней не вычисляются и не хранятся явно множества S_k .

Процесс поиска с возвращением удобно описывать в терминах обхода в глубину (см. ниже) дерева поиска решения, которое строится следующим образом. Корень дерева поиска решения (нулевой уровень) соответствует пустому вектору, являющемуся начальным частичным решением. Для любого k³1 вершины k-го уровня, являющиеся сыновьями некоторой вершины p, соответствуют частичным решениям
(а₁, а₂,… , а_k-1, а_k), где (а₁, а₂,… , а_k-1) – это то частичное решение, которое соответствует вершине p, а а_k Î S_k; при этом упорядоченность сыновей вершины p отражает упорядоченность соответствующих элементов а_k в S_k .

Обходы ордерева в глубину и в ширину

Рис. 20. Дерево  

Обходы графа в глубину и в ширину

Например, используя рекурсивную процедуру, линейный по временной сложности алгоритм обхода графа G в глубину можно записать следующим образом: procedure ОБХОД-В-ГЛУБИНУ(р: вершина); begin Посетить вершину р ; for all… В результате работы алгоритма, пройденные ребра графа образуют вместе с посещенными вершинами одно или несколько…

Контрольные вопросы

1. Дать описание алгоритму поиска с возвращением. В чем заключается суть алгоритма с возвращением?
2. Дать описание алгоритма обхода ордерева в глубину и ширину. В чем заключается суть алгоритма?
3. Дать описание алгоритма обхода графа в глубину и ширину. В чем заключается суть алгоритма?