Курсовая работа: Перебор с возвратом
🛑 👉🏻👉🏻👉🏻 ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻
Министерство образования Республики Беларусь
«Гомельский государственный университет им. Ф. Скорины»
Даны N упорядоченных множеств U 1
, U 2
, ..., U N
(N - известно), и требуется построить вектор A=(a 1
, a 2
, ..., a N
), где a 1
ÎU 1
, a 2
ÎU 2
, ..., a N
ÎU N
, удовлетворяющий заданному множеству условий и ограничений.
В алгоритме перебора вектор А строится покомпонентно слева направо. Предположим, что уже найдены значения первых (k-1) компонент, А=(а 1
, а 2
, ..., а (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 уровень) есть пустой вектор. Его сыновья суть множество кандидатов для выбора а 1
, и, в общем случае, узлы k-го уровня являются кандидатами на выбор а k
при условии, что а 1
, а 2
, ..., а (k-1)
выбраны так, как указывают предки этих узлов. Вопрос о том, имеет ли задача решение, равносилен вопросу, являются ли какие-нибудь узлы дерева решениями. Разыскивая все решения, мы хотим получить все такие узлы.
Рекурсивная схема реализации алгоритма.
if <вектор является решением> then <записать его>
for aÎSi do Backtrack(векторêêa,i+1);
{êê- добавление к вектору компоненты}
Оценка временной сложности алгоритма.
Данная схема реализации перебора приводит к экспоненциальным алгоритмам. Действительно, пусть все решения имеют длину N, тогда исследовать требуется порядка çS 1
ç*çS 2
ç*...*çS N
ç узлов дерева. Если значение S i
ограничено некоторой константой С, то получаем порядка С N
узлов.
На шахматной доске N*N требуется расставить N ферзей таким образом, чтобы ни один ферзь не атаковал другого.
Отметим следующее.
Все возможные способы расстановки ферзей - С N
N^2
(около 4,4*10 9
для N=8). Каждый столбец содержит самое большее одного ферзя, что дает только N N
расстановок (1,7*10 7
для N=8). Никакие два ферзя нельзя поставить в одну строку, а поэтому, для того чтобы вектор (а 1
, а 2
, ..., a N
) был решением, он должен быть перестановкой элементов (1, 2, ..., N), что дает только N! (4,0*10 4
для N=8) возможностей. Никакие два ферзя не могут находиться на одной диагонали, это сокращает число возможностей еще больше (для N=8 в дереве остается 2056 узлов). Итак, с помощью ряда наблюдений мы исключили из рассмотрения большое число возможных расстановок N ферзей на доске размером N*N. Использование подобного анализа для сокращения процесса перебора называется поиском с ограничениями или отсечением ветвей в связи с тем, что при этом удаляются поддеревья из дерева. Второе. Другим усовершенствованием является слияние, или склеивание, ветвей. Идея состоит в том, чтобы избежать выполнения дважды одной и той же работы: если два или больше поддеревьев данного дерева изоморфны, мы хотим исследовать только одно из них. В задаче о ферзях мы можем использовать склеивание, заметив, что если а 1
>éN/2ù, то найденное решение можно отразить и получить решение, для которого а 1
£éN/2ù. Следовательно, деревья, соответствующие, например, случаям а 1
=2 и а 1
=N-1, изоморфны.
Следующие рисунки иллюстрируют сказанное и поясняют ввод используемых структур данных.
Up:array[2..16] of boolean;{признак занятости диагоналей первого типа}
Down:array[-7..7] of boolean;{признак занятости диагоналей второго типа}
Vr:array[1..8] of boolean;{признак занятости вертикали}
X:array[1..8] of integer;{номер вертикали, на которой стоит ферзь на каждой горизонтали}
Далее идет объяснение “кирпичиков”, из которых “складывается” решение (технология “снизу вверх”).
procedure Hod(i,j:integer); {сделатьход}
X[i]:=j;Vr[j]:=false;Up[i+j]:=false;Down[i-j]:=false;
procedure O_hod(i,j:integer);{отменитьход}
Vr[j]:=true;Up[i+j]:=true;Down[i-j]:=true;
{проверка допустимости хода в позицию (i,j)}
D_hod:=Vr[j]andUp[i+j]andDown[i-j];
Основная процедура поиска одного варианта расстановки ферзей имеет вид:
procedure Solve(i:integer;var q:boolean);
Поиск всех решений. Длядоски 8*8 ответ 92.
for j:=1 to N do if D_hod(i,j) then begin
Inc(S);{счетчик числа решений, глобальная переменная}
Поиск только не симметричных решений. Для доски 8*8 ответ 12.
Эта модификация требует предварительных разъяснений. Из каждого решения задачи о ферзях можно получить ряд других при помощи вращений доски на 90 о
, 180 о
и 270 о
и зеркальных отражений относительно линий , разделяющих доску пополам (система координат фиксирована). Доказано, что в общем случае для доски N*N (N>1) для любой допустимой расстановки N ферзей возможны три ситуации:
· при одном отражении доски возникает новая расстановка ферзей, а при поворотах и других отражениях новых решений не получается;
· новое решение при повороте на 90 о
и ее отражения дают еще две расстановки;
· три поворота и четыре отражения дают новые расстановки.
Для отсечения симметричных решений на всем множестве решений требуется определить некоторое отношение порядка. Представим решение в виде вектора длиной N, координатами которого являются числа от 1 до N. Для ферзя, стоящего в i-й строке, координатой его столбца является i-я координата вектора. Для того, чтобы не учитывать симметричные решения, будем определять минимальный вектор среди всех векторов, получаемых в результате симметрий. Процедуры Sim1, Sim2, Sim3 выполняют зеркальные отображения вектора решения относительно горизонтальной, вертикальной и одной из диагональных осей. Известно (из геометрии), что композиция этих симметрий дает все определенные выше симметрии шахматной доски, причем не принципиально, в какой последовательности выполняются эти процедуры для каждой конкретной композиции. Проверка «на минимальность» решения производится функцией Cmp, которая возвращает значение true в том случае, когда одно из симметричных решений строго меньше текущего.
{не лучший вариант реализации - отсечение на выводе решений}
type Tarray=array[1..N] of integer;
r:=X[i]; X[i]:=X[N-i+1];X[N-i+1]:=r;
while (i<=N) and (Y[i]=X[i]) do Inc(i);
else if Y[i];
<вывод матрицы А - метками выделен путь выхода из лабиринта>;
procedure Solve(x,y,k:integer);{k - номер шага, x,y - координаты клетки}
if A[x+dx[i],y+dy[i]]=0 then Solve(x+dx[i],y+dy[i],k+1);
На острове Новой Демократии каждый из жителей организовал партию, которую сам и возглавил. Ко всеобщему удивлению, даже в самой малочисленной партии оказалось не менее двух человек. К сожалению, финансовые трудности не позволили создать парламент, куда вошли бы, как предполагалось по Конституции острова, президенты всех партий.
Посовещавшись, островитяне решили, что будет достаточно, если в парламенте будет хотя бы один член каждой партии.
Помогите островитянам организовать такой, как можно более малочисленный парламент, в котором будут представлены члены всех партий.
Исходные данные: каждая партия и ее президент имеют один и тот же порядковый номер от 1 до N (4£N£150). Вам даны списки всех N партий острова Новой Демократии. Выведите предлагаемый Вами парламент в виде списка номеров ее членов. Например, для четырех партий:
Список членов парламента 2 (состоит из одного члена).
Задача относится к классу NP-полных задач. Ее решение - полный перебор всех вариантов. Покажем, что ряд эвристик позволяет сократить перебор для некоторых наборов исходных данных.
Представим информацию о партиях и их членах с помощью следующего зрительного образа - таблицы. Для примера из формулировки задачи она имеет вид:
Тогда задачу можно переформулировать следующим образом. Найти минимальное число столбцов, таких, что множество единиц из них “покрывают” множество всех строк. Очевидно, что для примера это один столбец - второй. Поговорим о структурах данных.
number:Nint;{число партий, которые он представляет}
Логика формирования исходных данных (фрагмент реализации).
function Num(S:Sset):Nint;{подсчитывает количество элементов в множестве}
for i:=1 to N do if i in S then Inc(ch);
procedure Init;{предполагается, что данные корректны и во входном файле они организованы так, как представлены в примере из формулировки задачи}
for i:=1 to N do with A[i] do begin man:=i; part:=[i]; end;{каждыйжительпредставляетсвоюпартию}
while Not eoln do begin read(t);A[t].part:=A[t].part+[i];{житель t представляетпартиюсномером i, илипартиясномером i представленажителем t}
for i:=1 to N do A[i].number:=Num(A[i].part);
Следующим очевидным шагом является сортировка массива А по значению поля number. Становится понятным и необходимость ввода поля man в структуру записи - после сортировки номер элемента массива А не соответствует номеру жителя острова.
Пока не будем задумываться о том, как сократить перебор. Попытаемся набросать общую схему. Используемые переменные достаточно очевидны, они описываются в процессе их ввода, присвоение начальных значений глобальным переменным осуществляется в процедуре Init .
procedure Include(k:Nint);{включениеврешение}
procedure Exclude(k:Nint);{исключитьизрешения}
procedure Solve(k:Nint;Res,Rt:Sset);
{k- номер элемента массива А; Res - множество партий, которые представлены в текущем решении; Rt - множество партий, которые следует “покрыть” решением; min - минимальное количество членов в парламенте; mn - число членов парламента в текущем решении; Rbest - минимальный парламент; Rwork - текущий парламент; первый вызов - Solve(1,[],[1..N])}
Solve(i+1,Res+A[i].part,Rt-A[i].part);
Очевидно, что приведенная схема решения работает только для небольших значений N, особенно если есть ограничения (а они всегда есть) на время тестирования задачи. Предварительная обработка (до первого вызова процедуры Solve), заключающаяся в проверке, есть ли жители, которые представляют все партии (это первый шаг).
procedure One(t:Nint;Q:Sset);{проверяет - есть ли среди первых t элементов массива А такой, что A[i].part совпадает с Q}
while (i<=t) and (A[i].part<>Q) do Inc(i);
if i<=t then begin Rbest:=Rbest+[i]; Rt:=[] end;
Первый вызов этой процедуры - One(N,[1..N]), осуществляется в блоке предварительной обработки.
Идея
. Третий житель состоит в партиях 1 и 3, второй - в 1, 2 и 3. Есть “вхождение”, третий житель менее активный, исключим его. Однако из примера проглядывает и другая идея - появилась строка, в которой только одна единица. Мы получили “карликовую” партию, ее представляет один житель, заметим, что первоначально, по условию задачи, таких партий нет. Житель, представляющий “карликовую” партию должен быть включен в решение, но он же активный и представляет еще другие партии. Значит, эти партии представлять в парламенте нет необходимости - они представлены. Исключаем эти партии (строки таблицы), но после этого возможно появление других “карликовых” партий. Рассмотрим этот процесс на следующем примере: 1 - 8,9; 2 - 10,11; 3 - 12, 13; 4 - 8,9,10; 5 - 11,12,13; 6 - 8,9,10,11; 7 - 9,10,11,12,13;8 - 1,4,6; 9 - 1,4,6,7; 10 - 2,4,6,7; 11 - 2,5,6,7; 12 - 3,5,7; 13 - 3,5,7; 14 - 8; 15 - 9; 16 - 10; 17 - 11; 18 - 12; 19 - 13.
Выполняя операцию исключения жителей, «представительство» которых скромнее , чем у оставшихся, получаем.
Итак, партии с 14-й по 19-ю «карликовые», их представляют жители с 8-го по 13-й. Мы обязаны включить этих жителей в парламент. Включаем. Формируем множество партий, которые они представляют. Оказывается, что все. Решение найдено без всякого перебора.
Вывод - перебор следует выполнять не по всем жителям и не для всех партий! Если бы это выручало всегда. Сверхактивность жителей сводит на нет этот путь сокращения перебора. Остается надеяться, что кто-то должен и выращивать хлеб, а не только митинговать. Итак, “набросок” общей логики предварительной обработки.
<исключить менее активных жителей>;
<для “карликовых” партий включить жителей, представляющих их, в состав парламента>;
<изменить значения величин, описывающих процесс формирования парламента (Res, Rt, mn, Rwork)>;
Заметим, что необходимо исключить партии, “покрытые” жителями, представляющими карликовые партии из А[i].part оставшихся жителей. Это может привести к тому, что возможно появление жителей, представляющих все оставшиеся партии. Совместим проверку наличия вхождений, исключение части жителей и сжатие массива A в одной функции. Ее вид.
function Come(var t:Nint):boolean; {Проверяем - есть ли вхождения? Если есть, то исключаем соответствующих жителей и сжимаем массив А}
for j:=i+1 to t do if A[j].part<=A[i].part then begin
if (A[i].part=[]) and (i<=l) then begin for j:=i to l-1 do A[j]:=A[j+1];
Вариант построения процедуры исключения «карликовых» партий может быть и таким.
procedure Pygmy(t:Nint;var r,p:Sset);{t - количество обрабатываемых элементов массива А; r - множество номеров жителей, включаемых в парламент; p - множество номеров партий, представляемых жителями, включенных в парламент}
{определяем множество партий представляемых всеми жителями кроме A[i].man}
for j:=1 to t do if i<>j then v:=v+A[j].part;
{если есть хотя бы одна партия, которую представляет только житель с номером A[i].man, то этого жителя мы обязаны включить в парламент}
if A[i].part*v<>A[i].Part then r:=r+[A[i].man];
{формируем множество партий, имеющих представительство в данном составе парламента}
for i:=1 to t do if A[i].man in r then p:=p+A[i].part;
Итак, фрагмент предварительной обработки (до перебора).
while Come(t) and (Rt<>[]) do begin Rg:=[];Rp:=[];
if (j in Rp) and (j in A[i].part) then A[i]part:=A[i].part-[j];
Блок общих отсечений. Подсчитаем для каждого значения i (1£i£t) множество партий, представляемых жителями, номера которых записаны в элементах массива с i по t (массив С:array[1..N] of Sset). Тогда, если Res - текущее решение, а Rt - множество партий, требующих представления, то при Res+C[i]£Rt решение не может быть получено и эту ветку перебора следует “отсечь”.
C[t]:=A[t].part; for i:=t-1 downto 1 do begin
Блок отсечений по i. Если при включении элемента с номером i в решение, значение величины Rt не изменяется, то это включение бессмысленно (A[i].part*Rt=[]).
На этом мы закончим обсуждение этой, очень интересной с методической точки зрения, задачи. Заметим, что для любой вновь возникающей идеи по сокращению перебора место для ее реализации в логике определено. А именно, предобработка, общие отсечения, покомпонентные отсечения - другого не дано.
Примечание. Графовая модель задачи (двудольный граф). Каждому жителю соответствует вершина в множестве X, каждой партии - вершина в множестве Y. Ребро (i,j) существует, если житель с номером i представляет партию с номером j. Требуется найти минимальное по мощности множество вершин S, такое, что SÍX и для любой вершины jÎY существует вершина iÎS, из которой выходит ребро в вершину j. Модификация задачи о нахождении минимального доминирующего множества.
Постановка задачи
. В рюкзак загружаются предметы n различных типов (количество предметов каждого типа не ограничено). Максимальный вес рюкзака W. Каждый предмет типа i имеет вес w i
и стоимость v i
(i=1,2, ..., n). Требуется определить максимальную стоимость груза, вес которого не превышает W. Обозначим количество предметов типа i через k i
, тогда требуется максимизировать v 1
*k 1
+v 2
*k 2
+...+v n
*k n
при ограничениях w 1
*k 1
+w 2
*k 2
+...+w n
*k n
£W, где k i
- целые (0£k i
£[W/w i
]), квадратные скобки означают целую часть числа.
Рассмотрим простой переборный вариант решения задачи, работоспособный только для небольших значений n (определить, для каких?). Итак, данные:
Varn,w:integer;{количество предметов, максимальный вес}
Weight,Price:array[1..MaxN] of integer;{вес, стоимостьпредметов}
Best,Now:array[1..MaxN] of integer;{наилучшее, текущеерешения}
MaxPrice:LongInt;{наибольшая стоимость}
Решение, его основная часть - процедура перебора:
Procedure Rec(k,w:integer;st:LongInt);
{k - порядковый номер группы предметов, w - вес, который следует набрать из оставшихся предметов, st - стоимость текущего решения}
if (k>n) and (st>MaxPrice) then begin {найденорешение}
for i:=0 to w div Weight[k] do begin
Rec(k+1,W-i*Weight[k],st+i*Price[k]);
Инициализация переменных, вывод решения и вызывающая часть (Rec(1,w,0)) очевидны. В данной логике отсутствуют блоки предварительной обработки, общих отсечений и отсечений по номеру предмета (смотрите задачу о парламенте). В блоке предварительной обработки целесообразно найти какое-то решение, лучше, если оно будет как можно ближе к оптимальному (наилучший вариант загрузки рюкзака). «Жадная» логика дает первое приближение. Кроме того, разумно выполнить сортировку, например, по значению стоимости предметов или отношению веса предмета к его стоимости. Построение блока общих отсечений аналогично тому, как это сделано в задаче о парламенте, а ответ на вопрос, почему предметы данного типа не стоит складывать в рюкзак, остается открытым.
Инициализация переменных, вывод решения и вызывающая часть (Rec(1,w,0)) очевидны. В данной логике отсутствуют блоки предварительной обработки, общих отсечений и отсечений по номеру предмета (смотрите задачу о парламенте). В блоке предварительной обработки целесообразно найти какое-то решение, лучше, если оно будет как можно ближе к оптимальному (наилучший вариант загрузки рюкзака). «Жадная» логика дает первое приближение. Кроме того, разумно выполнить сортировку, например, по значению стоимости предметов или отношению веса предмета к его стоимости. Построение блока общих отсечений аналогично тому, как это сделано в задаче о парламенте, а ответ на вопрос, почему предметы данного типа не стоит складывать в рюкзак, остается открытым.
1. Ахо А.,Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов.-М.:Мир,1979.
2. Гэри М., Джонсон Д. Вычислительные алгоритмы и труднорешаемые задачи.-М.:Мир, 1982.
3. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы: Теория и практика.-М.:Мир,1980.
4. Суханов А.А. Олимпиадные задачи. Неопубликованный материал. - СПб.: 1996.
Название: Перебор с возвратом
Раздел: Рефераты по математике
Тип: курсовая работа
Добавлен 13:08:50 08 марта 2010 Похожие работы
Просмотров: 258
Комментариев: 16
Оценило: 3 человек
Средний балл: 5
Оценка: неизвестно Скачать
Срочная помощь учащимся в написании различных работ. Бесплатные корректировки! Круглосуточная поддержка! Узнай стоимость твоей работы на сайте 64362.ru
Привет студентам) если возникают трудности с любой работой (от реферата и контрольных до диплома), можете обратиться на FAST-REFERAT.RU , я там обычно заказываю, все качественно и в срок) в любом случае попробуйте, за спрос денег не берут)
Да, но только в случае крайней необходимости.
Курсовая работа: Перебор с возвратом
Реферат На Тему Предмет Політології, Сутність Та Зміст
Реферат Октановое Число И Методы Его Определения
Курсовая работа по теме Процесс пленкообразования модифицированных олигобутадиенов из органических и водных систем
Сочинение На Тему Звуки Русской Речи
Реферат: Солнечный транспорт. Скачать бесплатно и без регистрации
Курсовая работа по теме Анализ бюджетной политики Российской Федерации
Обучение Грамоте Контрольная Работа 1 Класс
Дипломная работа по теме Анализ проблем, связанных с реализацией права нации на самоопределение в международном праве
Сочинение О Правдине В Комедии Недоросль
Реферат По Физкультуре Мостик
Реферат На Тему Возрастные Особенности Развития Дошкольника
Реклама Практическая Работа
Starlight 5 Контрольные Работы С Ответами
Курс Лекций На Тему Теория Статистики
Реферат: Переработка отходов и вторичное сырье
Курсовая Работа Анализ Финансового Состояния Предприятия Диплом
Реферат: Cirrhosis Of The Liver Essay Research Paper
Сочинение по теме Экстремальный опыт
Нетрадиционные И Возобновляемые Источники Энергии Реферат
Реферат: Принципы организации дискуссионных клубов Дебаты в средней школе (на примере гимназии № 63 Санкт-Петербурга)
Реферат: Зубы
Реферат: Депортации с оккупированных территорий
Реферат: Коронавирусная инфекция