• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Евристики

Розділ 2. Програмуванняз відходом назад. Евристичні алгоритми.

Контрольні запитання.

Таможенный союз России, Беларуси и Казахстана

Союзное государство России и Беларуси

см. Информационно-аналитический портал Союзного государства http://www.soyuz.by/

Создание единого таможенного пространства намечено с 01.07.2010 г.

1. Які загальні методи побудови алгоритмів Ви знаєте ?

2. В чому сутність методу часткових цілей?

3. Що таке метод під'йому?

4. Що означає метод відпрацювання назад?

5. Як формулюється умова задачі про джип?

6. Який алгоритм розв'язання задачі про джип.

7. Складіть програму для роз'язання задачі про джип

Евристичний алгоритм, чи евристика, визначається як алгоритм із наступними властивостями:

1. Він звичайно знаходить гарні, хоча не обов'язково оптимальні
рішення.

2. Його можна швидше і простіше реалізувати, ніж будь-який відомий
точний алгоритм (той, що гарантує оптимальне рішення).

Поняття «гарний» і «звичайно» у властивості 1 міняються від задачі до задачі. Наприклад, якщо для рішення задачі усі відомі точні алгоритми вимагають декількох років машинного часу, то ми можемо охоче прийняти будь-яке нетривіальне наближене рішення, що може бути отримане за розумний час. З іншого боку, маючи швидке, близьке до оптимального рішення, ми можемо прагнути все-таки до точного рішення.

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

1. Ті, які легко задовольнити.

2. Ті, які не так легко задовольнити.

Чи

1.Ті, які повинні бути задоволені.

2.Ті, стосовно яких ми могли б піти на компроміс.

Тоді ціль побудови алгоритму — створити алгоритм, що гарантує виконання вимог 1-го класу, але не обов'язково 2-го. Це не означає, що для задоволення вимог 2-го класу не робиться ніяких спроб, це просто означає, що не може бути дано ніяких гарантій, що вони будуть задоволені.

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

Як приклад розглянемо наступний «грубий» алгоритм рішення задачі комівояжера:

Алгоритм "Жадібний комівояжер".Побудувати наближене рішення TOUR з вартістю COST для задачі комівояжера с N містами і матрицею вартості С, починаючи с вершини U.

Крок 0. [Ініціалізація] TOUR = 0; COST = 0; V = U; позначаємо U- «використана», а всі інші вершини — «не використана». (Вершина V — положення на мережі в даний момент.)

Крок 1. [Відвідування всіх міст] For К = 1 to N -1 do виконати до кроку 2 od.

Крок 2. [Вибір наступного ребра] Нехай (V, W) — ребро с найменшою

вартістю, що веде з V у будь-яку невикористану вершину W; TOUR = TOUR + (V, W);

COST =COST+C(F, W); позначаємо W — «використана»; andV = W.

КрокЗ. [Завершення туру] Set TOUR = TOUR + (V, 1); COST = COST + C (V,1)..

На рис. 2.1.а зображена мережа; Рис. 2.1.6 —є ілюструють побудову туру комівояжера алгоритмом "Жадібний комівояжер", що починається с вершини 1, пройдені вершини позначені чорним квадратиком, а непройдені — кружком.

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

Звичайно грубі алгоритми дуже швидкі й інтуїтивно привабливі, але, як ми помітили, вони не завжди працюють. Нам повезло, і ми змогли легко

для алгоритму "Жадібний комівояжер". Однак не завжди можна легко показати, що грубий алгоритм не працює. Зрозуміло, якщо ми вважаємо, що наш грубий алгоритм працює завжди, то ми повинні довести, що це так.

Алгоритм "Жадібний комівояжер" заснований на ідеї підйому. Мета — знайти тур с мінімальною вартістю. Задача зведена до набору окремих цілей - знайти на кожнім крокі «найдешевше» місто, щоб відвідати його наступним. Алгоритм не будує плану вперед; поточний вибір робиться безвідносно до наступного вибору.

