nextupprevious

Next:4.5 Обходы ордерева в глубину и ширину
Up:4 Разработка алгоритмов
Previous:4.3 Поиск с возвращением

4.4 Алгоритм поиска с возвращением

Рассмотрим общий случай, когда решение задачи имеет вид вектора $(a_1,a_2,\ldots)$, длина которого не определена, но ограничена сверху некоторым (известным или неизвестным) числом $r$, а каждое $a_i$ является элементом некоторого конечного линейно упорядоченного множества $A_i$. Таким образом, при исчерпывающем поиске в качестве возможных решений мы рассматриваем элементы множества $A_1 \times A_2 \times \ldots \times A_i$ для любого $i$, где $i \leq r$, и среди них выбираем те, которые удовлетворяют ограничениям, определяющим решение задачи.

В качестве начального частичного решения берется пустой вектор () и на основе имеющихся ограничений выясняется, какие элементы из $A_1$ являются кандидатами для их рассмотрения в качестве $a_1$ (множество таких элементов $a_1$ из $A_1$ ниже обозначается через $S_1$). В качестве $a_1$ выбирается наименьший элемент множества $S_1$, что приводит к частичному решению $(a_1)$. В общем случае ограничения, описывающие решения, говорят о том, из какого подмножества $S_k$ множества $A_k$ выбираются кандидаты для расширения частичного решения от $(a_1,a_2,\ldots, a_{k-1})$ до $(a_1,a_2,\ldots, a_{k-1},a_k)$. Если частичное решение $(a_1,a_2,\ldots, a_{k-1})$ не предоставляет других возможностей для выбора нового $a_k$ (т.е. у частичного решения $(a_1,a_2,\ldots, a_{k-1})$ либо нет кандидатов для расширения, либо все кандидаты к данному моменту уже использованы), то происходит возврат и осуществляется выбор нового элемента $a_{k-1}$ из $S_{k-1}$. Если новый элемент $a_{k-1}$ выбрать нельзя, т.е. к данному моменту множество $S_{k-1}$ уже пусто, то происходит еще один возврат и делается попытка выбрать новый элемент $a_{k-2}$ и т.д.

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

$k := 1;$
Вычислить $S_1$ (*например, в качестве $S_1$ взять $A_1$*);
while$k > 0$do
    while не пусто $S_k$do
        (* Продвижение *)
        В качестве $a_k$ взять наименьший элемент из $S_k$, удалив его из $S_k;$
        if $(a_1, a_2, ..., a_k)$ является решением
        then Записать это решение
        end;
        if$k<r$then
            k := k + 1; Вычислить $S_k$
            (* Например, в качестве $S_k$ можно взять $A_k$*)
        end
    end;
    (* Возврат *) k := k - 1
end;
(* Все решения найдены *)
 

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

procedure ПОИСК ($X$: ВЕКТОР; $I$ : Integer);
begin
        if$X$ является решением then записать его end;
        if  I <= r then
                Вычислить $S_I;$
                for all a from$S_I$do ПОИСК ($X \parallel (a), I$ + 1) end
        end
end

Здесь $\Vert$ обозначает операцию конкатенации (соединения) двух векторов, т.е. $(a_1,\ldots,a_n) \Vert (b_1,\ldots,b_m)=(a_1,\ldots, a_n, b_1,\ldots, b_m)$ и $() \Vert (a_1)=(a_1)$ для любых $a_1,\ldots, a_n, b_1,\ldots, b_m$. Вызов ПОИСК((),1) находит все решения, причем все возвраты скрыты в механизме, регулирующем рекурсию.

Для иллюстрации того, как описанный метод применяется при решении конкретных задач, рассмотрим задачу нахождения таких расстановок восьми ферзей на шахматной доске, в которых ни один ферзь не атакует другого. Решение расстановки ферзей можно искать в виде вектора $(a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8)$, где $a_i$ -- номер вертикали, на которой стоит ферзь, находящийся в $i$-й горизонтали, т.е. $A_1=A_2=A_3=A_4=A_5=A_6=A_7=A_8=\{1,2,3,4,5,6,7,8\}$. Каждое частичное решение -- это расстановка $N$ ферзей (где $1 \leq N \leq 8$) в первых $N$ горизонталях таким образом, чтобы эти ферзи не атаковали друг друга. Заметим, что общая процедура поиска с возвращением при применении ее к задаче о расстановке ферзей уточняется таким образом, что в ней не вычисляются и не хранятся явно множества $S_k$.

Процесс поиска с возвращением удобно описывать в терминах обхода в глубину (см. ниже) дерева поиска решения, которое строится следующим образом. Корень дерева поиска решения (нулевой уровень) соответствует пустому вектору, являющемуся начальным частичным решением. Для любого $k \geq 1$ вершины $k$-го уровня, являющиеся сыновьями некоторой вершины $p$, соответствуют частичным решениям $(a_1,a_2,\ldots, a_{k-1},a_k)$, где $(a_1,a_2,\ldots, a_{k-1})$ -- это то частичное решение, которое соответствует вершине $p$, а $a_k\in S_k$; при этом упорядоченность сыновей вершины $p$ отражает упорядоченность соответствующих элементов $a_k$ в $S_k$.

Next:4.5 Обходы ордерева в глубину и ширину
Up:4 Разработка алгоритмов
Previous:4.3 Поиск с возвращением

 © В.Н. Касьянов,Е.В.Касьянова, 2004