Метод розгалужень і меж Евристичні алгоритми Застосування принципу оптимальності

Реферат на тему:

Метод розгалужень і меж . Евристичні алгоритми . Застосування принципу оптимальності

1. Метод розгалужень і меж

Обхід усіх вузлів дерева пошуку варіантів може виявитися надто довгим. Наприклад, якщо в дереві всі вузли є допустимими, кожний проміжний вузол має m синів, а глибина дерева n , то всього в дереві 1+m +m ² + … +mⁿ =(m^{n +1} -1)/(m -1) вузлів. Уже за m =10 та n =10 це більш, ніж 10¹⁰ . Якщо припустити, що комп'ютер здатний обробити 10⁵ вузлів за секунду, то обхід такого дерева триватиме 10⁵ секунд, або приблизно добу.

Існує багато практичних задач, де вимагається відшукати чи побудувати не всі можливі варіанти, а лише один із них, найкращий у деякому розумінні, визначеному в задачі. Отже, тут з'являється таке поняття, як цінність варіантів. Загальним принципом розв'язання таких задач є скорочення обходу дерева варіантів. У ньому відкидаються деякі гілки, про які можна стверджувати, що вони не містять варіантів більш цінних, ніж уже знайдені. Розглянемо приклад.

Задача про три процесори . Нехай є три процесори, здатні виконувати завдання з однаковою швидкістю. Є набір завдань, про кожне з яких відомий час його виконання. Порядок виконання завдань неважливий. Якщо процесор почав виконувати завдання, то виконує його до кінця протягом зазначеного часу. Переключення процесора на виконання нового завдання відбувається миттєво. Треба так розподілити завдання між процесорами, шоб момент закінчення останнього завдання був мінімальним. Назвемо цю величину вартістю розподілу . Отже, займемося обчисленням мінімальної вартості серед можливих розподілів. Сам розподіл, що забезпечує таку вартість, для початку нас не цікавитиме.

Приклад . Нехай є 6 завдань, час виконання яких відповідно 7, 8, 9, 10, 11, 12. Якщо в зазначеному порядку розподілити перші три завдання між процесорами, а потім давати їх у тому ж порядку процесорам, що звільняються, то перший процесор закінчить роботу в момент 7+10=17, другий – у момент 8+11=19, а третій – 9+12=21. Маємо вартість 21. Проте їх можна розподілити інакше – 7+12, 8+11, 9+10, одержавши вартість 19.-

Перше, що ми зробимо в розв'язанні задачі – упорядкуємо завдання за незростанням часу їх виконання. Отже, нехай P ₁ , … , P_n – завдання, часи виконання T ₁ , … , T_n яких задовольняють нерівності T ₁ ³ … ³T_n . Розподіл можна подати послідовністю пар вигляду (i ; k ), де i – номер завдання, k – номер процесора, на якому воно виконується. Наприклад, за часів 12, 11, 10, 9, 8, 7 найкращий розподіл подається як

<(1; 1), (2; 2), (3; 3), (4; 3), (5; 2), (6; 1)>.

Подібно до розміщень ферзів, можна говорити про повний розподіл – довжини n , та неповний – меншої довжини. Так само утворимо дерево пошуку розподілів. Його коренем є порожній розподіл, синами кореня – три розподіли <(1; 1)>, <(1; 2)>, <(1; 3)> тощо, тобто синами кожного розподілу вигляду

v =<(1; k ₁ ), … , (i ; k_i )>

за i <n є три розподіли

v ₁ =<(1; k ₁ ), … , (i ; k_i ), (i +1; 1)>,

v ₂ =<(1; k ₁ ), … , (i ; k_i ), (i +1; 2)>,

v ₃ =<(1; k ₁ ), … , (i ; k_i ), (i +1; 3)>.

Повні розподіли є листками вигляду <(1; k ₁ ), … , (n ; k_n )>.

Тепер займемося упорядкуванням обходу дерева таким чином, щоб варіанти з меншою вартістю оброблялися якомога раніше, а варіанти з більшою вартістю – якомога пізніше. За розподілом v =<(1; k ₁ ), … , (i ; k_i )>, де i £ n , неважко обчислити трійку часів роботи процесорів (S ₁ , S ₂ , S ₃ ) з його виконання. Очевидно, його вартістю є найбільше з S ₁ , S ₂ , S ₃ . Такий розподіл за i <n та час T_{i +1} дають три варіанти трійок, відповідних його розподілам-синам v ₁ , v ₂ , v ₃ :

(S ₁ +T_{i +1} , S ₂ , S ₃ ), (S ₁ , S ₂ +T_{i +1} , S ₃ ), (S ₁ , S ₂ , S ₃ +T_{i +1} ).

За i +1=n неважко вибрати найменшу з цих трьох вартостей. Проте за i +1<n нас будуть цікавити не стільки вартості цих неповних розподілів, скільки нижні оцінки вартості тих повних розподілів