Next:4.5
Обходы ордерева в глубину и ширину
Up:4
Разработка алгоритмов
Previous:4.3
Поиск с возвращением
В качестве начального частичного решения берется пустой вектор () и
на основе имеющихся ограничений выясняется, какие элементы из
являются кандидатами для их рассмотрения в качестве
(множество таких элементов
из
ниже обозначается через
).
В качестве
выбирается наименьший элемент множества
,
что приводит к частичному решению
.
В общем случае ограничения, описывающие решения, говорят о том, из какого
подмножества
множества
выбираются кандидаты для расширения частичного решения от
до
.
Если частичное решение
не предоставляет других возможностей для выбора нового
(т.е. у частичного решения
либо нет кандидатов для расширения, либо все кандидаты к данному моменту
уже использованы), то происходит возврат и осуществляется выбор нового
элемента
из
.
Если новый элемент
выбрать нельзя, т.е. к данному моменту множество
уже пусто, то происходит еще один возврат и делается попытка выбрать новый
элемент
и т.д.
Общую схему алгоритма, осуществляющего поиск с возвращением для нахождения всех решений, можно представить в следующем виде:
Вычислить
(*например, в качестве
взять
*);
whiledo
while не пусто do
(* Продвижение *)
В качестве
взять наименьший элемент из
,
удалив его из
if
является решением
then Записать это
решение
end;
ifthen
k := k + 1; Вычислить
(* Например, в качестве
можно взять
*)
end
end;
(* Возврат *) k := k - 1
end;
(* Все решения найдены *)
Более коротко общую процедуру поиска с возвращением можно записать в рекурсивной форме:
procedure ПОИСК (:
ВЕКТОР;
: Integer);
begin
if
является решением then записать его end;
if I <=
r then
Вычислить
for all a fromdo
ПОИСК (
+ 1) end
end
end
Здесь
обозначает операцию конкатенации (соединения) двух векторов, т.е.
и
для любых
.
Вызов ПОИСК((),1) находит все решения, причем все возвраты скрыты в механизме,
регулирующем рекурсию.
Для иллюстрации того, как описанный метод применяется при решении конкретных
задач, рассмотрим задачу нахождения таких расстановок восьми ферзей на
шахматной доске, в которых ни один ферзь не атакует другого. Решение расстановки
ферзей можно искать в виде вектора ,
где
-- номер вертикали, на которой стоит ферзь, находящийся в
-й
горизонтали, т.е.
.
Каждое частичное решение -- это расстановка
ферзей (где
)
в первых
горизонталях таким образом, чтобы эти ферзи не атаковали друг друга. Заметим,
что общая процедура поиска с возвращением при применении ее к задаче о
расстановке ферзей уточняется таким образом, что в ней не вычисляются и
не хранятся явно множества
.
Процесс поиска с возвращением удобно описывать в терминах обхода в глубину
(см. ниже) дерева поиска решения, которое строится следующим образом. Корень
дерева поиска решения (нулевой уровень) соответствует пустому вектору,
являющемуся начальным частичным решением. Для любого
вершины
-го
уровня, являющиеся сыновьями некоторой вершины
,
соответствуют частичным решениям
,
где
-- это то частичное решение, которое соответствует вершине
,
а
;
при этом упорядоченность сыновей вершины
отражает упорядоченность соответствующих элементов
в
.
Next:4.5
Обходы ордерева в глубину и ширину
Up:4
Разработка алгоритмов
Previous:4.3
Поиск с возвращением