Жадібні алгоритми на графах




Скачати 12.33 Kb.
НазваЖадібні алгоритми на графах
Дата11.08.2013
Розмір12.33 Kb.
ТипДокументы

Школа олімпійського резерву ВІППО 13.03.2009

Жадібні алгоритми на графах

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

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

Ознаки того, що задачу можливо вирішити за допомогою жадібного алгоритму:

  1. Задачу можна розбити на підзадачі;

  2. Величини, що розглядаються в задачі, можна дробити так само як і задачу на підзадачі;

  3. Сума оптимальних рішень для двох підзадач дасть оптимальне рішення для всієї задачі.
^

Приклад задачі


Пасажирський ліфт не може підняти більше W кг. В ліфт намагаються влізти H людина, причому для кожного з них відома його вага: W1, W2 ... WH. Визначити яку максимальну кількість людей зможуть виїхати на ліфті за один раз.

Рішення


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

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

^ Алгоритм пошуку мінімального остового дерева

Алгоритм Дейкстри-Прима






Алгоритм Крускала








Схожі:

Жадібні алгоритми на графах iconТема. Жадібні алгоритми та динамічне програмування
Потім визначимо, скільки монет номіналом 10 центів не перевищить залишку від S. Ту саму операцію проведемо із монетою номіналом 5...
Жадібні алгоритми на графах iconУрок 20 Тема: Алгоритми
Розширити й поглибити поняття “алгоритм”. Сформувати поняття “виконавець алгоритму”. Учити складати алгоритми
Жадібні алгоритми на графах iconТема: Швидкі алгоритми сортування. Сортування Хоара
Мета: Закріпити поняття складності алгоритма. Сформувати вміння застосовувати швидкі алгоритми сортування
Жадібні алгоритми на графах iconЛінійні алгоритми Алгоритми, в яких команди виконуються послідовно...
Алгоритми, в яких команди виконуються послідовно одна за іншою, в порядку їх запису, називаються лінійними
Жадібні алгоритми на графах iconНаказ
...
Жадібні алгоритми на графах iconМи-розмовляли про жінок І про Тайах зокрема
Вона, — казали її подруги, — змінила свій харак­тер в Місті., Кількарічне кидання від одного мужчини до іншого, жадібні дотики до...
Жадібні алгоритми на графах iconТема заняття: Пошук в ширину на графах. Хвильовий алгоритм
Наявна матриця розміру M*N, що являє собою деякий лабіринт. Одна клітинка лабіринту є входом а інша виходом. Знайти найкоротший шлях...
Жадібні алгоритми на графах iconОсновні алгоритми сортування масивів
На і-му кроці значення і-го елемента масиву тимчасово запам'ятовується в змінній
Жадібні алгоритми на графах iconЛабораторна робота №6 Генетичні алгоритми
Мета: отримати навички розв’язання практичних задач за допомогою генетичних алгоритмів
Жадібні алгоритми на графах iconЛекція 3 амо 13. 10. 2008
Абстрактні алгоритми лише називають правило безпосереднього перероблення, але не описують, як реалізується обчислювальний процес
Додайте кнопку на своєму сайті:
Школьные материалы


При копіюванні матеріалу обов'язкове зазначення активного посилання © 2013
звернутися до адміністрації
nauch.com.ua
Головна сторінка