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

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

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

Обхід усіх вузлів дерева пошуку варіантів може виявитися надто довгим.
Наприклад, якщо в дереві всі вузли є допустимими, кожний проміжний вузол
має m синів, а глибина дерева n, то всього в дереві 1+m+m2+ …
+mn=(mn+1-1)/(m-1) вузлів. Уже за m=10 та n=10 це більш, ніж 1010. Якщо
припустити, що комп’ютер здатний обробити 105 вузлів за секунду, то
обхід такого дерева триватиме 105 секунд, або приблизно добу.

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

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

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

Перше, що ми зробимо в розв’язанні задачі – упорядкуємо завдання за
незростанням часу їх виконання. Отже, нехай P1, … , Pn – завдання, часи
виконання T1, … , Tn яких задовольняють нерівності T1 ? … ? Tn. Розподіл
можна подати послідовністю пар вигляду (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; k1), … , (i; ki)>

за i,

v2=<(1; k1), … , (i; ki), (i+1; 2)>,

v3=<(1; k1), … , (i; ki), (i+1; 3)>.

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

Тепер займемося упорядкуванням обходу дерева таким чином, щоб варіанти з
меншою вартістю оброблялися якомога раніше, а варіанти з більшою
вартістю – якомога пізніше. За розподілом v=<(1; k1), … , (i; ki)>, де
i? n, неважко обчислити трійку часів роботи процесорів (S1, S2, S3) з
його виконання. Очевидно, його вартістю є найбільше з S1, S2, S3. Такий
розподіл за i, <(1;2)>, <(1;3)> в
чергу достатньо записати лише один, для визначеності <(1; 1)>. Очевидно
також, що коли обробляється вузол із однаковими часами S[1], S[2], S[3],
то з трьох його синів до черги достатньо додати лише одного. Якщо ж два
з трьох часів у вузлі рівні, то до черги не додається один із двох
синів, що відрізняються лише порядком часів.

Опишемо обробку вузлів дерева таким алгоритмом.

Занести до черги розподіл (T[1], 0, 0; 1; T[1]);

Cmin:=? ;

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

? <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)>
подамо як послідовність , де aj позначає пару (j; kj).
Очевидно, що v(i) одержується з v(i-1) додаванням компонента ai.
Вартість розподілу при цьому не зменшується, тобто

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

Існує чимало задач, в яких розв’язок-послідовність
будується шляхом «нарощування» часткових розв’язків
новими компонентами ai. Умова (19.1) дозволяє відкидати ті часткові
розв’язки та всіх їх нащадків, якщо їх вартість не може бути меншою
вартості Cmin уже побудованого повного розв’язку. Таким чином, Cmin
виступає верхньою межею для вартості розв’язків, які є сенс будувати.
Але, як правило, обчислити вартість повного розв’язку можна лише після
його побудови. Для запобігання побудови всіх повних розв’язків треба
мати можливість оцінювати знизу їх вартість за вартістю побудованих
часткових. Чим точнішою буде така оцінка, тим ефективнішим буде
скорочення перебору.

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

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

;

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

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

Cmin:=? ;

while (черга не порожня) and (її перший елемент має оцінку E1.
Занумеруємо клітини кожного кільця числами від 0 до n-1. Позначимо через
Cki число, записане в клітині з номером i у кільці k, а через Ski –
найбільшу суму, яку можна набрати на шляху, що веде в цю клітину.
Очевидно, що S1i =C1i. Для початку обчислимо для кожної клітини другого
кільця найбільшу суму S2i на шляху довжини 2. За умовою задачі очевидно,
що

S2i=C2i+max{S1, i-1, S1i, S1, i+1} за i=1, … , n-2,

S20=C20+max{S1, n-1, S10, S11}, S2,n-1=C2, n-1+max{S1, n-2, S1, n-1,
S10}.

За цими сумами можна аналогічно підрахувати суми для клітин третього
кільця. Так само при переході до четвертого кільця достатньо знати лише
найбільші суми для клітин третього кільця тощо. Діставши суми для клітин
останнього кільця, вибираємо найбільшу з них, і задачу розв’язано.

Уточнення алгоритму залишаємо вправою. Скажемо лише, що суми Ski, k=2, …
, m, i=0, … , n-1, обчислюються за єдиною формулою

Ski=Cki+max{Sk-1, (i-1+n) mod n, Sk-1, i, Sk-1, (i+1) mod n}.

Оцінимо складність наведеного алгоритму. Очевидно, що при переході на
наступне кільце обчислюються n сум за сталу кількість дій кожна. Таких
переходів відбувається m-1, тому загальна кількість дій оцінюється як
O(nm).?

У наведених обчисленнях сум ми керувалися правилом: при переході на
наступне кільце неважливо, якими були шляхи до клітин попереднього
кільця. Аби вони давали найбільші суми, можливі для їх кінцевих клітин.
Ішими словами, вибір шляхів від клітин попереднього кільця в клітини
наступного не залежить від того, як саме ми вибирали клітини раніше.

Наведене правило є окремим конкретним випадком принципу оптимальності,
одного з головних у теорії динамічного програмування. Її автор,
Р.Беллман, сформулював цей принцип так:

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

Обсяг книжки не дозволяє викладати тут теорію динамічного програмування.
Вона велика й серйозна. Наведемо натомість ще один приклад застосування
принципу оптимальності.

Приклад 3. Розглянемо обчислення добутку n матриць

A = A1 ? A2 ? … ? An,

де кожна Ai – матриця з si-1 рядками та si стовпцями. Як відомо,
операція множення матриць є асоціативною, і результат не залежить від
порядку її застосування. Але від нього залежить кількість множень їх
елементів.

За традиційним алгоритмом множення матриць розмірами a? b та b? c
відбувається abc множень їх елементів. Наприклад, множення матриць A1?
A2? A3 розмірами 100? 1, 1? 100, 100? 1 відповідно у порядку (A1? A2)?
A3 вимагає 100? 1? 100+100? 100? 1=20000 множень, тоді як у порядку A1?
(A2? A3) – лише 1? 100? 1+100? 1? 1=200, тобто в 100 разів менше.

Отже, за послідовністю розмірів матриць s0, s1, s2, … , sn треба
обчислити найменшу кількість множень їх елементів, необхідних для
обчислення добутку матриць A = A1 ? A2 ? … ? An.

Очевидно, що при обчисленні добутку останнім виконується одне з множень,
тобто A=(A1? …? Ai)? (Ai+1? …? An), де 1? i? n-1. Якщо добутки A1? …? Ai
та Ai+1? …? An обчислено, то виконання останнього множення вимагає s0?
si? sn множень. Позначимо mik мінімальну кількість множень, необхідних
для обчислення Ai? Ai+1? …? Ak за i

Похожие записи