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

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

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

В этой главе мы обратимся к более мощному и нетривиальному методу разра- ботки алгоритмов — динамическому программированию. Охарактеризовать динами- ческое программирование будет проще после того, как вы увидите его в действии, но основная идея базируется на интуитивных представлениях, лежащих в основе принципа «разделяй и властвуй», и по сути противоположна жадной стратегии: алгоритм неявно исследует пространство всех возможных решений, расклады- вает задачу на серии подзадач, а затем строит правильные решения подзадач все большего размера. В некотором смысле динамическое программирование может рассматриваться как метод, работающий в опасной близости от границ перебора «грубой силой»: хотя оно систематически прорабатывает большой набор возмож- ных решений задачи, это делается без явной проверки всех вариантов. Именно из-за этой необходимости тщательного выдерживания баланса динамическое про- граммирование бывает трудно освоить; как правило, вы начинаете чувствовать себя уверенно только после накопления немалого практического опыта.


Помня об этом, мы рассмотрим первый пример динамического программирова- ния: задачу взвешенного интервального планирования, определение которой при- водилось в разделе 1.2. Разработка алгоритма динамического программирования для этой задачи будет проводиться в два этапа: сначала как рекурсивная процедура, которая сильно напоминает поиск «грубой силой», а затем, после переосмысления этой процедуры, — как итеративный алгоритм, который строит решения последо- вательно увеличивающихся подзадач.

6.1.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Глава 6 Динамическое программирование:

  1. Глава 2 Отрицательное и положительное программирование
  2. СТЕРЕОТИП ДИНАМИЧЕСКИЙ
  3. ПСИХОЛОГИЯ ДИНАМИЧЕСКАЯ
  4. АНАЛИЗ КАУЗАЛЬНО-ДИНАМИЧЕСКИЙ
  5. Динамическая медитация
  6. В динамических методах
  7. Иванова Г.С. Основы программирования, 2002
  8. ПСИХИКА: ПОНИМАНИЕ ДИНАМИЧЕСКОЕ
  9. Динамический смысл аспектов
  10. ПРОЦЕСС ПСИХИЧЕСКИЙ: ХАРАКТЕРИСТИКА ДИНАМИЧЕСКАЯ
  11. Основной курс (Программирование)
  12. Эстетика программирования
  13. Г.С.Иванова, Т.Н.Ничушкина, Е.К.Пугачев. Объектно- ориентированное программирование, 2001
  14. О. Л. Голицына, Т. Л. Партыка, И. И. Попов. ЯЗЫКИ ПРОГРАММИРОВАНИЯ, 2008
  15. Часть вторая Родительское программирование
  16. 46. Динамические процессы в малой группе
  17. Программирование телевизионного вещания
  18. Часть вторая Родительское программирование СУДЬБА ЧЕЛОВЕКА