Введение

Эта часть посвящена трём важным методам построения и анализа эффективных алгоритмов: динамическому программированию (глава 16), жадным алгоритмам (глава 17) и амортизационному анализу (глава 18). Эти методы, возможно, чуть сложнее разобранных ранее («разделяй и властвуй», использование случайных чисел, решение рекуррентных соотношений), но не менее важны.

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

Жадные алгоритмы, как и динамическое программирование, применяются в тех случаях, когда искомый объект строится по частям. Жадный алгоритм делает на каждом шаге «локально оптимальный» выбор. Простой пример: стараясь набрать данную сумму денег минимальным числом монет, можно последовательно брать монеты наибольшего возможного достоинства (не превосходящего той суммы, которую осталось набрать).

Жадный алгоритм обычно работает гораздо быстрее, чем алгоритм, основанный на динамическом программировании. Однако жадный алгоритм вовсе не всегда даёт оптимальное решение. Во многих задачах применимость жадных алгоритмов удаётся доказать с помощью так называемых матроидов, о которых рассказано в главе 17.

Амортизационный анализ - это средство анализа алгоритмов, производящих последовательность однотипных операций. Вместо того, чтобы оценивать время работы для каждой из этих операций по отдельности, амортизационный анализ оценивает среднее

304

Часть IV Методы построения и анализа алгоритмов

время работы в расчёте на одну операцию. Разница может оказаться существенной, если долго выполняемые операции не могут идти подряд. На самом деле амортизационный анализ - не только средство анализа алгоритмов, но еще и подход к разработке алгоритмов: ведь разработка алгоритма и анализ скорости его работы тесно связаны. В главе 18 мы рассказываем о трёх методах амортизационного анализа алгоритмов.

Динамическое программирование

Подобно методу «разделяй и властвуй», динамическое программирование решает задачу, разбивая её на подзадачи и объединяя их решения. Как мы видели в главе 1, алгоритмы типа «разделяй и властвуй» делят задачу на независимые подзадачи, эти подзадачи - на более мелкие подзадачи и так далее, а затем собирают решение основной задачи «снизу вверх». Динамическое программирование применимо тогда, когда подзадачи не являются независимыми, иными словами, когда у подзадач есть общие «подподзадачи». В этом случае алгоритм типа «разделяй и властвуй» будет делать лишнюю работу, решая одни и те же подподзадачи по нескольку раз. Алгоритм, основанный на динамическом программировании, решает каждую из подзадач единожды и запоминает ответы в специальной таблице. Это позволяет не вычислять заново ответ к уже встречавшейся подзадаче.

В типичном случае динамическое программирование применяется к задачам оптимизации (optimization problems). У такой задачи может быть много возможных решений; их «качество» определяется значением какого-то параметра, и требуется выбрать оптимальное решение, при котором значение параметра будет минимальным или максимальным (в зависимости от постановки задачи). Вообще говоря, оптимум может достигаться для нескольких разных решений.

Как строится алгоритм, основанный на динамическом программировании? Надо:

1.описать структуру оптимальных решений,

2.выписать рекуррентное соотношение, связывающее оптимальные значения параметра для подзадач,

3.двигаясь снизу вверх, вычислить оптимальное значение параметра,

4.пользуясь полученной информацией, построить оптимальное решение.

Основную часть работы составляют шаги 1-3. Если нас интересует только оптимальное значение параметра, шаг 4 не нужен. Если же шаг 4 необходим, для построения оптимального решения иногда