Cmin:=? ;

while (черга не порожня) and (її перший елемент має оцінку E<Cmin)

do

begin

Вилучити з черги її перший елемент Node=(S[1], S[2], S[3]; i; E);

if i=n-1 then {синами вузла є листки}

Обчислити вартість синів вузла Node та за необхідності

запам'ятати нову поточну мінімальну вартість Cmin

else

Обчислити оцінку вартості синів вузла Node та

додати до черги лише тих із них, чия оцінка не більше Cmin

end

Уточнення цього алгоритму залишаємо вправою.

Розглянемо приклад обчислення мінімальної вартості розподілу за наведеним алгоритмом. Нехай задано час виконання п'яти завдань 9, 8, 7, 5, 4. Очевидно, що найкращий розподіл (9, 8+4, 7+5) має вартість 12. Значення Cmin та зміст черги, що виникають за наведеним алгоритмом, подамо таблицею:

Cmin | Черга

? | <9,0,0; 1; 9>

? | <9,8,0; 2; 9> <17,0,0; 2; 17>

? | <9,8,7; 3; 12> <9,15,0; 3; 15> <16,8,0; 3; 16> <17,0,0; 2; 17>

? | <9,8,12; 4; 12> <9,13,7; 4; 13> <9,8,11; 4; 13> <9,15,0; 3; 15>

<16,8,0; 3; 16> <17,0,0; 2; 17>

12 | <9,13,7; 4; 13> <9,8,11; 4; 13> <9,15,0; 3; 15> <16,8,0; 3; 16>

<17,0,0; 2; 17>

Як бачимо, перший елемент черги має оцінку вартості, гіршу за Cmin, тому подальше дослідження дерева варіантів не відбувається. За виконання алгоритму до черги додається 9 проміжних вузлів, а вилучається 4. Між тим, неважко підрахувати, що з урахуванням симетричних варіантів дерево містить 19 проміжних вузлів. Фактично, ми одержали потрібний розподіл взагалі без перебирання варіантів.

У загальному випадку метод розгалужень і меж не позбавляє перебирання. У цьому неважко переконатися, імітувавши наведений алгоритм на прикладі часів виконання завдань (12, 8, 7, 5, 4, 2).

Задача про розподіл завдань представляє чималу групу задач, які розв'язуються методом розгалужень і меж. Подивимося на цю задачу більш узагальнено. Розподіл (повний чи частковий) v(i)=<(1; k1), … , (i; ki)> подамо як послідовність <a1, a2, … , ai>, де aj позначає пару (j; kj). Очевидно, що v(i) одержується з v(i-1) додаванням компонента ai. Вартість розподілу при цьому не зменшується, тобто

C(v(i-1))? C(v(i)). (19.1)

Існує чимало задач, в яких розв'язок-послідовність <a1, a2, … , an> будується шляхом "нарощування" часткових розв'язків <a1, a2, … , ai-1> новими компонентами ai. Умова (19.1) дозволяє відкидати ті часткові розв'язки та всіх їх нащадків, якщо їх вартість не може бути меншою вартості Cmin уже побудованого повного розв'язку. Таким чином, Cmin виступає верхньою межею для вартості розв'язків, які є сенс будувати. Але, як правило, обчислити вартість повного розв'язку можна лише після його побудови. Для запобігання побудови всіх повних розв'язків треба мати можливість оцінювати знизу їх вартість за вартістю побудованих часткових. Чим точнішою буде така оцінка, тим ефективнішим буде скорочення перебору.

Отже, алгоритм розв'язання багатьох задач за методом розгалужень і меж має таку загальну структуру:

Для кожного можливого a1 занести до черги частковий розв'язок

<a1>;

Обчислити нижню оцінку E вартості його нащадків, що є

повними розв'язками;

Cmin:=? ;

while (черга не порожня) and (її перший елемент має оцінку E<Cmin)

do

begin

Вилучити з черги її перший елемент Node;

if синами вузла Node є листки then

Обчислити вартість синів Node та за необхідності

запам'ятати нову поточну мінімальну вартість Cmin

else

Обчислити оцінку вартості синів вузла Node та

додати до черги лише тих із них, чия оцінка не більше Cmin

end.

4. Евристичні алгоритми

Повернемося до задачі про розподіл завдань по трьох процесорах і спробуємо розв'язати її у зовсім інший спосіб.

Нехай ми маємо неповний розподіл (S1, S2, S3) усіх завдань, крім останнього. У цьому випадку найкраще розподілити останнє завдання, додавши його час до найменшого з S1, S2, S3, тобто передати його до найменш завантаженого процесора.

Тепер правилом "передати чергове завдання до найменш завантаженого процесора" будемо керуватися при розподілі кожного з завдань. Застосування цього правила виражається алгоритмом, за яким завдання розподіляються без будь-якого перебирання варіантів:

розподілити перші три завдання по одному на процесор;

for i:=4 to n do

begin

обчислити k – номер найменшого з S[1], S[2], S[3];

додати T[i] до S[k]

end

За цим алгоритмом завдання (12, 8, 7, 5, 4) розподіляються як (12, 8+4, 7+5). Очевидно, що краще не може бути.

Проте розподіл завдань за цим алгоритмом не завжди є найкращим. Наприклад, завдання (12, 8, 7, 5, 4, 2) розподіляються за ним як (12+2, 8+4, 7+5) з вартістю 14, хоча є кращий розподіл (12, 8+5, 7+4+2) з вартістю 13.

Правило "передати чергове завдання до найменш завантаженого процесора", яким ми керувалися при розподілі завдань, є прикладом евристики. Взагалі, значенням цього слова є "мистецтво відшукання істини", а в інформатиці евристика – це правило, метод або прийом, призначений для підвищення ефективності пошуку розв'язку задачі [Сл].

Алгоритм, побудований на основі застосування евристики, називається евристичним. Як правило, евристичні алгоритми дозволяють швидко побудувати розв'язок задачі, але не завжди гарантують, що він дійсно буде найкращим.

Приклад 19.1. Розглянемо ще одну задачу та дві евристики для неї. Нехай, як і раніше, задано упорядкований за незростанням список часів виконання завдань T1, T2, … , Tn, але кількість процесорів не фіксовано. Замість цього задано час T0, і треба визначити найменшу кількість процесорів, яка забезпечує виконання всіх завдань у межах T0. Зрозуміло, що T0? T1.

Спочатку переформулюємо цю задачу в інших термінах. Час виконання завдання можна розглядати як об'єм предмету, а час T0 – як об'єм ящиків, по яких розподіляються предмети (форма ящиків та предметів неважлива). Отже, треба обчислити найменшу кількість ящиків, необхідних для розподілу всіх предметів. Тепер сформулюємо дві евристики.

Е1. "Перший прийнятний". Перший