Оптимальне рішення задачі комівояжера має дві основних властивості:

1.Воно складається з множини ребер, що разом представляють тур.

2.Вартість ніякого іншого туру не буде менше даного.

Рис.2.1. Ілюстрація алгоритму "Жадібний комівояжер".

Алгоритм "Жадібний комівояжер" розглядає властивість 1 як обов'язкову, чи легку вимогу, а властивість 2 — як важку, щодо якого можна піти на компроміс.

Приклад с п'ятьма містами на рис. 2.1 відразу показує, що алгоритм 2 не гарантує властивість 2. Однак на крокі 2 робиться деяка спроба знизити вартість туру Т.

Звичайно, для алгоритму "Жадібний комівояжер" легко написати програму, але чи є він швидким? Для довільної задачі комівояжера с n містами потрібно О(n²) операцій, щоб побудувати чи прочитати матрицю вартістю С. Тому нижня межа складності будь-якого алгоритму, здатного дати нетривіальне можливе рішення цієї задачі, дорівнює О(n²). Неважко перевірити, що для будь-якої розумної реалізації кроків 1—3 потрібно не більше, ніж О(n²), операцій. Тому алгоритм "Жадібний комівояжер" настільки швидкий, наскільки можливо.

Очевидно, алгоритм "Жадібний комівояжер" — це гарний евристичний алгоритм. Звичайно, поняття «гарний» відносно. Оскільки алгоритм 1 (вичерпний комівояжер) занадто неефективний, епітет «гарний» може просто вказувати на той факт, що алгоритм "Жадібний комівояжер" — найкращий з наявних для великих (у розумних межах) значень n.

Якість алгоритму "Жадібний комівояжер" може бути значно поліпшено простою модифікацією. Найгіршою властивістю алгоритму є те, що вибір ребер дуже низької вартості при виконанні кроку 1 на ранніх чи середніх стадіях роботи алгоритму може привести до вибору дуже дорогих ребер у заключній стадії. Один зі способів вберегтись від цього — застосовувати алгоритм для кожного з р^n різних, випадково обраних, початкових міст. Інша модифікація може складатися в повторенні алгоритму для того ж самого початкового міста, але треба починати з другого по дешевині ребра і потім, бути може, повернутися до проходження найдешевших ребер для наступних вершин. Можливі й інші варіації. Потім можна вибрати найменший з розглянутих турів. Чи краще: зберігати тільки найдешевший тур з дотепер знайдених і відкидати частково побудовані тури, вартості яких уже перевищують вартість поточного найдешевшого туру. Звичайно, складність модифікованого алгоритму, що ми назвемо 22, може досягати порядку О(pn²).

Алгоритм "Жадібний комівояжер2"Утворити тури з 1< Р < N різних початкових міст для задач комівояжера с N містами. Послідовно будуються Р турів і запам'ятовується кращий з дотепер знайдених турів. Вхідні данні для алгоритму - значення N, Р, матриця вартостей С і Р початкових міст {V_b V₂,..., V_p}.

