Оглавление
Алгоритм поиска с возвращением.. 1
Обходы ордерева в глубину и в ширину. 2
Обходы графа в глубину и в ширину. 3
Контрольные вопросы.. 4
Лекция №23
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
Здесь || обозначает операцию конкатенации (соединения) двух векторов, т.е.
(а1, а2,… , аn) || (b1, b2,… , bm)= (а1, а2,… , аn,,b1, b2,… , bm) и () || (а1) для любых а1, а2,… , аn,,b1, b2,… , bm.
Вызов ПОИСК((),1) находит все решения, причем все возвраты скрыты в механизме, регулирующем рекурсию.
Для иллюстрации того, как описанный метод применяется при решении конкретных задач, рассмотрим задачу нахождения таких расстановок восьми ферзей на шахматной доске, в которых ни один ферзь не атакует другого. Решение расстановки ферзей можно искать в виде вектора (а1, а2, а3, а4, а5, а6, а7,
а8), где аi– номер вертикали, на которой стоит ферзь, находящийся в i-й горизонтали, т.е. А1=А2 =А3=А4 =А5 =А6 =А7 =А8 ={1,2,3,4,5,6,7,8} . Каждое частичное решение – это расстановка N ферзей (где 1£N£8) в первых N горизонталях таким образом, чтобы эти ферзи не атаковали друг друга. Заметим, что общая процедура поиска с возвращением при применении ее к задаче о расстановке ферзей уточняется таким образом, что в ней не вычисляются и не хранятся явно множества Sk .
Процесс поиска с возвращением удобно описывать в терминах обхода в глубину (см. ниже) дерева поиска решения, которое строится следующим образом. Корень дерева поиска решения (нулевой уровень) соответствует пустому вектору, являющемуся начальным частичным решением. Для любого k³1 вершины k-го уровня, являющиеся сыновьями некоторой вершины p, соответствуют частичным решениям
(а1, а2,… , аk-1, аk), где (а1, а2,… , аk-1) – это то частичное решение, которое соответствует вершине p, а аk Î Sk; при этом упорядоченность сыновей вершины p отражает упорядоченность соответствующих элементов аk в Sk .
Контрольные вопросы