Реферат: Метод розгалужень і меж Евристичні алгоритми Застосування принципу оптимальності
while (черга не порожня ) and (її перший елемент має оцінку E<Cmin)
do
begin
Вилучити з черги її перший елемент Node;
if синами вузла Node є листки then
Обчислити вартість синів Node та за необхідності
запам'ятати нову поточну мінімальну вартість Cmin
else
Обчислити оцінку вартості синів вузла Node та
додати до черги лише тих із них, чия оцінка не більше Cmin
end .
2 . Евристичні алгоритми
Повернемося до задачі про розподіл завдань по трьох процесорах і спробуємо розв'язати її у зовсім інший спосіб.
Нехай ми маємо неповний розподіл (S 1 , S 2 , S 3 ) усіх завдань, крім останнього. У цьому випадку найкраще розподілити останнє завдання, додавши його час до найменшого з S 1 , S 2 , S 3 , тобто передати його до найменш завантаженого процесора.
Тепер правилом "передати чергове завдання до найменш завантаженого процесора " будемо керуватися при розподілі кожного з завдань . Застосування цього правила виражається алгоритмом, за яким завдання розподіляються без будь-якого перебирання варіантів:
розподілити перші три завдання по одному на процесор ;
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.
Правило "передати чергове завдання до найменш завантаженого процесора ", яким ми керувалися при розподілі завдань, є прикладом евристики . Взагалі, значенням цього слова є "мистецтво відшукання істини", а в інформатиці евристика – це правило, метод або прийом, призначений для підвищення ефективності пошуку розв'язку задачі [Сл].
Алгоритм, побудований на основі застосування евристики, називається евристичним . Як правило, евристичні алгоритми дозволяють швидко побудувати розв'язок задачі, але не завжди гарантують, що він дійсно буде найкращим.
Приклад 1. Розглянемо ще одну задачу та дві евристики для неї. Нехай, як і раніше, задано упорядкований за незростанням список часів виконання завдань T 1 , T 2 , … , Tn , але кількість процесорів не фіксовано. Замість цього задано час T 0 , і треба визначити найменшу кількість процесорів, яка забезпечує виконання всіх завдань у межах T 0 . Зрозуміло, що T 0 ³ T 1 .
Спочатку переформулюємо цю задачу в інших термінах. Час виконання завдання можна розглядати як об'єм предмету, а час T 0 – як об'єм ящиків, по яких розподіляються предмети (форма ящиків та предметів неважлива). Отже, треба обчислити найменшу кількість ящиків, необхідних для розподілу всіх предметів. Тепер сформулюємо дві евристики.
Е1. "Перший прийнятний ". Перший предмет кладемо в перший ящик. Другий також, якщо він там уміщається. Якщо не уміщається, то кладемо його в другий ящик. Взагалі, черговий предмет кладемо в ящик із найменшим номером, в якому він уміщається .
Е2. "Найкращий прийнятний ". Черговий предмет кладеться в той ящик, у якому залишається найменший ще допустимий незайнятий об'єм . Якщо таких ящиків кілька, то з них вибираємо ящик із найменшим номером.
Запис відповідних евристичних алгоритмів залишаємо вправою.
3 . Застосування принципу оптимальності