Быстрый поиск

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

Тогда задачу можно переформулировать следующим образом. Найти минимальное число столбцов, таких, что множество единиц из них покрывают” множество всех строк. Очевидно, что для примера это один столбец - второй. Поговорим о структурах данных.

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;{подсчитывает количество элементов в множестве}

var i,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 begin read(t);A[t].part:=A[t].part+[i];{житель t представляет партию с номером i, или партия с номером i представлена жителем t}

end;

readln;

end;

for i:=1 to N do A[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])}

var i:Nint;

begin

блок общих отсечений

if Rt=[] then begin if nm<min then

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;

Очевидно, что приведенная схема решения работает только для небольших значений 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