Крок 0. [Ініціалізація] К = Q; COST = оо; BEST = 0. (Змінна К підраховує

кількість дотепер використаних початкових міст; BEST служить для запам'ятовування кращого з дотепер знайдених турів, вартість якого дорівнює COST.)

Крок 1. [Початок нового туру] Поки К<Р виконати:

Крок 2. [Утворення нового туру] К = К+1; Викликати підалгоритм Жадібний комівояжер для (V_K).

5
19
22

Реалізація алгоритму "Жадібний комівояжер2" з підалгоритмом
"Жадібний комівояжер" не докладає зусиль. Алгоритм "Жадібний комівояжер2" повинен передавати поточне значення COST алгоритму "Жадібний комівояжер". Якщо в процесі виконання підпрограми вартість частково побудованого туру більше чи дорівнює COST, то повертається значення С(К) = .

Що вийде, якщо застосувати алгоритм "Жадібний комівояжер2" до задачі з п'ятьма містами, що показана на рис.2.2.? Візьмемо р=3, а як початкові міста — три вершини с непарними номерами.

Починаючи с вершини 1, знаходимо наступні ребра:

(1,2) з вартістю 25,

(2, 3) з вартістю 17 [зауважуємо, що (2,1) дає небажаний підтур],

(3,5) з вартістю 1,

(5.4) з вартістю 10 (це ребро ми змушені вибрати як єдино можливе на
даному етапі),

(4.1) з вартістю 9.

Загальна вартість отриманого туру дорівнює 62. Починаючи с вершини 3, знаходимо наступні ребра:

(3.5) з вартістю 1,

(5.2)з вартістю 8 [зауважуємо, що (5,3) дає небажаний подтур],

(2,1) з вартістю 5, (1,4) з вартістю 31,

(4.3) з вартістю 24.

Загальна вартість цього туру дорівнює 69. Нарешті, починаючи с вершини 5, знаходимо:

(5.3) з вартістю 7,

(3.4) з вартістю 6,

(4.1) з вартістю 9,

(1.2) з вартістю 25,

(2.5) з вартістю 25.

Тут загальна вартість дорівнює 72.

Цей маленький приклад показує, як повторне застосування евристичного алгоритму з деякими модифікаціями при кожнім повторенні може компенсувати його слабкі місця. Це схоже на взяття вибірки для визначення середнього значення випадкової перемінної. Чим більше вибірка, тим більше ми маємо інформації і тим кращу одержуємо оцінку. Однак у даному випадку в нас немає теоретичного результату, аналогічного закону великих чисел, що гарантує збіжність до значення істини.

Розглянемо ще один простий, але дуже ефективний евристичний алгоритм.

Припустимо, що в нас є множина п однакових процесорів, позначених Р₁ ... , Р_n, і m незалежних завдань J₁ ... , J_m, які потрібно виконати. Процесори можуть працювати одночасно, і будь-яке завдання можна виконувати на будь-якому процесорі. Якщо завдання завантажене в процесор, воно залишається там до кінця обробки. Час обробки завдання J_i відомо, він дорівнює ti, і=1, ... , m. Наша мета — організувати обробку завдань таким чином, щоб виконання всього набору завдань було довершено якнайшвидше. Насамперед побудуємо модель.

Розкладом може бути просто упорядкований список завдань L. Система працює в такий спосіб: перший процесор, що звільнився, бере зі списку наступне завдання. Якщо одночасно звільняються два чи більш процесори, то виконувати чергове завдання зі списку буде процесор с найменшим номером. Передбачається, що час, необхідне для завантаження завдання в машину, дорівнює нулю. Процесор буде обробляти завдання до повного завершення, а потім, якщо список не вичерпаний, одержить наступне завдання.

Припустимо, що мається три процесори і шість завдань с t₁=2, t₂=5, t₃=8, t₄=l, t₅=5 t₆=l. Розглянемо розклад L= (J₂, J₅, J_1, J₄, J_6, J₃)- У початковий момент часу Т=0, P₁ починає обробку J₂, P₂ починає J₅, а Р₃ починає J₁. Процесор Р₃ закінчує J₁ у момент часу Т=2 і починає обробляти завдання J₄, поки Р₁ і Р₂ ще працюють над своїми первісними завданнями. При Т=3 Р₃ знову закінчує завдання J₄ і починає обробляти завдання J₆, що завершується в момент Т=4. Тоді він починає останнє завдання J₃. Процесори P₁ і Р₂ закінчують завдання при Т=5, але, тому що список L порожній, вони зупиняються. Процесор Р₃ завершує виконання J₃ при Т=12. Розглянутий

розклад проілюстрований на рис. 6 діаграмою часу, відомої як схема Ганта. Очевидно, що розклад не оптимальний. У процесорів Р₁ і Р₂ великий час марного простою. Розклад L* = (J_3, J₂, J₅, J₁, J₄,J ₆,) дозволяє завершити всі завдання за Т*=8, що повинно бути оптимумом, тому що ніякий розклад не може дозволити завершити всі завдання за менший час, чим потрібно для виконання самого довгого завдання.

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

Розглянемо наступний, дуже простий евристичний алгоритм. Позначимо через L* розклад виконання завдань, у якому завдання с найбільшим часом обробки стоїть першим, потім у порядку убування часу обробки стоять інші завдання, останнім стоїть завдання с самим маленьким часом обробки. Евристичний алгоритм створює розклад L*, що перелічує завдання в порядку убування часу їхньої обробки (при збігу часів порядок вибирається довільно).

Повертаючи до попереднього прикладу, бачимо, що L*=( J_3, J₂, J₅, J₁, J₄, J₆). Розклад L* завершує всі завдання за час Т*=8, як показано на Рис. 7. Таким чином, у цьому прикладі евристичний алгоритм побудував оптимальний розклад.

Рис.2.3.. Схема Ганта для оптимального розкладу L.

Рис.2.4.. Схема Ганта для оптимального розкладу L*.

Простий евристичний алгоритм не є точним. На Рис. 8 показаний приклад для двох процесорів і t₁=3, t₂=3, t₃=2, t4=2, t₅=2. На Рис. 2.5, a показаний розклад L*, а на Рис. 2.5, б — оптимальний розклад.

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

За допомогою цього результату можна одержати верхню межу помилки, якщо ми скористаємося цим евристичним алгоритмом, не бажаючи затрачати зусиль на пошук оптимального розкладу. Для n=2, T*/T₀<7/6, і ця максимальна помилка досягається, як показано на Рис. 2.5. Для великого числа процесорів максимальна помилка може досягати 33%.

Рис. 2.5. Неоптимальний евристичний розклад L* і оптимальний розклад L₀

Точні верхні оцінки евристичних алгоритмів на найгірших випадках одержати важко. Такі оцінки відомі фактично для дуже малого числа евристичних алгоритмів.

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

Ця задача складання розкладу еквівалентна наступній задачі упакування. Нехай кожному процесору Pj відповідає шухляда Bj розміру То. Нехай кожному завданню J_; відповідає предмет розміру ti, рівного часу виконання завдання

Ji, i=l, ... ,n. Тепер для рішення задачі по складанню розкладу потрібно побудувати алгоритм, що дозволяє розмістити всі предмети в мінімальній кількості шухляд. Звичайно, не можна заповшовати шухляди більше їхнього обсягу То і предмети не можна дробити на частині.

Розі'лянемо множина предметів: два з них мають розмір 3 і три — розміри 2. Яке потрібно мінімальне число шухляд розміру 4, щоб помістити в них усі предмети? Відповідь показана на Рис. 9, де заштриховані ділянки позначають порожні місця в шухлядах.

Рис. 2.6. Мінімальна кількість шухляд розміру 4, необхідне для розміщення предметів розмірами 2,2, 2,3 і 3.

Для рішення щєї задачі існує кілька простих евристичних алгоритмів. Кожний з них може бути описаний у декількох рядках. Розглянемо чотири таких алгоритми:

Н1 (перше розміщення, що потрапилося, для заданого списку, First Fit, FF). Нехай L — деякий порядок предметів. Перший предмет з L кладемо в шухляду Ві Другий предмет з L кладемо в B1, якщо він туди міститься. У противному випадку кладемо його в наступну шухляду В2. Узагалі черговий предмет з L кладемо в шухляду Ві, куди цей предмет поміститься, причому індекс і шухляди найменший серед усіх можливих. Якщо предмет не міститься ні в одну з k частково заповнених шухляд, кладемо його в шухляду Bk+1. Цей основний крок повторюється, поки список L не буде вичерпаний.

Н2 (перше розміщення, що трапилося, с убуванням, First Fit Decreasing, FFD). Цей алгоритм відрізняється від алгоритму FF тим, що список L

упорядкований від великих предметів до меншого.

НЗ (краще розміщення для заданого списку, Best Fit, BF). Нехай L — заданий порядок завдань. Основний крок той же, що й у FF, але черговий предмет кладеться в ту шухляду, де залишається найменший невикористаний простір. Таким чином, якщо черговий предмет має розмір 3 і є чотири частково заповнених шухляди розміру 6, у яких залишилося 2, 3, 4 і 5 одиниць незаповненого простору, тоді предмет кладеться в другу шухляду, і той стає цілком заповненим.

Н4 (краще розміщення с убуванням, Best Fit Decreasing, BFD). Цей алгоритм такої ж, як і BF, але L упорядкований від великих предметів до меншого.

Рис. 2.7. Приклад, у якому евристичний алгоритм першого розміщення з убуванням дає найгірше можливе співвідношення: Nffd/No=11/9. Для цієї задачі упакування було знайдено кілька гарних верхніх оцінок. Одна з кращих, що належить Грехему, виглядає у такий спосіб. Нехай N₀ — мінімальна кількість необхідних шухляд, отримана за допомогою точного алгоритму. Якщо W_FFD позначає наближене рішення, знайдене алгоритмом FFD, тоді для будь-якого є > 0 і досить великого No

Таким чином, алгоритм FFD дає рішення, що не може бути гірше оптимального більш ніж на 23%. Це гарантована оцінка; для будь-якої конкретної задачі помилка може бути набагато менше.

Нелегко побудувати приклад, на якому евристичний алгоритм FFD працює найгіршим можливим образом. Представимо один такий «поганий випадок». Нехай е>0 — довільно обране, але маленьке додатне дійсне число. Припустимо, що всі шухляди розміру 1 і що потрібно упакувати наступні предмети:

6 предметів розміру 1/2 + є,

6 предметів розміру 1/4 + є,

12 предметів розміру 1/4, - 2є,

6 предметів розміру 1/4+ 2є.

На Рис. 2.7, а показане оптимальне упакування, що використовує N₀=9 шухляд. Очевидно, що це упакування оптимальне, тому що всі 9 шухляд цілком заповнені. Якщо для рішення цієї задачі застосувати евристичний алгоритм FFD пункту Н2, одержимо упакування, показану на Рис. 2.7.6, що використовує N_FFD ⁼11 шухляд.

Задачі упакування можуть бути дивно оманні. Наприклад, якщо потрібно упакувати в шухляди розміру 1000 предмети розмірів L=(760, 395, 395, 379, 379, 241, 200, 105, 105, 40), то евристичний алгоритм Н2 зажадає для цього N_FFD=3 шухляди. Це насправді оптимальне рішення. Зменшимо всі розміри на одну одиницю, що приводить до списку L'=(759, 394, 394, 378, 378, 240, 199,104,104, 39). Тепер евристичний алгоритм FFD дає N_FFD=4. Це, мабуть, не оптимальне і зовсім несподіване рішення. Чому цей приклад не порушує результату 11/9?

Звернемо увагу на іншу аномалію. Застосовуючи евристичний алгоритм Н1, упакуємо L=(7, 9, 7, 1, 6, 2, 4, 3) у шухляди розміру 13. Знаходимо, що N_Ff=3, як показано на Рис. 2.8 а; очевидно, що цей результат оптимальний. Заберемо предмет розміру 1, що приводить до списку L'= (7, 9,7,6,2,4,3). Тепер, як показано на Рис.2.8, б, JV_FF =4.

L=(7, 9, 7, 1, 6, 2, 4, 3) NFf=3

L'= (7, 9,7,6,2,4,3) JVFF =4

Рис. 2.8. Аномалія при використанні евристичного алгоритму першого розміщення, що потрапилося; упакування стає гірше, коли прибраний предмет.

Читайте також:

1. Евристики
2. РОЛЬ АРХІВНОЇ ЕВРИСТИКИ У ВИКОРИСТАННІ ДОКУМЕНТНОЇ ІНФОРМАЦІЇ

Переглядів: 816