Министерство образования Республики Беларусь

Учреждение образования

«Гомельский государственный университет им. Ф. Скорины»

Математический факультет

Кафедра МПУ

Курсовая работа

Метод «решета»

Исполнитель:

Студентка группы М-32

Логвинович А.Ю.

Гомель 2007

Содержание

• Введение
• 1. Решето Эратосфена
• 2. Быки и коровы
• (модификация задачи А.А. Суханова)
• 3. Задача о коммивояжере (перебор вариантов)
• 4. Задача о секторах
• Заключение
• Литература
• Введение
• Идея метода. Решето представляет собой метод комбинаторного программирования, который рассматривает конечное множество и исключает все элементы этого множества, не представляющие интереса. Он является логическим дополнением к процессу поиска с возвратом (backtrack), который перечисляет все элементы множества решений, представляющие интерес.

1. Решето Эратосфена

Эратосфен - греческий математик, 275-194 гг. до нашей эры. Классическая задача поиска простых чисел в интервале [2..N] - инструмент для обсуждения метода. Объяснение строится на основе следующего рисунка и фрагмента логики.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

Числа, выделенные «жирным» шрифтом, отбрасываются.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

Числа, выделенные курсивом, отбрасываются.

Const N= ...;{верхняя граница интервала чисел}

Type Number=Set of 2..N;{решето, N<256}

Var S:Number;

procedure Poisk(var S:Number);

var i,j:2..N;

begin

S:=[2..N];

for i:=2 to N div 2 do

if i in S then begin

j:=i+i;

while j<=N do begin S:=S-[j];j:=j+i;end;

end;

end;

Логическим развитием задачи является ее решение при N больших 256. В этом случае необходимо ввести массив с множественным типом данных элементов.

2. Быки и коровы (модификация задачи А.А. Суханова)

Компьютер и ребенок играют в следующую игру. Ребенок загадывает последовательность из четырех (не обязательно различных) цветов, выбранных из шести заданных. Для удобства будем обозначать цвета цифрами от 1 до 6. Компьютер должен отгадать последовательность, используя информацию, которую он получает из ответов ребенка.

Компьютер отображает на экране последовательность, а ребенок должен ответить (используя для ввода ответа клавиатуру) на два вопроса:

сколько правильных цветов на неправильных местах;

сколько правильных цветов на правильных местах.

Компьютер Ответ ребенка

1234 1 0

5156 2 1

6165 2 1

5625 1 2

5653 1 2

4655 0 4

Пример. Предположим, что ребенок загадал последовательность 4655. Один из возможных способов отгадать последовательность такой:

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

Const Pmax=6*6*6*6;

Type Post=String[4];

Var A:array[1..Pmax] of Post;

B:array[1..Pmax] of boolean;

cnt:integer;{счетчик числа ходов}

ok:boolean;{найдено решение}

procedure Init;

var i,j,k,l:integer;

begin

for i:=1 to 6 do

for j:=1 to 6 do

for k:=1 to 6 do

