5.8 Жадные алгоритмы и динамическое программирование

Итак, что же представляют собой жадные алгоритмы? Перед тем, как ответить на этот вопрос, отве- тим на другой: а что же есть алго- ритм? Кажется, интуитивно мы это понимаем, однако интуиция имеет свойство подводить в самый не- подходящий момент, причем очень незаметно.

Просто алгоритмом будем назы- вать механизм, который должен га- рантировать не только то, что ре- шение будет найдено, но и то, что будет найдено именно оптималь- ное решение. Кроме того, алго- ритм должен обладать следующи- ми качествами:

• Ограниченность по времени (работа алгоритма должна прекратиться за разумное время);

• Правильность (алгоритм должен находить правильное решение);

• Детерминистичность (сколько бы раз не исполнялся алгоритм с одинаковыми входными дан- ными, результат должен быть один и тот же);

• Конечность (описание работы алгоритма должно содержать конечное число шагов);

• Однозначность (каждый шаг алгоритма должен интерпретироваться однозначно).

Эвристика – это прямая противоположность алгоритму, так как она не дает ни- каких гарантий ни того, что реше- ние будет найдено, ни того, что оно будет оптимальным. Между алгоритмом и эвристикой лежат два понятия, которые называют приблизительный алгоритм (ре- шение гарантировано, но его оп- тимальность – нет) и вероятност- ный алгоритм (решение не гаран- тировано, но если оно будет най- дено, то будет обязательно опти- мальным).

А теперь можно перейти к рас- смотрению жадных алгоритмов. Этот класс алгоритмов намного проще и быстрее, чем динамиче- ское программирование. Жад- ный алгоритм делает на каждом шаге локально оптимальный вы- бор, надеясь, что итоговое решение окажется оптимальным. Од- нако это не всегда так, и потому иногда бывает, что жадный алго- ритм в терминах вышеупомяну- того определения – не полноцен- ный алгоритм, а приблизитель- ный. Но для большого числа ал- горитмических задач жадные ал- горитмы действительно дают оп- тимум. Общую схему работы жадных алгоритмов дадим в кон- це, после рассмотрения конкрет- ных примеров.