Министерство образования Республики Беларусь
Учреждение образования
«Гомельский государственный университет им. Ф.Скорины»
Математический факультет
Кафедра МПУ
Курсовая работа
Перебор с возвратом
Исполнитель:
Студентка группы М-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 ;
for aÎSido 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. Использование подобного анализа длясокращения процесса перебора называется поиском с ограничениями или отсечениемветвей в связи с тем, что при этом удаляются поддеревья из дерева. Второе.Другим усовершенствованием является слияние, или склеивание, ветвей. Идеясостоит в том, чтобы избежать выполнения дважды одной и той же работы: если дваили больше поддеревьев данного дерева изоморфны, мы хотим исследовать толькоодно из них. В задаче о ферзях мы можем использовать склеивание, заметив, чтоесли а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); {сделать ход}
begin
X[i]:=j;Vr[j]:=false;Up[i+j]:=false;Down[i-j]:=false;
end;
procedure O_hod(i,j:integer);{отменить ход}
begin
Vr[j]:=true;Up[i+j]:=true;Down[i-j]:=true;
end;
function D_hod(i,j:integer);
{проверка допустимости хода в позицию (i,j)}
begin
D_hod:=Vr[j]andUp[i+j]andDown[i-j];
end;
Основная процедура поиска одного варианта расстановкиферзей имеет вид:
procedure Solve(i:integer;var q:boolean);
var j:integer;
begin
j:=0;
repeat
inc(j);q:=false;{цикл по вертикали}
if D_hod(i,j) then begin Hod(i,j);
if i
if not q then O_hod(i,j);
end else q:=true;{решение найдено}
end;
until q or (j=8);
end;
Возможные модификации.
Поиск всех решений. Для доски 8*8 ответ 92.
Procedure Solve(i:integer);
var j:integer;
begin
if i
for j:=1 to N do if D_hod(i,j) then begin
Hod(i,j);
Solve(i+1);
O_hod(i,j);
end;
end
else begin
Inc(S);{счетчикчисла решений, глобальная переменная}
Print;{вывод решения}
end;
end;
Поиск только не симметричных решений. Для доски 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;
procedure Sim1(var X:Tarray);
var i:integer;
begin
for i:=1 to N do X[i]:=N-X[i]+1;
end;
procedure Sim2(var X:Tarray);
var i,r:integer;
begin
for i:=1 to N do begin
r:=X[i]; X[i]:=X[N-i+1];X[N-i+1]:=r;
end;
end;
procedure Sim3(var X:Tarray);
var Y:Tarray;
i:integer;
begin
for i:=1 to N do Y[X[i]]:=i;
X:=Y;
end;
function Cmp(X,Y:Tarray):boolean;
var i:integer;
begin
i:=1;
while (i
if i>N then Cmp:=false
else if Y[i]
end;
Procedure Solve(i:integer);
var j:integer;f:boolean;
Y:Tarray;
begin
if i
for j:=1 to N do if D_hod(i,j) then begin
Hod(i,j);
Solve(i+1);
O_hod(i,j);
end;
end
else begin
f:=true;
for j:=0 to 7 do begin
Y:=X;
if j and 1 =0 then Sim1(Y);
if j and 2 =0 then Sim2(Y);
if j and 4 =0 then Sim3(Y);
if Cmp(Y,X) then f:=false;
end;
if f then begin
Inc(S);{счетчикчисла решений, глобальная переменная}
Print;{вывод решения}
end;
end;
end;2. Задача о шахматном коне
Существуют способы обойти шахматным конем доску,побывав на каждом поле по одному разу. Составить программу подсчета числаспособов обхода.
Разбор задачи начинается с оценки числа 64! — таковообщее число способов разметки доски 8*8. Каждую разметку следует оценивать напредмет того, является ли она способом обхода конем доски(решение в “лоб”).Затем оцениваем порядок сокращения перебора исходя из условия — логика выбораочередного хода коня. Будем считать, что поля для хода выбираются по часовойстрелке. Объяснение иллюстрируется следующими рисунками.
/>
/>
Структуры данных.
Const N=; M= ;
Dx:array[1..8] ofinteger=(-2,-1,1,2,2,1,-1-2);
Dy:array[1..8] ofinteger=(1,2,2,1,-1,-2,-2,-1);
Var A:array[-1..N+2,-1..M+2] of integer;
Основной фрагмент реализации — процедура Solve.
procedure Solve(x,y,l:integer);
var z,i,j:integer;
begin
A[x,y]:=l;
if l=N*M then Inc(t)
else for z:=1 to 8 do begini:=x+Dx[z];j:=y+Dy[z];
if A[i,j]=0 then Rec(i,j,l+1)
end;
A[x,y]:=0;
end;
for i:=-1 to N+2 do for j:=-1 to M doA[i,j]:=-1;
for i:=1 to N do for j:=1 to M doA[i,j]:=0;
t:=0;
for i:=1 to N do for j:=1 to M doSolve(i,j,1);
writeln(‘число способов обхода конемдоски’,N,’*’,M,’--’,t);
Изменим логику так, чтобы находился только одинвариант обхода конем доски. При этом маршрут коня находится с использованиемправила Варнсдорфа выбора очередного хода (предложено более 150 лет тому назад).Его суть — при обходе шахматной доски коня следует ставить на поле, из которогоон может сделать минимальное количество перемещений на еще не занятые поля,если таких полей несколько, можно выбирать любое из них. В этом случае в первуюочередь занимаются угловые поля и количество “возвратов” значительноуменьшается.
Вариант процедуры Solve для этогослучая.
procedure Solve(x,y,l:integer);
varW:array[1..8] of integer;
xn,yn,i,j,m:integer;
begin
A[x,y]:=l;
if (l
for i:=1 to 8 do begin{формирование массива W}
W[i]:=0;xn:=x+dx[i];yn:=y+dy[i];
if (A[xn,yn]=0) the begin
for j:=1 to 8 do
if (A[xn+dx[j],yn+dy[j]]=0) the Inc(W[i]);
end else W[i]:=-1;
end;
i:=1;
while(i
m:=1;{ищем клетку, из которой можно сделать наименьшеечисло перемещений}
for j:=2 to 8 do if W[j]
if (W[m]>=0) and (W[m]
then Solve(x+dx[m],y+dy[m],l+1);
W[m]:=maxint;{отмечаемиспользованную в переборе клетку}
Inc(i);
end;
end
else begin ;
halt;
end;
A[x,y]:=0;
end;3. Задача о лабиринте
Классическая задача для изучения темы. Как ипредыдущие, не обходится без внимания в любой книге по информатике.Формулировка проста. Дано клеточное поле, часть клеток занята препятствиями.Необходимо попасть из некоторой заданной клетки в другую заданную клетку путемпоследовательного перемещения по клеткам. Изложение задачи опирается на рисунокпроизвольного лабиринта и две «прорисовки» с использованием простого перебора иметода «волны». Классический перебор выполняется по правилам, предложенным в1891 г. Э.Люка в “Математических досугах”:
· в каждой клетке выбирается еще неисследованный путь;
· если из исследуемой в данныймомент клетки нет путей, то возвращаемся на один шаг назад (в предыдущуюклетку) и пытаемся выбрать другой путь.
Естественными модификациями задачи поиска всех путейвыхода из лабиринта являются:
· поиск одного пути;
· поиск одного пути кратчайшей длиныметодом «волны».
Решение первой задачи.
program Labirint;
const Nmax=...;
dx:array[1..4] of integer=(1,0,-1,0);
dy:array[1..4] of integer=(0,1,0,-1);
type MyArray=array[0..Nmax+1,0..Nmax+1] ofinteger;
var A:MyArray;
xn,yn,xk,yk,N:integer;
procedure Init;
begin
;
end;
procedure Print;
....
begin
;
end;
procedure Solve(x,y,k:integer);{k — номер шага, x,y — координаты клетки}
var i:integer;
begin
A[x,y]:=k;
if (x=xk) and (y=yk) then Print
else for i:=1 to 4 do
if A[x+dx[i],y+dy[i]]=0 thenSolve(x+dx[i],y+dy[i],k+1);
A[x,y]:=0;
end;
begin
Init;
Solve(xn,yn,1);
end.
4. Задача о парламенте
На острове Новой Демократии каждый из жителейорганизовал партию, которую сам и возглавил. Ко всеобщему удивлению, даже всамой малочисленной партии оказалось не менее двух человек. К сожалению,финансовые трудности не позволили создать парламент, куда вошли бы, какпредполагалось по Конституции острова, президенты всех партий.
Посовещавшись, островитяне решили, что будетдостаточно, если в парламенте будет хотя бы один член каждой партии.
Помогите островитянам организовать такой, как можноболее малочисленный парламент, в котором будут представлены члены всех партий.
Исходные данные: каждая партия и ее президент имеютодин и тот же порядковый номер от 1 до N (4£N£150). Вам даны списки всех N партий острова НовойДемократии. Выведите предлагаемый Вами парламент в виде списка номеров еечленов. Например, для четырех партий:Президенты Члены партий 1 2,3,4 2 3 3 1,4,2 4 2
Список членов парламента 2 (состоит из одного члена).
Задача относится к классу NP-полных задач. Ее решение- полный перебор всех вариантов. Покажем, что ряд эвристик позволяет сократитьперебор для некоторых наборов исходных данных.
Представим информацию о партиях и их членах с помощьюследующего зрительного образа — таблицы. Для примера из формулировки задачи онаимеет вид:
/>
Тогда задачу можно переформулировать следующимобразом. Найти минимальное число столбцов, таких, что множество единиц из них“покрывают” множество всех строк. Очевидно, что для примера это один столбец — второй. Поговорим о структурах данных.
Const Nmax=150;
Type Nint=0..Nmax+1;
Sset=Set of 0..Nmax;
Person=record
man:Nint;{номер жителя}
number:Nint;{число партий, которые онпредставляет}
part:Sset;{партии}
end;
Var A:array[Nint] of Person;
Логика формирования исходных данных (фрагментреализации).
function Num(S:Sset):Nint;{подсчитывает количествоэлементов в множестве}
vari,ch:Nint;
begin ch:=0;
for i:=1 to N do if i in S then Inc(ch);
Num:=ch;
end;
procedure Init;{предполагается, что данные корректны иво входном файле они организованы так, как представлены в примере изформулировки задачи}
begin
readln(N);{число жителей}
for i:=1 to N do with A[i] do begin man:=i;part:=[i]; end;{каждый житель представляет свою партию}
for i:=1 to N do begin
while Not eoln do beginread(t);A[t].part:=A[t].part+[i];{житель t представляет партию с номером i, или партия с номером i представлена жителем t}
end;
readln;
end;
for i:=1 to N doA[i].number:=Num(A[i].part);
end;
Следующим очевидным шагом является сортировка массиваА по значению поля number. Становится понятным и необходимость ввода поля man вструктуру записи — после сортировки номер элемента массива А не соответствуетномеру жителя острова.
Пока не будем задумываться о том, как сократитьперебор. Попытаемся набросать общую схему. Используемые переменные достаточноочевидны, они описываются в процессе их ввода, присвоение начальных значенийглобальным переменным осуществляется в процедуре Init .
procedure Include(k:Nint);{включение в решение}
begin
Rwork:=Rwork+[A[k].man];
Inc(mn);
end;
procedure Exclude(k:Nint);{исключить из решения}
begin
Rwork:=Rwork-[A[k].man];
Dec(mn);
end;
procedure Solve(k:Nint;Res,Rt:Sset);
{k- номер элемента массива А; Res — множество партий,которые представлены в текущем решении; Rt — множество партий, которые следует“покрыть” решением; min — минимальное количество членов в парламенте; mn — число членов парламента в текущем решении; Rbest — минимальный парламент; Rwork- текущий парламент; первый вызов — Solve(1,[],[1..N])}
vari:Nint;
begin
блок общих отсечений
if Rt=[] then begin if nm
begin min:=mn;Rbest:=Rwork end;
end
else begin
i:=k;
while i
блок отсечений по i
Include(i);
Solve(i+1,Res+A[i].part,Rt-A[i].part);
Exclude(i);
Inc(i);
end;
end;
end;
Очевидно, что приведенная схема решения работаеттолько для небольших значений N, особенно если есть ограничения (а они всегдаесть) на время тестирования задачи. Предварительная обработка (до первоговызова процедуры Solve), заключающаяся в проверке, есть ли жители, которыепредставляют все партии (это первый шаг).
procedure One(t:Nint;Q:Sset);{проверяет — есть лисреди первых t элементов массива А такой, что A[i].part совпадает с Q}
var i:Nint;
begin
i:=1;
while (iQ) doInc(i);
if i
end;
Первый вызов этой процедуры — One(N,[1..N]),осуществляется в блоке предварительной обработки.
Рассмотрим пример.Президенты Члены партии 1 2,3 2 4 3 2 4 1
/>
Идея. Третийжитель состоит в партиях 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. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 1 1 1 1 2 1 1 1 3 1 1 1 4 1 1 1 1 5 1 1 1 1 6 1 1 1 1 1 7 1 1 1 1 1 1 8 1 1 1 1 1 9 1 1 1 1 1 1 10 1 1 1 1 1 1 11 1 1 1 1 1 1 12 1 1 1 1 1 13 1 1 1 1 1 14 1 1 15 1 1 16 1 1 17 1 1 18 1 1 19 1 1
Выполняя операцию исключения жителей,«представительство» которых скромнее, чем у оставшихся, получаем. 1 2 3 4 5 6 7 8 9 10 11 12 13 1 1 1 1 2 1 1 1 3 1 1 1 4 1 1 1 1 5 1 1 1 1 6 1 1 1 1 1 7 1 1 1 1 1 1 8 1 1 1 1 9 1 1 1 1 1 10 1 1 1 1 1 11 1 1 1 1 1 12 1 1 1 1 13 1 1 1 1 14 1 15 1 16 1 17 1 18 1 19 1
Итак, партии с 14-й по 19-ю «карликовые», ихпредставляют жители с 8-го по 13-й. Мы обязаны включить этих жителей впарламент. Включаем. Формируем множество партий, которые они представляют.Оказывается, что все. Решение найдено без всякого перебора.
Вывод — перебор следует выполнять не по всем жителям ине для всех партий! Если бы это выручало всегда. Сверхактивность жителей сводитна нет этот путь сокращения перебора. Остается надеяться, что кто-то должен ивыращивать хлеб, а не только митинговать. Итак, “набросок” общей логикипредварительной обработки.
while do begin
;
;
;
;
;
end;
Заметим, что необходимо исключить партии, “покрытые”жителями, представляющими карликовые партии из А[i].part оставшихся жителей.Это может привести к тому, что возможно появление жителей, представляющих всеоставшиеся партии. Совместим проверку наличия вхождений, исключение частижителей и сжатие массива A в одной функции. Ее вид.
function Come(var t:Nint):boolean; {Проверяем — естьли вхождения? Если есть, то исключаем соответствующих жителей и сжимаем массивА}
var i,j,l:Nint;
begin
for i:=1 to t-1 do
for j:=i+1 to t do ifA[j].part
A[j].part:=[];A[j].number:=0;
end;
l:=t;
for i:=1 to t do begin
if (A[i].part=[]) and (i
A[l].number:=0;A[l].part:=[];
Dec(l);
end;
end;
Come:=Not(t=l);
t:=l;
end;
Вариант построения процедуры исключения «карликовых»партий может быть и таким.
procedure Pygmy(t:Nint;var r,p:Sset);{t — количествообрабатываемых элементов массива А; r — множество номеров жителей, включаемых впарламент; p — множество номеров партий, представляемых жителями, включенных впарламент}
var i,j:Nint;v:Sset;
begin
r:=[];p:=[];
for i:=1 to t do begin
{определяем множество партий представляемых всемижителями кроме A[i].man}
v:=[];
for j:=1 to t do if ij thenv:=v+A[j].part;
{если есть хотя бы одна партия, которую представляеттолько житель с номером A[i].man, то этого жителя мы обязаны включить в парламент}
if A[i].part*vA[i].Part thenr:=r+[A[i].man];
end;
{формируем множество партий, имеющих представительствов данном составе парламента}
for i:=1 to t do if A[i].man in r thenp:=p+A[i].part;
end;
Итак, фрагмент предварительной обработки (доперебора).
t:=N;Rt:=[1..N];Rwork:=[];
One(t,Rt);
while Come(t) and (Rt[]) do beginRg:=[];Rp:=[];
Pygmy(t,Rg,Rp);
Rt:=Rt-Rp;Rwork:=Rwork+Rg;
if Rp[] then begin
for i:=1 to t do begin{исключение}
for j:=1 to N do
if (j in Rp) and (j in A[i].part) thenA[i]part:=A[i].part-[j];
A[i].number:=Num(A[i].part);
end;
;
end;
end;
if (Rt[]) then One(t,Rt);
Блок общих отсечений. Подсчитаем для каждого значения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 dobegin
C[i]:=[];C[i]:=A[i].part+C[i+1];
end;
Блок отсечений по i. Если при включении элемента сномером i в решение, значение величины Rt не изменяется, то это включениебессмысленно (A[i].part*Rt=[]).
На этом мы закончим обсуждение этой, очень интереснойс методической точки зрения, задачи. Заметим, что для любой вновь возникающейидеи по сокращению перебора место для ее реализации в логике определено. Аименно, предобработка, общие отсечения, покомпонентные отсечения — другого недано.
Примечание. Графовая модель задачи (двудольный граф).Каждому жителю соответствует вершина в множестве X, каждой партии- вершина в множестве Y. Ребро (i,j) существует,если житель с номером i представляет партию с номером j.Требуется найти минимальное по мощности множество вершин S,такое, что SÍX идля любой вершины jÎYсуществует вершина iÎS, изкоторой выходит ребро в вершину j. Модификация задачи о нахожденииминимального доминирующего множества.5. Задача о рюкзаке (переборвариантов)
Постановка задачи. В рюкзак загружаются предметы n различных типов (количествопредметов каждого типа не ограничено). Максимальный вес рюкзака W.Каждый предмет типа i имеет вес wi и стоимость vi (i=1,2, ..., n). Требуется определитьмаксимальную стоимость груза, вес которого не превышает W.Обозначим количество предметов типа i через ki,тогда требуется максимизировать v1*k1+v2*k2+...+vn*kn при ограничениях w1*k1+w2*k2+...+wn*kn£W,где ki — целые (0£ki£[W/wi]), квадратные скобки означают целую часть числа.
Рассмотрим простой переборный вариант решения задачи,работоспособный только для небольших значений n (определить,для каких?). Итак, данные:
Сonst MaxN=????;
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 — стоимостьтекущего решения}
var i:integer;
begin
if (k>n) and (st>MaxPrice) then begin{найдено решение}
Best:=Now;MaxPrice:=st; end
else if k
for i:=0 to w div Weight[k] do begin
Now[k]:=i;
Rec(k+1,W-i*Weight[k],st+i*Price[k]);
end;
end;
Инициализация переменных, вывод решения и вызывающаячасть (Rec(1,w,0)) очевидны. В данной логике отсутствуют блокипредварительной обработки, общих отсечений и отсечений по номеру предмета(смотрите задачу о парламенте). В блоке предварительной обработки целесообразнонайти какое-то решение, лучше, если оно будет как можно ближе к оптимальному(наилучший вариант загрузки рюкзака). «Жадная» логика дает первое приближение.Кроме того, разумно выполнить сортировку, например, по значению стоимостипредметов или отношению веса предмета к его стоимости. Построение блока общихотсечений аналогично тому, как это сделано в задаче о парламенте, а ответ навопрос, почему предметы данного типа не стоит складывать в рюкзак, остаетсяоткрытым.
Заключение
Инициализация переменных, вывод решения и вызывающаячасть (Rec(1,w,0)) очевидны. В данной логике отсутствуют блокипредварительной обработки, общих отсечений и отсечений по номеру предмета(смотрите задачу о парламенте). В блоке предварительной обработки целесообразнонайти какое-то решение, лучше, если оно будет как можно ближе к оптимальному(наилучший вариант загрузки рюкзака). «Жадная» логика дает первое приближение.Кроме того, разумно выполнить сортировку, например, по значению стоимостипредметов или отношению веса предмета к его стоимости. Построение блока общихотсечений аналогично тому, как это сделано в задаче о парламенте, а ответ навопрос, почему предметы данного типа не стоит складывать в рюкзак, остается открытым.
Литература
1. Ахо А., Хопкрофт Д., Ульман Д. Построение и анализвычислительных алгоритмов.-М.: Мир,1979.
2. Гэри М., Джонсон Д. Вычислительные алгоритмы итруднорешаемые задачи.-М.: Мир, 1982.
3. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторныеалгоритмы: Теория и практика.-М.: Мир,1980.
4.Суханов А.А. Олимпиадные задачи. Неопубликованный материал. — СПб.: 1996.