for l:=1 to 6 do A[(i-1)*216+(j-1)*36+(k-1)*6+l]:= Chr(i+Ord(`0'))+Chr(j+Ord(`0'))+Chr(k+Ord(`0'))+Chr(k+Ord(`0'));

for i:=1 to Pmax do B[i]:=true;

cnt:=0;ok:=false;

end;

Поясним на примере идею решета. Пусть длина последовательности равна двум, а количество цветов - четырем. Ребенок загадал 32, а компьютер спросил 24. Ответ ребенка 1 0, фиксируем его в переменных kr (1) и bk(0).

A	B	B (после анализа bk)	B (после анализа kr)	Результат
11	true		false	false
12	true			true
13	true		false	false
14	true	false		false
21	true	false		false
22	true	false		false
23	true	false		false
24	true	false		false
31	true		false	false
32	true			true
33	true		false	false
34	true	false		false
41	true			true
42	true		false	false
43	true			true
44	true	false		false

Итак, было 16 возможных вопросов, после первого осталось четыре - работа решета. Функция, реализующая анализ элемента массива А, по значениям переменных kr и bk, имеет вид:

function Pr(a,b:Post;kr,bk:integer):boolean;

var i,x:integer;

begin

{проверка по “быкам”}

x:=0;

for i:=1 to 4 do if a[i]=b[i] then inc(x);

if x<>bk then begin Pr:=false;exit;end;

{проверка по “коровам”}

x:=0;

for i:=1 to 4 do if (a[i]<>b[i]) and (Pos(b[i],a)<>0) then inc(x);

if x<>kr then begin Pr:=false;exit;end;

Pr:=true;

end;

Логика - “сделать отсечение” по значению хода h.

procedure Hod(h:Post);

var i,kr,bk:integer;

begin

inc(cnt);write(cnt:2,'.',h,'-');

readln(kr,bk);

if bk=4 then begin ok:=true;<вывод результата>;end

else for i:=1 to Pmax do if B[i] and Not Pr(A[i],h,kr,bk) then B[i]:=false;

end;

Общая логика.

.....

begin

clrscr;

init;

hod(`1223');

while not ok do begin

выбор очередного хода из А

hod(h);

end;

end.

Дальнейшая работа с задачей требует ответа на следующие вопросы:

Зависит ли значение cnt от выбора первого хода? Установить экспериментальным путем.

Как логика выбора очередного хода влияет на результат игры? Исследовать. Например, выбрать тот элемент А (соответствующий элемент В должен быть равен true), в котором количество несовпадающих цифр максимально.

3. Задача о коммивояжере (перебор вариантов)

Постановка задачи. Классическая формулировка задачи известна уже более 200 лет: имеются n городов, расстояния между которыми заданы ; коммивояжеру необходимо выйти из какого-то города, посетить остальные n-1 городов точно по одному разу и вернуться в исходный город. При этом маршрут коммивояжера должен быть минимальной длины (стоимости).

Задача коммивояжера принадлежит классу NP-полных, то есть неизвестны полиномиальные алгоритмы ее решения. В задаче с n городами необходимо рассмотреть (n-1)! маршрутов, чтобы выбрать маршрут минимальной длины. Итак, при больших значениях n невозможно за разумное время получить результат.

Перебор вариантов. Оказывается, что и при простом переборе не обязательно просматривать все варианты. Это реализуется в данном классическом методе.

Структуры данных.

Const Max=100;

Var A:array[1..Max,1..Max] of integer;{Матрица расстояний между городами}

B:array[1..Max,1..Max] of byte;{Вспомогательный массив, элементы каждой строки матрицы сортируются в порядке возрастания, но сами элементы не переставляются, а изменяются в матрице В номера столбцов матрицы А }

Way, BestWay:array[1..Max] of byte;{Хранится текущее решение и лучшее решение}

Nnew:array[1..Max] of boolean;{Значение элемента массива false говорит о том, что в соответствующем городе коммивояжер уже побывал}

BestCost:integer;{Стоимость лучшего решения}

Идея решения. Пусть мы находимся в городе с номером v. Наши действия.

Шаг 1. Если расстояние (стоимость), пройденное коммивояжером до города с номером v, не меньше стоимости найденного ранее наилучшего решения (BestCost), то следует выйти из данной ветви дерева перебора.

Шаг 2. Если рассматривается последний город маршрута (осталось только вернуться в первый город), то следует сравнить стоимость найденного нового решения со стоимостью лучшего из ранее найденных. Если результат сравнения положительный, то значения BestCost и BestWay следует изменить и выйти из этой ветви дерева перебора .

Шаг 3. Пометить город с номером v как рассмотренный, записать этот номер по значению Count в массив Way .

Шаг 4. Рассмотреть пути коммивояжера из города v в ранее не рассмотренные города. Если такие города есть, то перейти на эту же логику с измененными значениями v, Count, Cost, иначе на следующий шаг.

Шаг 5. Пометить город v как нерассмотренный и выйти из данной ветви дерева перебора.

Пример. Ниже приведены матрицы А и В (после сортировки элементов каждой строки матрицы А).

A B

@	27	43	16	30	26
7	@	16	1	30	25
20	13	@	35	5	0
21	16	25	@	18	18
12	46	27	48	@	5
23	5	5	9	5	@
4	6	2	5	3	1
4	1	3	6	5	2
6	5	2	1	4	3
2	5	6	1	3	4
6	1	3	2	4	5
2	3	5	4	1	6

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



Итак, запись логики.

procedure Solve(v,Count:byte;Cost:integer);

{v - номер текущего города; Count - счетчик числа пройденных городов; Cost - стоимость текущего решения}

var i:integer;

begin

if Cost>BestCost then exit;{Стоимость текущего решения превышает стоимость лучшего из ранее полученных }

if Count=N then begin Cost:=Cost+A[v,1];Way[N]:=v;{Последний город пути. Доформировываем решение и сравниваем его с лучшим из ранее полученных.}

if Cost<BestCost then begin

BestCost:=Cost;BestWay:=Way;

end;

exit;

end;

Nnew[v]:=false;Way[Count]:=v;{Город с номером v пройден, записываем его номер в путь коммивояжера}

for i:=1 to N do if Nnew[B[v,i]] then

Solve(B[v,i], Count+1,Cost+A[v,B[v,i]]); {Поиск города, в который коммивояжер может пойти из города с номером v}

Nnew[v]:=true; {Возвращаем город с номером v в число непройденных}

end;

Первый вызов - Solve(1,1,0).

Разработка по данному «шаблону» работоспособной программы - техническая работа. Если Вы решитесь на это, то есть смысл проверить ее работоспособность на следующем примере (матрица А приведена ниже). Решение имеет вид 1 8 9 2 5 10 6 7 4 3 1, его стоимость 158.

@	32	19	33	22	41	18	15	16	31
32	@	51	58	27	42	35	18	17	34
9	51	@	23	35	49	26	34	35	41
33	58	23	@	33	37	23	46	46	32
22	27	35	33	@	19	10	23	23	9
41	42	49	37	19	@	24	42	42	10
18	35	26	23	10	24	@	25	25	14
15	18	34	46	23	42	25	@	1	32
16	17	35	46	23	42	25	1	@	32
31	34	41	32	9	10	14	32	32	@

Оцените время работы программы. Если у Вас мощный компьютер, то создайте матрицу А[1..50,1..50] и попытайтесь найти наилучшее решение с помощью разобранного метода. Заметим, что набор 2500 чисел - утомительное занятие и разумная лень - «двигатель прогресса».

4. Задача о секторах

Задан круг, разделенный на секторы. Даны три числа: k (0<=k<=20), n (n<=6) и m (m<=20), где n - количество секторов. В каждый из секторов помещается одно число >= k. Когда секторы заполнены числами, Вы можете получать из них новые числа по одному из следующих правил:

взять число из одного сектора;

взять число, равное сумме двух или более чисел в смежных секторах.

Из этих чисел составляется наибольшая последовательность подряд идущих новых чисел, начинающихся с числа m :(m, m+1, m+2, ..., i).

Напишите программу, которая определяет способ расстановки чисел в секторах, максимизирующий длину последовательности.

Пример. На рисунке показано, как получаются все новые числа от 2 до 21 из чисел, записанных в секторах. Серым цветом выделены суммируемые числа.

Входные и выходные данные

Исходные данные расположены во входном файле с именем INPUT.TXT, который содержит числа n, m и k. Ниже приведен пример файла исходных данных INPUT.TXT.

Выходной файл с именем OUTPUT.TXT должен содержать:

наибольшее число i в неразрывной последовательности, которое может быть получено из чисел в секторах;

все наборы чисел в секторах, из которых можно получить неразрывную последовательность от m до i. В каждой строке выводится один набор чисел в секторах. Каждый такой набор - список чисел, начинающихся с наименьшего (которое может быть не единственным).

Например, (2 10 3 1 5) не является решением, так как начинается не с наименьшего числа. Обратите внимание, что (1 3 10 2 5) и (1 5 2 10 3) считаются различными решениями и должны быть оба выведены. Ниже приведен файл OUTPUT.TXT для нашего примера.

21

1 3 10 2 5

1 5 2 10 3

2 4 9 3 5

2 5 3 9 4

Если наименьшее число встретится несколько раз, вывести все возможные комбинации, например: (1 1 2 3), (1 2 3 1), (1 3 2 1) и (1 1 3 2).

Рассуждения по поводу задачи. Очевидно, что в первый сектор может помещаться число из интервала от k до m. Считаем, что минимальное из чисел находится в первом секторе. Если k больше m, то задача не имеет решения. Обозначим через Up верхнюю границу, а через Down - нижнюю границу интервала, из которого могут браться числа для записи в сектора с номерами от 2 до n. Общая схема («набросок»).

for l:=k to m do begin

<выбор числа в первый сектор>;

for j:=2 to n do begin (* j - номер сектора *)

<определение значений верхней и нижней границ для чисел, записываемых в сектор с номером j>;

for i:=Down to Up do (* i - записываемое число *)

begin

< записать в сектор с номером j число i >

< откорректировать массив сумм, которые можно составить из чисел, записанных в сектора>

< выполнить проверку последовательности сумм >

end;

end;

end;

Эта привлекательная схема перебора мало пригодна для «жизни», ибо время перебора будет весьма не привлекательным. Попробуем на этапе уточнения повысить пригодность схемы. "Откорректировать массив сумм". Пусть в Q (array[1..n,0..n] of byte) будут храниться суммы чисел из секторов круга S (array[1..n] of byte). В нулевом столбце элементы равны 0. В 1-м столбце - суммы, составленные из чисел, взятых из одного сектора, 2-м - из двух и т.д. В n-м столбце подсчитывается только элемент в первой строке.

Массив Q:

		1	2	3	4	5	6
1	0	S[1]	Q[1,1]+S[2]	Q[1,2]+S[3]	Q[1,3]+S[4]	Q[1,4]+S[5]	Q[1,5]+S[6]
2	0	S[2]	Q[2,1]+S[3]	Q[2,2]+S[4]	Q[2,3]+S[5]	Q[2,4]+S[6]
3	0	S[3]	Q[3,1]+S[4]	Q[3,2]+S[5]	Q[3,3]+S[6]	Q[3,4]+S[1]
4	0	S[4]	Q[4,1]+S[5]	Q[4,2]+S[6]	Q[4,3]+S[1]	Q[4,4]+S[2]
5	0	S[5]	Q[5,1]+S[6]	Q[5,2]+S[1]	Q[5,3]+S[2]	Q[5,4]+S[3]
6	0	S[6]	Q[6,1]+S[1]	Q[6,2]+S[2]	Q[6,3]+S[3]	Q[6,4]+S[4]

Итак, если у нас есть массив констант (для простоты) Sq вида

1 2 3 4 5 6

2 3 4 5 6 0

3 4 5 6 1 0

5 6 1 2 3 0

6 1 2 3 4 0,

то элемент массива Q[i,j] вычисляется следующим образом:

Q[i,j]:=Q[i,j-1] + Q[Sq[i,j],1]

При изменении числа в секторе с номером t необходимо откорректировать часть матрицы Q, показанную на рисунке темным цветом (эта часть больше, чем требуется, но для простоты считаем ее такой).

Схема процедуры уточнения сумм:

procedure AddSum(t,number :byte);

(* Q, Sq - глобальные переменные *)

var z,i,j :integer;

begin

Q[t,1]:=number;

for i:=1 to n do begin

if t-i+1>1 then z:=t-i+1 else z:=2;

for j:=z to n-1 do begin

Q[i,j]:=0;

Q[i,j]:=Q[i,j-1]+Q[Sq[i,j],1];

end;

end;

Q[1,n]:=Q[1,5] + Q[n,1];

end;

Следующее уточнение. "Выполнить проверку последовательности сумм". Из чего следует исходить? Во-первых, наилучшая последовательность сумм может получиться не из одного варианта заполнения секторов числами. Поэтому необходимо ввести структуру данных - двумерный массив - для их хранения и, соответственно, указатель числа записанных вариантов:

,

где type SView = array[1..nMax] of byte;

NumS :byte;

Во-вторых, для хранения наибольшего числа необходима переменная MaxS. В-третьих, значения сумм лучше представить множественным типом данных SetS :set of byte. Это упростит логику поиска последовательности. Процедура проверки имеет вид:

procedure Check;

(* SetS, BestS, NumS, MaxS, M - глобальные *)

var i,j :integer;

begin

SetS:=[];

for i:=1 to N do

for j:=1 to N-1 do SetS:=Sets+[Q[i,j]];

SetS:=SetS+[Q[1,N]];

i:=M;

while i in SetS do Inc(i);

if i>MaxS then begin

NumS:=1;

BestS[NumS]:=S;

MaxS:=i;(* на единицу больше действительной длины *)

end

else if i=MaxS then begin Inc(NumS); BestS[NumS]:=S; end;

end;

Общая схема уточнена. Но если довести ее до программы, то решение, например, для исходных данных n=6, m=1, k=1 за реальное время не будет получено. Необходимо сокращать перебор, искать эвристики, позволяющие сделать это.

1-я эвристика. Пусть у нас есть (n-1) сектор, в которые записаны числа, образующие последовательность m, m+1, ... . количество сумм (арифметическая прогрессия) равно n*(n-1)div2, т. е. это количество различных чисел, получаемое из чисел в заполненных n-1 секторе. Обозначим через X первое число из последовательности m, m+1, ..., которое мы не можем получить. В пустой сектор не имеет смысла записывать число, большее X. Поскольку X не превосходит n(n-1) div 2 + m, то это выражение можно считать значением верхней границы Up чисел, записываемых в сектора. В качестве нижней границы Down следует брать S[1], ибо числа, записываемые в сектора 2, 3, ..., n не меньше этого числа.

2-я эвристика. Пусть m<2*k. Тогда числа m, m+1, ..., 2*k-1 как сумма чисел из нескольких (более одного) секторов. Следовательно, либо, если 2*k-mn, все они должны находиться в круге, либо, если 2*k-m>n, в круге должны находиться числа m, m+1, ..., m+n-1.

3-я эвристика. "Исключение симметричных решений". При поиске числа для записи в последний сектор значение Down можно уточнить:

if < сектор последний > then Down:=S[2]

else Down:=S[1];

4-я эвристика. "Отсечение снизу". При поиске числа для последнего сектора нам известна максимальная сумма, которую дают числа, записанные в (N-1) сектор. Это значение Q[1,N-1]. Если сумма Up и Q[i,N-1] меньше ранее полученного наибольшего числа MaxS, то эту "ветку" в переборе вариантов можно "отсечь"(при любом варианте заполнения последнего сектора лучшего решения мы не получим).

Описанных эвристик (чем не эвристическое программирование?) оказывается достаточно для написания работоспособной программы для нижеприведенных тестов. В таблице приведены и правильные результаты.

N 3	M 1	K 1	max 7	1 2 4; 1 4 2
4	2	2	13	2 3 4 6; 2 6 4 3
5	3	1	22	3 5 7 4 6; 3 6 4 7 5
4	16	1	23	1 16 2 20; 1 20 2 16; 1 16 4 18; 1 18 4 16; 2 16 4 17; 2 17 4 16
5	16	12	20	16 17 18 19 20; 16 20 19 18 17; 16 17 18 20 19; 16 19 20 18 17; 16 17 19 18 20; 16 20 18 19 17; 16 17 19 18 20; 16 20 18 19 17; 16 17 19 20 18; 16 18 20 19 17; 16 17 20 18 19; 16 19 18 20 17
6	1	1	31	1 2 5 4 6 13; 1 13 6 4 5 2; 1 2 7 4 12 5; 1 5 12 4 7 2; 1 3 2 7 8 10; 1 10 8 7 2 3; 1 3 6 2 5 14; 1 14 5 2 6 3; 1 7 3 2 4 14; 1 14 4 2 3 7
6	2	2	29	2 3 7 4 9 6; 2 6 9 4 7 3
6	4	4	31	4 4 6 5 7 9; 4 9 7 5 6 4; 4 4 9 7 5 6; 4 6 5 7 9 4; 4 5 5 6 7 8; 4 8 7 6 5 5

Заключение

Инициализация переменных, вывод решения и вызывающая часть (Rec(1,w,0)) очевидны. В данной логике отсутствуют блоки предварительной обработки, общих отсечений и отсечений по номеру предмета (смотрите задачу о парламенте). В блоке предварительной обработки целесообразно найти какое-то решение, лучше, если оно будет как можно ближе к оптимальному (наилучший вариант загрузки рюкзака). «Жадная» логика дает первое приближение. Кроме того, разумно выполнить сортировку, например, по значению стоимости предметов или отношению веса предмета к его стоимости. Построение блока общих отсечений аналогично тому, как это сделано в задаче о парламенте, а ответ на вопрос, почему предметы данного типа не стоит складывать в рюкзак, остается открытым.

Литература

Ахо А.,Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов.-М.:Мир,1979.

Гэри М., Джонсон Д. Вычислительные алгоритмы и труднорешаемые задачи.-М.:Мир, 1982.

Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы: Теория и практика.- М.:Мир,1980.

4. Суханов А.А. Олимпиадные задачи. Неопубликованный материал. - СПб.: 1996.