Курсовая работа: Перебор с возвратом
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 3 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 4 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 |
| 5 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 6 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
| 7 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 8 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 9 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 10 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 11 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 12 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| 13 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 |
| 14 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 15 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 16 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 17 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 18 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 19 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
Итак, партии с 14-й по 19-ю «карликовые», их представляют жители с 8-го по 13-й. Мы обязаны включить этих жителей в парламент. Включаем. Формируем множество партий, которые они представляют. Оказывается, что все. Решение найдено без всякого перебора.
Вывод - перебор следует выполнять не по всем жителям и не для всех партий! Если бы это выручало всегда. Сверхактивность жителей сводит на нет этот путь сокращения перебора. Остается надеяться, что кто-то должен и выращивать хлеб, а не только митинговать. Итак, “набросок” общей логики предварительной обработки.
while <есть вхождения> do begin
<исключить менее активных жителей>;
<сжать А>;
<для “карликовых” партий включить жителей, представляющих их, в состав парламента>;
<изменить значения величин, описывающих процесс формирования парламента (Res, Rt, mn, Rwork)>;
<откорректировать A>;
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 if A[j].part<=A[i].part then begin
A[j].part:=[];A[j].number:=0;
end;
l:=t;
for i:=1 to t do begin
if (A[i].part=[]) and (i<=l) then begin for j:=i to l-1 do A[j]:=A[j+1];
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 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];
end;
{формируем множество партий, имеющих представительство в данном составе парламента}
for i:=1 to t do if A[i].man in r then p:=p+A[i].part;
end;
Итак, фрагмент предварительной обработки (до перебора).
t:=N;Rt:=[1..N];Rwork:=[];
One(t,Rt);
while Come(t) and (Rt<>[]) do begin Rg:=[];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) then A[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 do begin
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<=n then
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.
