Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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

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