.: Menu :.
Home
Реферати
Книги
Конспекти уроків
Виховні заходи
Зразки документів
Реферати партнерів
Завантаження
Завантажити
Електронні книги


????????...

 
��������...
Жадібні алгоритми 


Жадібні алгоритми
10.3. „Жадібні| алгоритми
Розглянемо невелике |дитяче| завдання. Допустимо, що у нас є монети гідністю 25, 10, 5 копійок і 1 копійку і потрібно повернути здачу 63 копійки. Майже не роздумуючи, ми перетворимо цю величину в дві монети по 25 копійок, одну монету в 10 копійок і три монети по одній копійці. Нам не тільки вдалося швидко визначити перелік монет потрібної гідності, але і, по суті, ми склали найкоротший список монет необхідної гідності.
Алгоритм, яким читач в цьому випадку напевно скористався, полягав у виборі монети найбільшої гідності (25 копійок), але не більше 63 копійок, додаванню її в список здачі і відніманню її вартості з 63 (виходить 38 копійок). Потім знову вибираємо монету найбільшої гідності, але не більше залишку (38 копійок): цією монетою знову виявляється монета в 25 копійок. Цю монету ми знову додаємо в список здачі, віднімаємо її вартість із залишку і т.д.
Цей метод внесення змін називається |жадібним| алгоритмом. На кожній окремій стадії |жадібний| алгоритм вибирає той варіант, який є локально оптимальним в тому або іншому сенсі. Зверніть увагу, що алгоритм для визначення здачі забезпечує в цілому оптимальне рішення лише унаслідок особливих властивостей монет. Якби у нас були монети гідністю 1 копійку, 5 і 11 копійок і потрібно було б дати здачу 15 копійок, то |жадібний| алгоритм вибрав би спочатку монету гідністю 11 копійок, а потім чотири монети по одній копійці, тобто всього п.ять монет. Проте в даному випадку можна було б обійтися трьома монетами по 5 копійок.
Ми вже зустрічалися в цій книзі з декількома |жадібними| алгоритмами, наприклад алгоритмом побудови найкоротшого шляху Дейкстри і алгоритмом побудови остовного дерева мінімальною вартістю Круськала. Алгоритм найкоротшого шляху Дейкстри є |жадібним| в тому сенсі, що він завжди вибирає вершину, найближчу до джерела, серед тих, найкоротший шлях яких ще невідомий. Алгоритм Круськала також |жадібний|. він вибирає з ребер, що залишаються, які не створюють цикл, ребро з мінімальною вартістю.

Мал. 10.10 Граф з ребром негативної вартості
Слід підкреслити, що не кожен |жадібний| алгоритм дозволяє отримати оптимальний результат в цілому. Як нерідко буває в житті, |жадібна стратегія| часом забезпечує лише хвилинну вигоду, тоді як в цілому результат може виявитися несприятливим. Подивимося, наприклад, що відбудеться, якщо в алгоритмах Дейкстри і Круськала допустити наявність ребер з негативними вагами. Виявляється, що на алгоритм Круськала побудови остовного дерева це ніяк не вплине: з його допомогою як і раніше можна буде одержати дерево мінімальної вартості. Але алгоритм Дейкстри в деяких випадках вже не дозволяє одержати найкоротші шляхи.
Приклад 10.4. На мал. 10.10 показаний граф з ребром негативної вартості між вершинами b і c. Якщо джерелом є вершина s, то алгоритм Дейкстри спочатку правильно визначає, що мінімальний шлях до а має протяжність 1. Тепер, розглядаючи ребра від s (або а) до b або c, алгоритм розраховує, що найкоротший шлях від c до b, а саме s > а > b, має довжину 3. Але далі одержуємо, що c має найкоротший шлях від s завдовжки 1.
Проте |жадібний| вибір b замість є невиправданим. Виявляється, що шлях s > a > c > b має довжину лише 2, тому обчислена нами мінімальна відстань для b є неправильным.
„Жадібні| алгоритми як евристики
Існують завдання, для яких жоден з відомих |жадібних| алгоритмів не дозволяє одержати оптимального рішення. проте є |жадібні| алгоритми, які з великою вірогідністю дозволяють одержувати |хороші| рішення. Нерідко цілком задовільним можна рахувати |майже оптимальне| рішення,що характеризується вартістю, яка лише на декілька відсотків перевищує оптимальну. У таких випадках |жадібний| алгоритм часто опиняється найшвидшим способом одержати |хороше| рішення. Взагалі кажучи, якщо дане завдання таке, що єдиним способом одержати оптимальне рішення є використання методу повного пошуку, тоді |жадібний| алгоритм або інший евристичний метод отримання хорошого (хоч і необов.язково оптимального) рішення може виявитися єдиним реальним засобом досягнення результату.
Приклад 10.5. Розглянемо одне знамените завдання, для отримання оптимального рішення якого зі всіх відомих нам алгоритмів підходять лише алгоритми повного перебору, час виконання яких залежить експоненціально від об.єму вхідних даних. Це завдання, яке називається завданням комівояжера, зводиться до пошуку в неорієнтованому графі з ваговими значеннями ребер такого маршруту (простого циклу, що включає всі вершини), у якого сума вагів складових його ребер буде мінімальною. Такий маршрут часто називають гамільтоновим циклом.
На мал. 10.11,а показаний граф з шістьма вершинами (їх часто називають |містами|), який може служити основою для завдання комівояжера. Задані координати кожної вершини, а вагою кожного ребра вважається його довжина. Зверніть увагу: ми припускаємо (і таке припущення характерний для завдання комівояжера), що існують всі ребра графа, тобто граф є повним. У більш загальних випадках, коли вага ребер не ґрунтується на евклідовій відстані, у ребра може опинитися нескінченна вага, чого насправді, звичайно, не буває.
На мал. 10.11, б, в, г, д показані чотири маршрути по шести |містах|. Читач може самостійно прикинути, який з цих маршрутів є оптимальним (можливо, такого маршруту взагалі немає). Протяжності цих чотирьох маршрутів дорівнюють 50.00, 49.73, 48.39 і 49.78 відповідно. маршрут на мал. 10.11,г є найкоротшим зі всіх можливих маршрутів.



Мал.. 10.11. Приклад задачі Камівояжера
Завдання комівояжера має ряд практичних застосувань. Як випливає з самої назви завдання, її можна використовувати для складання маршруту людини, яка повинна відвідати ряд пунктів і, врешті-решт, повернутися в початковий пункт. Наприклад, завдання комівояжера використовувалося для складання маршрутів осіб, монет, що займаються виїмкою, з таксофонів. В цьому випадку вершинами є місця установки таксофонів і |базовий пункт|. Вартістю кожного ребра (відрізка маршруту) є час в дорозі між двома крапками (вершинами) на маршруті.

Search:
????????...

над чим мене примусив замислитися роман панаса Мирного та Івана Білика

askjcjasz

askjcjasz

Етапи розвитку операційної системи

дворянський період національно-культурного відродження в україні

ораторский стиль мовлення

Етапи розвитку операційної системи

твір чому я навчився у гектора

Все про хамурапів

реферати з української літератури панас мирний чіпка вареник - борець за справедливість чи злочиність



?????????? ????????? ????
   
Created by Yura Pagor, 2007-2010