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

Рассмотрим общий случай, когда решение задачи имеет вид вектора (а₁, а₂,…), длина которого не определена, но ограничена сверху некоторым (известным или неизвестным) числом 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;
(* Все решения найдены *)

 

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