Смекни!
smekni.com

Перебор с возвратом (стр. 3 из 3)

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 (определить, для каких?). Итак, данные:

СonstMaxN=????;

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.