Министерство образования Республики Беларусь

Учреждение образования

«Гомельский государственный университет им. Ф. Скорины»

Математический факультет

Кафедра МПУ

Курсовая работа

Перебор с возвратом

Исполнитель:

Студентка группы М-32

Ловренчук А.Ю.

Научный руководитель:

Канд. физ-мат. наук, доцент

Звягина Т.Е.

Гомель 2007

Введение

 

Даны N упорядоченных множеств U1, U2, ..., UN (N - известно), и требуется построить вектор A=(a1, a2, ..., aN), где a1ÎU1, a2ÎU2, ..., aNÎUN, удовлетворяющий заданному множеству условий и ограничений.

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

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

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

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

begin

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

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

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

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

end;

end;

Оценка временной сложности алгоритма. Данная схема реализации перебора приводит к экспоненциальным алгоритмам. Действительно, пусть все решения имеют длину N, тогда исследовать требуется порядка çS1ç*çS2ç*...*çSNç узлов дерева. Если значение Si ограничено некоторой константой С, то получаем порядка СN узлов.

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

 

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

Отметим следующее. Все возможные способы расстановки ферзей - СNN^2 (около 4,4*109 для N=8). Каждый столбец содержит самое большее одного ферзя, что дает только NN расстановок (1,7*107 для N=8). Никакие два ферзя нельзя поставить в одну строку, а поэтому, для того чтобы вектор (а1, а2, ..., aN) был решением, он должен быть перестановкой элементов (1, 2, ..., N), что дает только N! (4,0*104 для N=8) возможностей. Никакие два ферзя не могут находиться на одной диагонали, это сокращает число возможностей еще больше (для N=8 в дереве остается 2056 узлов). Итак, с помощью ряда наблюдений мы исключили из рассмотрения большое число возможных расстановок N ферзей на доске размером N*N. ............