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

Лекция №23

Рассмотрим общий случай, когда решение задачи имеет вид вектора (а₁, а₂,…), длина которого не определена, но ограничена сверху некоторым (известным или неизвестным) числом r, а каждое а_i является элементом некоторого конечного линейно упорядоченного множества А_i. Таким образом, при исчерпывающем поиске в качестве возможных решений мы рассматриваем элементы множества А₁ ´ А₂ ´… ´ А_i для любого i, где i£r, и среди них выбираем те, которые удовлетворяют ограничениям, определяющим решение задачи.

В качестве начального частичного решения берется пустой вектор () и на основе имеющихся ограничений выясняется, какие элементы из А₁ являются кандидатами для их рассмотрения в качестве а₁ (множество таких элементов а₁ из А₁ ниже обозначается через а₁). В качестве а₁ выбирается наименьший элемент множества S₁, что приводит к частичному решению (а₁). В общем случае ограничения, описывающие решения, говорят о том, из какого подмножества S_k множества А_k выбираются кандидаты для расширения частичного решения от (а₁, а₂,…, а_k-1) до (а₁, а₂,…, а_k-1, а_k). Если частичное решение (а₁, а₂,…, а_k-1) не предоставляет других возможностей для выбора нового а_k (т.е. у частичного решения (а₁, а₂,…, а_k-1)
либо нет кандидатов для расширения, либо все кандидаты к данному моменту уже использованы), то происходит возврат и осуществляется выбор нового элемента а_k-1 из S_k-1. Если новый элемент а _k-1 выбрать нельзя, т.е. к данному моменту множество S_k-1 уже пусто, то происходит еще один возврат и делается попытка выбрать новый элемент а_k-2 и т.д.

Общую схему алгоритма, осуществляющего поиск с возвращением для нахождения всех решений, можно представить в следующем виде:

k:=1;
Вычислить S₁ (*например, в качестве S₁ взять А₁ *);
while k>0 do
while не пусто S_k do (* Продвижение *)
В качестве а_k взять наименьший элемент из S_k, удалив его из S_k
if (а₁, а₂,…, а _k ) является решением then Записать это решение
end;
if k<r thenk:= k + 1; Вычислить S_k
(* Например, в качестве S_k можно взять А_k *)
end
end;
(* Возврат *) k:= k - 1
end;
(* Все решения найдены *)

Более коротко общую процедуру поиска с возвращением можно записать в рекурсивной форме:

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.

Дата добавления: 2014-01-04