Міністерство освіти Республіки Білорусь
Установа освіти
«Гомельський державний університет ім. Ф. Скорини »
Математичний факультет
Кафедра МПУ
Курсова робота
Перебір з поверненням
Виконавець:
Студентка групи М-32
Ловренчук А.Ю.
Науковий керівник:
Канд. фіз-мат. наук, доцент
Звягіна Т.Є.
Гомель 2007
Введення
Дано N впорядкованих множин U 1, U 2, ..., U N (N - відомо), і потрібно побудувати вектор A = (a 1, a 2, ..., a N), де a 1 ÎU 1, a 2 ÎU 2, ..., a N ÎU N, що задовольняє заданій множині умов і обмежень.
В алгоритмі перебору вектор А будується покомпонентно зліва направо. Припустимо, що вже знайдено значення перших (k-1) компонент, А = (а 1, а 2, ..., а (k-1),?, ...,?), Тоді заданий безліч умов обмежує вибір наступного компоненти а k деяким безліччю S k ÌU k. Якщо S k <> [] (порожній), ми маємо право вибрати в якості а k найменший елемент S k і перейти до вибору (k +1) компоненти і так далі. Однак якщо умови такі, що S k виявилося порожнім, то ми повертаємося до вибору (k-1) компоненти, відкидаємо а (k-1) і вибираємо як нового а (k-1) той елемент S (k-1), який безпосередньо випливає за щойно відкинутим. Може виявитися, що для нового а (k-1) умови завдання допускають непорожнє S k, і тоді ми намагаємося знову вибрати елемент а k. Якщо неможливо вибрати а (k-1), ми повертаємося ще на крок назад і вибираємо новий елемент а (k-2) і так далі.
Графічне зображення - дерево пошуку. Корінь дерева (0 рівень) є порожній вектор. Його сини суть безліч кандидатів для вибору а 1, і, в загальному випадку, вузли k-го рівня є кандидатами на вибір а k за умови, що а 1, а 2, ..., а (k-1) вибрані так, як вказують предки цих вузлів. Питання про те, чи має завдання рішення, рівносильний питання, чи є які-небудь вузли дерева рішеннями. Розшукуючи всі рішення, ми хочемо отримати всі такі вузли.
Рекурсивна схема реалізації алгоритму.
procedure Backtrack (вектор, i);
begin
if <вектор є рішенням> then <записати його>
else begin <обчислити Si>;
for aÎSi do Backtrack (векторêêa, i +1);
{Êê-додавання до вектора компоненти}
end;
end;
Оцінка часової складності алгоритму. Дана схема реалізації перебору призводить до експоненціальним алгоритмам. Дійсно, нехай всі рішення мають довжину N, тоді дослідити потрібно близько çS 1 ç * çS 2 ç *...* çS N ç вузлів дерева. Якщо значення S i обмежено деякою константою С, то отримуємо порядку З N вузлів.
Відзначимо наступне. Всі можливі способи розміщення ферзів - З N N ^ 2 (близько 4,4 * 10 9 для N = 8). Кожен стовпець містить найбільше одного ферзя, що дає тільки N N розстановок (1,7 * 10 7 для N = 8). Ніякі два ферзя не можна поставити в один рядок, а тому, для того щоб вектор (а 1, а 2, ..., a N) був рішенням, він повинен бути перестановкою елементів (1, 2, ..., N), що дає тільки N! (4,0 * 10 4 для N = 8) можливостей. Ніякі два ферзя не можуть перебувати на одній діагоналі, це скорочує число можливостей ще більше (для N = 8 в дереві залишається 2056 вузлів). Отже, за допомогою ряду спостережень ми виключили з розгляду велика кількість можливих розстановок N ферзів на дошці розміром N * N. Використання такого аналізу для скорочення процесу перебору називається пошуком з обмеженнями або відсіканням гілок у зв'язку з тим, що при цьому віддаляються піддерева з дерева. Друге. Іншим удосконаленням є злиття, або склеювання, гілок. Ідея полягає в тому, щоб уникнути виконання двічі однієї і тієї ж роботи: якщо два або більше піддерев даного дерева ізоморфні, ми хочемо досліджувати лише одна з них. У задачі про ферзя ми можемо використовувати склеювання, зауваживши, що якщо а 1> éN/2ù, то знайдене рішення можна відобразити і отримати рішення, для якого а 1 £ éN/2ù. Отже, дерева, відповідні, наприклад, випадків а 1 = 2 і а 1 = N-1, ізоморфні.
Наступні малюнки ілюструють сказане і пояснюють введення використовуваних структур даних.
Структури даних.
Up: array [2 .. 16] of boolean; {ознака зайнятості діагоналей першого типу}
Down: array [-7 .. 7] of boolean; {ознака зайнятості діагоналей другого типу}
Vr: array [1 .. 8] of boolean; {ознака зайнятості вертикалі}
X: array [1 .. 8] of integer; {номер вертикалі, на якій стоїть ферзь на кожній горизонталі}
Далі йде пояснення "цеглинок", з яких "складається" рішення (технологія "знизу вгору").
procedure Hod (i, j: integer); {зробити хід}
begin
X [i]: = j; Vr [j]: = false; Up [i + j]: = false; Down [ij]: = false;
end;
procedure O_hod (i, j: integer); {скасувати хід}
begin
Vr [j]: = true; Up [i + j]: = true; Down [ij]: = true;
end;
function D_hod (i, j: integer);
{Перевірка допустимості ходу в позицію (i, j)}
begin
D_hod: = Vr [j] andUp [i + j] andDown [ij];
end;
Основна процедура пошуку одного варіанта розстановки ферзів має вигляд:
procedure Solve (i: integer; var q: boolean);
var j: integer;
begin
j: = 0;
repeat
inc (j); q: = false; {цикл по вертикалі}
if D_hod (i, j) then begin Hod (i, j);
if i <8 then begin Solve (i +1, q);
if not q then O_hod (i, j);
end else q: = true; {рішення знайдено}
end;
until q or (j = 8);
end;
Можливі модифікації.
Пошук всіх рішень. Для дошки 8 * 8 відповідь 92.
Procedure Solve (i: integer);
var j: integer;
begin
if i <= N then begin
for j: = 1 to N do if D_hod (i, j) then begin
Hod (i, j);
Solve (i +1);
O_hod (i, j);
end;
end
else begin
Inc (S); {лічильник числа рішень, глобальна змінна}
Print; {висновок рішення}
end;
end;
Пошук тільки не симетричних рішень. Для дошки 8 * 8 відповідь 12.
Ця модифікація вимагає попередніх роз'яснень. З кожного рішення задачі про ферзя можна отримати ряд інших за допомогою обертань дошки на 90 о, 180 о і 270 о і дзеркальних відображень щодо ліній, що розділяють дошку навпіл (система координат фіксована). Доведено, що в загальному випадку для дошки N * N (N> 1) для будь-якої допустимої розстановки N ферзів можливі три ситуації:
· При одному відображенні дошки виникає нова розстановка ферзів, а при поворотах та інших відображеннях нових рішень не виходить;
· Нове рішення при повороті на 90 о і її відображення дають ще дві розстановки;
· Три повороту і чотири відображення дають нові розстановки.
Для відсікання симетричних рішень по всьому безлічі рішень потрібно визначити певний стосунок порядку. Уявімо рішення у вигляді вектора довжиною N, координатами якого є числа від 1 до N. Для ферзя, що стоїть в i-му рядку, координатою його стовпця є i-я координата вектора. Для того, щоб не враховувати симетричні рішення, будемо визначати мінімальний вектор серед усіх векторів, що отримуються в результаті симетрій. Процедури Sim1, Sim2, Sim3 виконують дзеркальні відображення вектора рішення щодо горизонтальної, вертикальної і однієї з діагональних осей. Відомо (з геометрії), що композиція цих симетрій дає всі визначені вище симетрії шахової дошки, причому не принципово, в якій послідовності виконуються ці процедури для кожної конкретної композиції. Перевірка «на мінімальність» рішення проводиться функцією Cmp, яка повертає значення true в тому випадку, коли одне з симетричних рішень суворо менше поточного.
{Не кращий варіант реалізації - відсікання на виведення рішень}
type Tarray = array [1 .. N] of integer;
procedure Sim1 (var X: Tarray);
var i: integer;
begin
for i: = 1 to N do X [i]: = NX [i] +1;
end;
procedure Sim2 (var X: Tarray);
var i, r: integer;
begin
for i: = 1 to N do begin
r: = X [i]; X [i]: = X [N-i +1]; X [N-i +1]: = r;
end;
end;
procedure Sim3 (var X: Tarray);
var Y: Tarray;
i: integer;
begin
for i: = 1 to N do Y [X [i]]: = i;
X: = Y;
end;
function Cmp (X, Y: Tarray): boolean;
var i: integer;
begin
i: = 1;
while (i <= N) and (Y [i] = X [i]) do Inc (i);
if i> N then Cmp: = false
else if Y [i] <X [i] then Cmp: = true else Cmp: = false;
end;
Procedure Solve (i: integer);
var j: integer; f: boolean;
Y: Tarray;
begin
if i <= N then begin
for j: = 1 to N do if D_hod (i, j) then begin
Hod (i, j);
Solve (i +1);
O_hod (i, j);
end;
end
else begin
f: = true;
for j: = 0 to 7 do begin
Y: = X;
if j and 1 = 0 then Sim1 (Y);
if j and 2 = 0 then Sim2 (Y);
if j and 4 = 0 then Sim3 (Y);
if Cmp (Y, X) then f: = false;
end;
if f then begin
Inc (S); {лічильник числа рішень, глобальна змінна}
Print; {висновок рішення}
end;
end;
end;
Розбір задачі починається з оцінки числа 64! - Така загальна кількість способів розмітки дошки 8 * 8. Кожну розмітку слід оцінювати на предмет того, чи є вона способом обходу конем дошки (рішення в "лоб"). Потім оцінюємо порядок скорочення перебору виходячи з умови - логіка вибору чергового ходу коня. Будемо вважати, що поля для ходу вибираються за годинниковою стрілкою. Пояснення ілюструється наступними малюнками.
Структури даних.
Const N =; M =;
Dx: array [1 .. 8] of integer = (-2, -1,1,2,2,1, -1-2);
Dy: array [1 .. 8] of integer = (1,2,2,1, -1, -2, -2, -1);
Var A: array [-1 .. N +2, -1 .. M +2] of integer;
Основний фрагмент реалізації - процедура Solve.
procedure Solve (x, y, l: integer);
var z, i, j: integer;
begin
A [x, y]: = l;
if l = N * M then Inc (t)
else for z: = 1 to 8 do begin i: = x + Dx [z]; j: = y + Dy [z];
if A [i, j] = 0 then Rec (i, j, l +1)
end;
A [x, y]: = 0;
end;
for i: =- 1 to N +2 do for j: =- 1 to M do A [i, j]: =- 1;
for i: = 1 to N do for j: = 1 to M do A [i, j]: = 0;
t: = 0;
for i: = 1 to N do for j: = 1 to M do Solve (i, j, 1);
writeln ('кількість способів обходу конем дошки', N ,'*', M ,'--', t);
Змінимо логіку так, щоб був тільки один варіант обходу конем дошки. При цьому маршрут коня перебуває з використанням правила Варнсдорф вибору чергового ходу (запропоновано більше 150 років тому). Його суть - при обході шахової дошки коня слід ставити на поле, з якого він може зробити мінімальну кількість переміщень на ще не зайняті поля, якщо таких полів кілька, можна вибирати будь-яке з них. У цьому випадку в першу чергу займаються кутові поля і кількість "повернень" значно зменшується.
Варіант процедури Solve для цього випадку.
procedure Solve (x, y, l: integer);
varW: array [1 .. 8] of integer;
xn, yn, i, j, m: integer;
begin
A [x, y]: = l;
if (l <N * N) then begin
for i: = 1 to 8 do begin {формування масиву W}
W [i]: = 0; xn: = x + dx [i]; yn: = y + dy [i];
if (A [xn, yn] = 0) the begin
for j: = 1 to 8 do
if (A [xn + dx [j], yn + dy [j]] = 0) the Inc (W [i]);
end else W [i]: =- 1;
end;
i: = 1;
while (i <= 8) do begin
m: = 1; {шукаємо клітку, з якої можна зробити найменше число переміщень}
for j: = 2 to 8 do if W [j] <W [m] then m: = j;
if (W [m]> = 0) and (W [m] <maxint)
then Solve (x + dx [m], y + dy [m], l +1);
W [m]: = maxint; {відзначаємо використану в переборі клітку}
Inc (i);
end;
end
else begin <висновок рішення>;
halt;
end;
A [x, y]: = 0;
end;
· В кожній клітині вибирається ще не досліджений шлях;
· Якщо з досліджуваної в даний момент клітки немає шляхів, то повертаємося на один крок назад (у попередню клітину) і намагаємося вибрати інший шлях.
Природними модифікаціями завдання пошуку всіх шляхів виходу з лабіринту є:
· Пошук одного шляху;
· Пошук одного шляху найкоротшою довжини методом «хвилі».
Вирішення першого завдання.
program Labirint;
const Nmax =...;
dx: array [1 .. 4] of integer = (1,0, -1,0);
dy: array [1 .. 4] of integer = (0,1,0, -1);
type MyArray = array [0 .. Nmax +1,0 .. Nmax +1] of integer;
var A: MyArray;
xn, yn, xk, yk, N: integer;
procedure Init;
begin
<Введення лабіринту, координат початкової та кінцевої клітин. Межі поля відзначаються як перешкоди>;
end;
procedure Print;
....
begin
<Висновок матриці А - мітками виділено шлях виходу з лабіринту>;
end;
procedure Solve (x, y, k: integer); {k - номер кроку, x, y - координати клітини}
var i: integer;
begin
A [x, y]: = k;
if (x = xk) and (y = yk) then Print
else for i: = 1 to 4 do
if A [x + dx [i], y + dy [i]] = 0 then Solve (x + dx [i], y + dy [i], k +1);
A [x, y]: = 0;
end;
begin
Init;
Solve (xn, yn, 1);
end.
Порадившись, остров'яни вирішили, що буде достатньо, якщо в парламенті буде хоча б один член кожної партії.
Допоможіть остров'янам організувати такий, як можна більш малочисельний парламент, в якому будуть представлені члени всіх партій.
Вихідні дані: кожна партія і її президент мають один і той самий порядковий номер від 1 до N (4 £ N £ 150). Вам дані списки всіх N партій острова Нової Демократії. Виведіть пропонований Вами парламент у вигляді списку номерів її членів. Наприклад, для чотирьох партій:
Список членів парламенту 2 (складається з одного члена).
Завдання ставиться до класу NP-повних задач. Її рішення - повний перебір всіх варіантів. Покажемо, що ряд евристик дозволяє скоротити перебір для деяких наборів вихідних даних.
Уявімо інформацію про партії та їх членів за допомогою наступного зорового образу - таблиці. Для прикладу з формулювання завдання вона має вигляд:
Тоді задачу можна переформулювати наступним чином. Знайти мінімальне число стовпців, таких, що безліч одиниць з них "покривають" безліч всіх рядків. Очевидно, що для прикладу це один стовпець - другий. Поговоримо про структури даних.
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.
Установа освіти
«Гомельський державний університет ім. Ф. Скорини »
Математичний факультет
Кафедра МПУ
Курсова робота
Перебір з поверненням
Виконавець:
Студентка групи М-32
Ловренчук А.Ю.
Науковий керівник:
Канд. фіз-мат. наук, доцент
Звягіна Т.Є.
Гомель 2007
Введення
Дано N впорядкованих множин U 1, U 2, ..., U N (N - відомо), і потрібно побудувати вектор A = (a 1, a 2, ..., a N), де a 1 ÎU 1, a 2 ÎU 2, ..., a N ÎU N, що задовольняє заданій множині умов і обмежень.
В алгоритмі перебору вектор А будується покомпонентно зліва направо. Припустимо, що вже знайдено значення перших (k-1) компонент, А = (а 1, а 2, ..., а (k-1),?, ...,?), Тоді заданий безліч умов обмежує вибір наступного компоненти а k деяким безліччю S k ÌU k. Якщо S k <> [] (порожній), ми маємо право вибрати в якості а k найменший елемент S k і перейти до вибору (k +1) компоненти і так далі. Однак якщо умови такі, що S k виявилося порожнім, то ми повертаємося до вибору (k-1) компоненти, відкидаємо а (k-1) і вибираємо як нового а (k-1) той елемент S (k-1), який безпосередньо випливає за щойно відкинутим. Може виявитися, що для нового а (k-1) умови завдання допускають непорожнє S k, і тоді ми намагаємося знову вибрати елемент а k. Якщо неможливо вибрати а (k-1), ми повертаємося ще на крок назад і вибираємо новий елемент а (k-2) і так далі.
Графічне зображення - дерево пошуку. Корінь дерева (0 рівень) є порожній вектор. Його сини суть безліч кандидатів для вибору а 1, і, в загальному випадку, вузли k-го рівня є кандидатами на вибір а k за умови, що а 1, а 2, ..., а (k-1) вибрані так, як вказують предки цих вузлів. Питання про те, чи має завдання рішення, рівносильний питання, чи є які-небудь вузли дерева рішеннями. Розшукуючи всі рішення, ми хочемо отримати всі такі вузли.
Рекурсивна схема реалізації алгоритму.
procedure Backtrack (вектор, i);
begin
if <вектор є рішенням> then <записати його>
else begin <обчислити Si>;
for aÎSi do Backtrack (векторêêa, i +1);
{Êê-додавання до вектора компоненти}
end;
end;
Оцінка часової складності алгоритму. Дана схема реалізації перебору призводить до експоненціальним алгоритмам. Дійсно, нехай всі рішення мають довжину N, тоді дослідити потрібно близько çS 1 ç * çS 2 ç *...* çS N ç вузлів дерева. Якщо значення S i обмежено деякою константою С, то отримуємо порядку З N вузлів.
1. Завдання про розстановку ферзів
На шаховій дошці N * N потрібно розставити N ферзів таким чином, щоб жоден ферзь не атакував іншого.Відзначимо наступне. Всі можливі способи розміщення ферзів - З N N ^ 2 (близько 4,4 * 10 9 для N = 8). Кожен стовпець містить найбільше одного ферзя, що дає тільки N N розстановок (1,7 * 10 7 для N = 8). Ніякі два ферзя не можна поставити в один рядок, а тому, для того щоб вектор (а 1, а 2, ..., a N) був рішенням, він повинен бути перестановкою елементів (1, 2, ..., N), що дає тільки N! (4,0 * 10 4 для N = 8) можливостей. Ніякі два ферзя не можуть перебувати на одній діагоналі, це скорочує число можливостей ще більше (для N = 8 в дереві залишається 2056 вузлів). Отже, за допомогою ряду спостережень ми виключили з розгляду велика кількість можливих розстановок N ферзів на дошці розміром N * N. Використання такого аналізу для скорочення процесу перебору називається пошуком з обмеженнями або відсіканням гілок у зв'язку з тим, що при цьому віддаляються піддерева з дерева. Друге. Іншим удосконаленням є злиття, або склеювання, гілок. Ідея полягає в тому, щоб уникнути виконання двічі однієї і тієї ж роботи: якщо два або більше піддерев даного дерева ізоморфні, ми хочемо досліджувати лише одна з них. У задачі про ферзя ми можемо використовувати склеювання, зауваживши, що якщо а 1> éN/2ù, то знайдене рішення можна відобразити і отримати рішення, для якого а 1 £ éN/2ù. Отже, дерева, відповідні, наприклад, випадків а 1 = 2 і а 1 = N-1, ізоморфні.
Наступні малюнки ілюструють сказане і пояснюють введення використовуваних структур даних.
Up: array [2 .. 16] of boolean; {ознака зайнятості діагоналей першого типу}
Down: array [-7 .. 7] of boolean; {ознака зайнятості діагоналей другого типу}
Vr: array [1 .. 8] of boolean; {ознака зайнятості вертикалі}
X: array [1 .. 8] of integer; {номер вертикалі, на якій стоїть ферзь на кожній горизонталі}
Далі йде пояснення "цеглинок", з яких "складається" рішення (технологія "знизу вгору").
procedure Hod (i, j: integer); {зробити хід}
begin
X [i]: = j; Vr [j]: = false; Up [i + j]: = false; Down [ij]: = false;
end;
procedure O_hod (i, j: integer); {скасувати хід}
begin
Vr [j]: = true; Up [i + j]: = true; Down [ij]: = true;
end;
function D_hod (i, j: integer);
{Перевірка допустимості ходу в позицію (i, j)}
begin
D_hod: = Vr [j] andUp [i + j] andDown [ij];
end;
Основна процедура пошуку одного варіанта розстановки ферзів має вигляд:
procedure Solve (i: integer; var q: boolean);
var j: integer;
begin
j: = 0;
repeat
inc (j); q: = false; {цикл по вертикалі}
if D_hod (i, j) then begin Hod (i, j);
if i <8 then begin Solve (i +1, q);
if not q then O_hod (i, j);
end else q: = true; {рішення знайдено}
end;
until q or (j = 8);
end;
Можливі модифікації.
Пошук всіх рішень. Для дошки 8 * 8 відповідь 92.
Procedure Solve (i: integer);
var j: integer;
begin
if i <= N then begin
for j: = 1 to N do if D_hod (i, j) then begin
Hod (i, j);
Solve (i +1);
O_hod (i, j);
end;
end
else begin
Inc (S); {лічильник числа рішень, глобальна змінна}
Print; {висновок рішення}
end;
end;
Пошук тільки не симетричних рішень. Для дошки 8 * 8 відповідь 12.
Ця модифікація вимагає попередніх роз'яснень. З кожного рішення задачі про ферзя можна отримати ряд інших за допомогою обертань дошки на 90 о, 180 о і 270 о і дзеркальних відображень щодо ліній, що розділяють дошку навпіл (система координат фіксована). Доведено, що в загальному випадку для дошки N * N (N> 1) для будь-якої допустимої розстановки N ферзів можливі три ситуації:
· При одному відображенні дошки виникає нова розстановка ферзів, а при поворотах та інших відображеннях нових рішень не виходить;
· Нове рішення при повороті на 90 о і її відображення дають ще дві розстановки;
· Три повороту і чотири відображення дають нові розстановки.
Для відсікання симетричних рішень по всьому безлічі рішень потрібно визначити певний стосунок порядку. Уявімо рішення у вигляді вектора довжиною N, координатами якого є числа від 1 до N. Для ферзя, що стоїть в i-му рядку, координатою його стовпця є i-я координата вектора. Для того, щоб не враховувати симетричні рішення, будемо визначати мінімальний вектор серед усіх векторів, що отримуються в результаті симетрій. Процедури Sim1, Sim2, Sim3 виконують дзеркальні відображення вектора рішення щодо горизонтальної, вертикальної і однієї з діагональних осей. Відомо (з геометрії), що композиція цих симетрій дає всі визначені вище симетрії шахової дошки, причому не принципово, в якій послідовності виконуються ці процедури для кожної конкретної композиції. Перевірка «на мінімальність» рішення проводиться функцією Cmp, яка повертає значення true в тому випадку, коли одне з симетричних рішень суворо менше поточного.
{Не кращий варіант реалізації - відсікання на виведення рішень}
type Tarray = array [1 .. N] of integer;
procedure Sim1 (var X: Tarray);
var i: integer;
begin
for i: = 1 to N do X [i]: = NX [i] +1;
end;
procedure Sim2 (var X: Tarray);
var i, r: integer;
begin
for i: = 1 to N do begin
r: = X [i]; X [i]: = X [N-i +1]; X [N-i +1]: = r;
end;
end;
procedure Sim3 (var X: Tarray);
var Y: Tarray;
i: integer;
begin
for i: = 1 to N do Y [X [i]]: = i;
X: = Y;
end;
function Cmp (X, Y: Tarray): boolean;
var i: integer;
begin
i: = 1;
while (i <= N) and (Y [i] = X [i]) do Inc (i);
if i> N then Cmp: = false
else if Y [i] <X [i] then Cmp: = true else Cmp: = false;
end;
Procedure Solve (i: integer);
var j: integer; f: boolean;
Y: Tarray;
begin
if i <= N then begin
for j: = 1 to N do if D_hod (i, j) then begin
Hod (i, j);
Solve (i +1);
O_hod (i, j);
end;
end
else begin
f: = true;
for j: = 0 to 7 do begin
Y: = X;
if j and 1 = 0 then Sim1 (Y);
if j and 2 = 0 then Sim2 (Y);
if j and 4 = 0 then Sim3 (Y);
if Cmp (Y, X) then f: = false;
end;
if f then begin
Inc (S); {лічильник числа рішень, глобальна змінна}
Print; {висновок рішення}
end;
end;
end;
2. Задача про шаховому коні
Існують способи обійти шаховим конем дошку, побувавши на кожному полі по одному разу. Скласти програму підрахунку числа способів обходу.Розбір задачі починається з оцінки числа 64! - Така загальна кількість способів розмітки дошки 8 * 8. Кожну розмітку слід оцінювати на предмет того, чи є вона способом обходу конем дошки (рішення в "лоб"). Потім оцінюємо порядок скорочення перебору виходячи з умови - логіка вибору чергового ходу коня. Будемо вважати, що поля для ходу вибираються за годинниковою стрілкою. Пояснення ілюструється наступними малюнками.
Структури даних.
Const N =; M =;
Dx: array [1 .. 8] of integer = (-2, -1,1,2,2,1, -1-2);
Dy: array [1 .. 8] of integer = (1,2,2,1, -1, -2, -2, -1);
Var A: array [-1 .. N +2, -1 .. M +2] of integer;
Основний фрагмент реалізації - процедура Solve.
procedure Solve (x, y, l: integer);
var z, i, j: integer;
begin
A [x, y]: = l;
if l = N * M then Inc (t)
else for z: = 1 to 8 do begin i: = x + Dx [z]; j: = y + Dy [z];
if A [i, j] = 0 then Rec (i, j, l +1)
end;
A [x, y]: = 0;
end;
for i: =- 1 to N +2 do for j: =- 1 to M do A [i, j]: =- 1;
for i: = 1 to N do for j: = 1 to M do A [i, j]: = 0;
t: = 0;
for i: = 1 to N do for j: = 1 to M do Solve (i, j, 1);
writeln ('кількість способів обходу конем дошки', N ,'*', M ,'--', t);
Змінимо логіку так, щоб був тільки один варіант обходу конем дошки. При цьому маршрут коня перебуває з використанням правила Варнсдорф вибору чергового ходу (запропоновано більше 150 років тому). Його суть - при обході шахової дошки коня слід ставити на поле, з якого він може зробити мінімальну кількість переміщень на ще не зайняті поля, якщо таких полів кілька, можна вибирати будь-яке з них. У цьому випадку в першу чергу займаються кутові поля і кількість "повернень" значно зменшується.
Варіант процедури Solve для цього випадку.
procedure Solve (x, y, l: integer);
varW: array [1 .. 8] of integer;
xn, yn, i, j, m: integer;
begin
A [x, y]: = l;
if (l <N * N) then begin
for i: = 1 to 8 do begin {формування масиву W}
W [i]: = 0; xn: = x + dx [i]; yn: = y + dy [i];
if (A [xn, yn] = 0) the begin
for j: = 1 to 8 do
if (A [xn + dx [j], yn + dy [j]] = 0) the Inc (W [i]);
end else W [i]: =- 1;
end;
i: = 1;
while (i <= 8) do begin
m: = 1; {шукаємо клітку, з якої можна зробити найменше число переміщень}
for j: = 2 to 8 do if W [j] <W [m] then m: = j;
if (W [m]> = 0) and (W [m] <maxint)
then Solve (x + dx [m], y + dy [m], l +1);
W [m]: = maxint; {відзначаємо використану в переборі клітку}
Inc (i);
end;
end
else begin <висновок рішення>;
halt;
end;
A [x, y]: = 0;
end;
3. Завдання про лабіринт
Класична задача для вивчення теми. Як і попередні, не обходиться без уваги в будь-якій книзі з інформатики. Формулювання просте. Дано клітинне поле, частина клітин зайнята перешкодами. Необхідно потрапити з деякою заданою клітини в іншу задану клітину шляхом послідовного переміщення по клітинах. Виклад завдання спирається на малюнок довільного лабіринту і дві «промальовування» з використанням простого перебору і методу «хвилі». Класичний перебір виконується за правилами, запропонованими в 1891 р. Е. Люка в "Математичні дозвілля":· В кожній клітині вибирається ще не досліджений шлях;
· Якщо з досліджуваної в даний момент клітки немає шляхів, то повертаємося на один крок назад (у попередню клітину) і намагаємося вибрати інший шлях.
Природними модифікаціями завдання пошуку всіх шляхів виходу з лабіринту є:
· Пошук одного шляху;
· Пошук одного шляху найкоротшою довжини методом «хвилі».
Вирішення першого завдання.
program Labirint;
const Nmax =...;
dx: array [1 .. 4] of integer = (1,0, -1,0);
dy: array [1 .. 4] of integer = (0,1,0, -1);
type MyArray = array [0 .. Nmax +1,0 .. Nmax +1] of integer;
var A: MyArray;
xn, yn, xk, yk, N: integer;
procedure Init;
begin
<Введення лабіринту, координат початкової та кінцевої клітин. Межі поля відзначаються як перешкоди>;
end;
procedure Print;
....
begin
<Висновок матриці А - мітками виділено шлях виходу з лабіринту>;
end;
procedure Solve (x, y, k: integer); {k - номер кроку, x, y - координати клітини}
var i: integer;
begin
A [x, y]: = k;
if (x = xk) and (y = yk) then Print
else for i: = 1 to 4 do
if A [x + dx [i], y + dy [i]] = 0 then Solve (x + dx [i], y + dy [i], k +1);
A [x, y]: = 0;
end;
begin
Init;
Solve (xn, yn, 1);
end.
4. Завдання про парламент
На острові Нової Демократії кожен з жителів організував партію, яку сам і очолив. На загальний подив, навіть у найменш численною партії виявилося не менше двох осіб. На жаль, фінансові труднощі не дозволили створити парламент, куди увійшли б, як передбачалося за Конституцією острова, президенти всіх партій.Порадившись, остров'яни вирішили, що буде достатньо, якщо в парламенті буде хоча б один член кожної партії.
Допоможіть остров'янам організувати такий, як можна більш малочисельний парламент, в якому будуть представлені члени всіх партій.
Вихідні дані: кожна партія і її президент мають один і той самий порядковий номер від 1 до N (4 £ N £ 150). Вам дані списки всіх N партій острова Нової Демократії. Виведіть пропонований Вами парламент у вигляді списку номерів її членів. Наприклад, для чотирьох партій:
| Президенти | Члени партій |
| 1 | 2,3,4 |
| 2 | 3 |
| 3 | 1,4,2 |
| 4 | 2 |
Завдання ставиться до класу NP-повних задач. Її рішення - повний перебір всіх варіантів. Покажемо, що ряд евристик дозволяє скоротити перебір для деяких наборів вихідних даних.
Уявімо інформацію про партії та їх членів за допомогою наступного зорового образу - таблиці. Для прикладу з формулювання завдання вона має вигляд:
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
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 і 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.
Виконуючи операцію винятку жителів, «представництво» яких скромніше, ніж у решти, отримуємо.
Отже, партії з 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. Модифікація задачі про знаходження мінімального домінуючого множини.
Розглянемо простий переборних варіант рішення задачі, працездатний тільки для невеликих значень 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, Wi * Weight [k], st + i * Price [k]);
end;
end;
Ініціалізація змінних, висновок рішення і викликає частина (Rec (1, w, 0)) очевидні. У цій логіці відсутні блоки попередньої обробки, загальних відсікань і відсікань за номером предмета (дивіться завдання про парламент). У блоці попередньої обробки доцільно знайти якесь рішення, краще, якщо воно буде якомога ближче до оптимального (найкращий варіант завантаження рюкзака). «Жадібний» логіка дає перше наближення. Крім того, розумно виконати сортування, наприклад, за значенням вартості предметів або відношенню ваги предмета до його вартості. Побудова блоку загальних відсікань аналогічно тому, як це зроблено в задачі про парламент, а відповідь на питання, чому предмети даного типу не варто складати в рюкзак, залишається відкритим.
2. Гері М., Джонсон Д. Обчислювальні алгоритми і труднорешаемие задачі.-М.: Світ, 1982.
3. Рейнгольд Е., Нівергельт Ю., Део М. Комбінаторні алгоритми: Теорія і практіка.-М.: Світ, 1980.
4. Суханов А.А. Олімпіадні завдання. Неопублікований матеріал. - СПб.: 1996.
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
блок загальних відсікань |
begin min: = mn; Rbest: = Rwork end;
end
else begin
i: = k;
while i <= N do begin
блок відсікань по 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 |
Висновок - перебір слід виконувати не по всім жителям і не для всіх партій! Якщо б це виручало завжди. Надактивність жителів зводить нанівець цей шлях скорочення перебору. Залишається сподіватися, що хтось повинен і вирощувати хліб, а не тільки мітингувати. Отже, "нарис" загальної логіки попередньої обробки.
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 має вагу w i і вартість v i (i = 1,2, ..., n). Потрібно визначити максимальну вартість вантажу, вага якого не перевищує W. Позначимо кількість предметів типу i через k i, тоді потрібно максимізувати v 1 * k 1 + v 2 * k 2 +...+ v n * k n при обмеженнях w 1 * k 1 + w 2 * k 2 + ... + w n * k n £ W, де k i - цілі (0 £ k i £ [W / w i]), квадратні дужки означають цілу частину числа.Розглянемо простий переборних варіант рішення задачі, працездатний тільки для невеликих значень 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, Wi * Weight [k], st + i * Price [k]);
end;
end;
Ініціалізація змінних, висновок рішення і викликає частина (Rec (1, w, 0)) очевидні. У цій логіці відсутні блоки попередньої обробки, загальних відсікань і відсікань за номером предмета (дивіться завдання про парламент). У блоці попередньої обробки доцільно знайти якесь рішення, краще, якщо воно буде якомога ближче до оптимального (найкращий варіант завантаження рюкзака). «Жадібний» логіка дає перше наближення. Крім того, розумно виконати сортування, наприклад, за значенням вартості предметів або відношенню ваги предмета до його вартості. Побудова блоку загальних відсікань аналогічно тому, як це зроблено в задачі про парламент, а відповідь на питання, чому предмети даного типу не варто складати в рюкзак, залишається відкритим.
Висновок
Ініціалізація змінних, висновок рішення і викликає частина (Rec (1, w, 0)) очевидні. У цій логіці відсутні блоки попередньої обробки, загальних відсікань і відсікань за номером предмета (дивіться завдання про парламент). У блоці попередньої обробки доцільно знайти якесь рішення, краще, якщо воно буде якомога ближче до оптимального (найкращий варіант завантаження рюкзака). «Жадібний» логіка дає перше наближення. Крім того, розумно виконати сортування, наприклад, за значенням вартості предметів або відношенню ваги предмета до його вартості. Побудова блоку загальних відсікань аналогічно тому, як це зроблено в задачі про парламент, а відповідь на питання, чому предмети даного типу не варто складати в рюкзак, залишається відкритим.Література
1. Ахо А., Хопкрофта Д., Ульман Д. Побудова та аналіз обчислювальних алгорітмов.-М.: Світ, 1979.2. Гері М., Джонсон Д. Обчислювальні алгоритми і труднорешаемие задачі.-М.: Світ, 1982.
3. Рейнгольд Е., Нівергельт Ю., Део М. Комбінаторні алгоритми: Теорія і практіка.-М.: Світ, 1980.
4. Суханов А.А. Олімпіадні завдання. Неопублікований матеріал. - СПб.: 1996.