Курсовая работа: Перебор с возвратом

begin min:=mn;Rbest:=Rwork end;

end

else begin

i:=k;

while i<=N do begin

блокотсеченийпо 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 (i<=t) and (A[i].part<>Q) do Inc(i);

if i<=t then begin Rbest:=Rbest+[i]; Rt:=[] end;

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	0	0	0	0	0	0	1	1	0	0	0	0	0	0	0	0	0	0
2	0	1	0	0	0	0	0	0	0	1	1	0	0	0	0	0	0	0	0
3	0	0	1	0	0	0	0	0	0	0	0	1	1	0	0	0	0	0	0
4	0	0	0	1	0	0	0	1	1	1	0	0	0	0	0	0	0	0	0
5	0	0	0	0	1	0	0	0	0	0	1	1	1	0	0	0	0	0	0
6	0	0	0	0	0	1	0	1	1	1	1	0	0	0	0	0	0	0	0
7	0	0	0	0	0	0	1	0	1	1	1	1	1	0	0	0	0	0	0
8	1	0	0	1	0	1	0	1	0	0	0	0	0	1	0	0	0	0	0
9	1	0	0	1	0	1	1	0	1	0	0	0	0	0	1	0	0	0	0
10	0	1	0	1	0	1	1	0	0	1	0	0	0	0	0	1	0	0	0
11	0	1	0	0	1	1	1	0	0	0	1	0	0	0	0	0	1	0	0
12	0	0	1	0	1	0	1	0	0	0	0	1	0	0	0	0	0	1	0
13	0	0	1	0	1	0	1	0	0	0	0	0	1	0	0	0	0	0	1
14	0	0	0	0	0	0	0	1	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	0	1	0	0	0	0
16	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	1	0	0	0
17	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	1	0	0
18	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	1	0
19	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	1

Выполняя операцию исключения жителей, «представительство» которых скромнее , чем у оставшихся, получаем.

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

<исключить менее активных жителей>;