WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Метод розгалужень і меж. Евристичні алгоритми. Застосування принципу оптимальності - Реферат

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


Реферат на тему:
Метод розгалужень і меж. Евристичні алгоритми. Застосування принципу оптимальності
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 найкращий розподіл подається як
.
Подібно до розміщень ферзів, можна говорити про повний розподіл - довжини n, та неповний - меншої довжини. Так само утворимо дерево пошуку розподілів. Його коренем є порожній розподіл, синами кореня - три розподіли , , тощо, тобто синами кожного розподілу вигляду
v=
за iv1=,
v2=,
v3=.
Повні розподіли є листками вигляду .
Тепер займемося упорядкуванням обходу дерева таким чином, щоб варіанти з меншою вартістю оброблялися якомога раніше, а варіанти з більшою вартістю - якомога пізніше. За розподілом v=, де i n, неважко обчислити трійку часів роботи процесорів (S1, S2, S3) з його виконання. Очевидно, його вартістю є найбільше з S1, S2, S3. Такий розподіл за i(S1+Ti+1, S2, S3), (S1, S2+Ti+1, S3), (S1, S2, S3+Ti+1).
За i+1=n неважко вибрати найменшу з цих трьох вартостей. Проте за i+1Розглянемо найпростіший спосіб такого оцінювання. Очевидно, що за неповного розподілу v перших i завдань із трійкою часів (S1, S2, S3) всі розподіли, що є його нащадками, мають вартість не меншу, ніж
E(v)=max{S1, S2, S3, min{S1, S2, S3}+Ti+1}.
Отже, оцінка E(v) є нижньою межею для вартості нащадків розподілу v.
Організуємо обхід дерева розподілів таким чином, що:
1. для кожного з вузлів обчислюється зазначена оцінка вартості,
2. вузли розглядаються у порядку зростання їх оцінок,
3. вузли з оцінкою, більшою від вартості вже одержаного повного розподілу, взагалі не розглядаються.
Ці міркування складають суть методу розгалужень і меж. Упорядкування вузлів робить обхід цілеспрямованим, а відкидання явно неперспективних піддерев скорочує його.
Уточнимо організацію даних для обробки вузлів у зазначеному порядку. Оскільки нас цікавлять не самі розподіли, а лише їх вартість, у вузлах дерева будемо зберігати тільки трійку часів та номер завдання, розподіленого останнім. Маючи список часів T[1], … , T[n] обробки завдань, неважко за цими даними обчислити оцінку вартості для неповних розподілів та саму вартість для повних. Для наочності цю величину також зберігатимемо у вузлі. Отже, вузол дерева подається трійкою часів S[1], S[2], S[3], номером завдання i та оцінкою вартості E, яка за imax{ S[1], S[2], S[3], min{ S[1], S[2], S[3]}+T[i+1]}.
Очевидно, що за i=n-1 ця величина є вартістю повного розподілу, який подається "кращим із синів" цього вузла дерева.
Проміжні вузли записуються не в магазин, а в чергу, елементи якої упорядковано за зростанням оцінок вартості. Таким чином, для подання черги зручно скористатися лінійним списком (п.16.3.3). Вузли, відповідні повним розподілам, в чергу не записуються, оскільки оцінка вартості є власне їх вартістю.
Очевидно, що спочатку з трьох розподілів , , в чергу достатньо записати лише один, для визначеності . Очевидно також, що коли обробляється вузол із однаковими часами S[1], S[2], S[3], то з трьох його синів до черги достатньо додати лише одного. Якщо ж два з трьох часів у вузлі рівні, то до черги не додається один із двох синів, що відрізняються лише порядком часів.
Опишемо обробку вузлів дерева таким алгоритмом.
Занести до черги розподіл (T[1], 0, 0; 1; T[1]);
Cmin:= ;
while (черга не порожня) and (її перший елемент має оцінку Edo
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 Черга
12
Як бачимо, перший елемент черги має оцінку вартості, гіршу за Cmin, тому подальше дослідження дерева варіантів не відбувається.За виконання алгоритму до черги додається 9 проміжних вузлів, а вилучається 4. Між тим, неважко підрахувати, що з урахуванням симетричних варіантів дерево містить 19 проміжних вузлів. Фактично, ми одержали потрібний розподіл взагалі без перебирання варіантів.
У загальному випадку метод розгалужень і меж не позбавляє перебирання. У цьому неважко переконатися, імітувавши наведений алгоритм на прикладі часів виконання завдань (12, 8, 7, 5, 4, 2).
Задача про розподіл завдань представляє
Loading...

 
 

Цікаве