Сайт підготовки до олімпіади з інформатики

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

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

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

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

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

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

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

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

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

Рішення

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

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

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

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