Математика / Курсовая работа: Перебор с возвратом

Курсовая работа: Перебор с возвратом

Даны N упорядоченных множеств U₁ , U₂ , ..., U_N (N - известно), и требуется построить вектор A=(a₁ , a₂ , ..., a_N ), где a₁ ÎU₁ , a₂ ÎU₂ , ..., a_N ÎU_N , удовлетворяющий заданному множеству условий и ограничений.

В алгоритме перебора вектор А строится покомпонентно слева направо. Предположим, что уже найдены значения первых (k-1) компонент, А=(а₁ , а₂ , ..., а_(k-1) , ?, ..., ?), тогда заданное множество условий ограничивает выбор следующей компоненты а_k некоторым множеством S_k ÌU_k . Если S_k <>[ ] (пустое), мы вправе выбрать в качестве а_k наименьший элемент S_k и перейти к выбору (k+1) компоненты и так далее. Однако если условия таковы, что S_k оказалось пустым, то мы возвращаемся к выбору (k-1) компоненты, отбрасываем а_(k-1) и выбираем в качестве нового а_(k-1) тот элемент S_(k-1) , который непосредственно следует за только что отброшенным. Может оказаться, что для нового а_(k-1) условия задачи допускают непустое S_k , и тогда мы пытаемся снова выбрать элемент а_k . Если невозможно выбрать а_(k-1) , мы возвращаемся еще на шаг назад и выбираем новый элемент а_(k-2) и так далее.

Графическое изображение - дерево поиска. Корень дерева (0 уровень) есть пустой вектор. Его сыновья суть множество кандидатов для выбора а₁ , и, в общем случае, узлы k-го уровня являются кандидатами на выбор а_k при условии, что а₁ , а₂ , ..., а_(k-1) выбраны так, как указывают предки этих узлов. Вопрос о том, имеет ли задача решение, равносилен вопросу, являются ли какие-нибудь узлы дерева решениями. Разыскивая все решения, мы хотим получить все такие узлы.

Рекурсивная схема реализации алгоритма.

procedure Backtrack(вектор,i);

begin

if <вектор является решением> then <записать его>

else begin <вычислить Si>;

for aÎSi do Backtrack(векторêêa,i+1);

{êê- добавление к вектору компоненты}

end;

Оценка временной сложности алгоритма. Данная схема реализации перебора приводит к экспоненциальным алгоритмам. Действительно, пусть все решения имеют длину N, тогда исследовать требуется порядка çS₁ ç*çS₂ ç*...*çS_N ç узлов дерева. Если значение S_i ограничено некоторой константой С, то получаем порядка С^N узлов.

1. Задача о расстановке ферзей

На шахматной доске N*N требуется расставить N ферзей таким образом, чтобы ни один ферзь не атаковал другого.

Отметим следующее. Все возможные способы расстановки ферзей - С^N _N^2 (около 4,4*10⁹ для N=8). Каждый столбец содержит самое большее одного ферзя, что дает только N^N расстановок (1,7*10⁷ для N=8). Никакие два ферзя нельзя поставить в одну строку, а поэтому, для того чтобы вектор (а₁ , а₂ , ..., a_N ) был решением, он должен быть перестановкой элементов (1, 2, ..., N), что дает только N! (4,0*10⁴ для N=8) возможностей. Никакие два ферзя не могут находиться на одной диагонали, это сокращает число возможностей еще больше (для N=8 в дереве остается 2056 узлов). Итак, с помощью ряда наблюдений мы исключили из рассмотрения большое число возможных расстановок N ферзей на доске размером N*N. Использование подобного анализа для сокращения процесса перебора называется поиском с ограничениями или отсечением ветвей в связи с тем, что при этом удаляются поддеревья из дерева. Второе. Другим усовершенствованием является слияние, или склеивание, ветвей. Идея состоит в том, чтобы избежать выполнения дважды одной и той же работы: если два или больше поддеревьев данного дерева изоморфны, мы хотим исследовать только одно из них. В задаче о ферзях мы можем использовать склеивание, заметив, что если а₁ >éN/2ù, то найденное решение можно отразить и получить решение, для которого а₁ £éN/2ù. Следовательно, деревья, соответствующие, например, случаям а₁ =2 и а₁ =N-1, изоморфны.