Примечания и дополнительная литература

Первопроходцем в области систематического изучения динамического програм- мирования был Ричард Беллман (Bellman, 1957); алгоритм сегментированной задачи наименьших квадратов, приведенный в этой главе, основан на одной из ранних работ Беллмана (Bellman, 1961).
С тех пор динамическое программирова- ние поднялось до уровня метода, широко используемого в компьютерной науке, исследовании операций, теории управления и ряде других областей. Значительная часть последних разработок по теме относится к стохастическому динамическому программированию: если в нашей формулировке задачи неявно предполагалось, что все входные данные известны с самого начала, многие задачи в области пла- нирования, производства и складского учета и в других областях включают не- определенность, а алгоритмы динамического программирования для этих задач формулируют эту неопределенность по вероятностной формуле. Введение в стоха- стическое динамическое программирование приведено в книге Росса (Ross, 1983).

В области комбинаторной оптимизации изучались многие расширения и ва- риации на тему задачи о рюкзаке. Как упоминалось в этой главе, псевдополино- миальная граница, встречающаяся в области динамического программирования, может стать неприемлемой при большом размере входных данных; в таких случаях динамическое программирование часто объединяется с другими эвристиками для практического решения больших экземпляров задачи о рюкзаке. Книга Мартелло и Тота (Martello, Toth, 1990) посвящена вычислительным методам решения разных вариантов задачи о рюкзаке.

Динамическое программирование заняло место среди базовых методов вычис- лительной биологии в начале 1970-х годов в результате интенсивного изучения задачи сравнения последовательностей.

Санкофф (Sankoff, 2000) приводит инте- ресные исторические данные о ранних работах этого периода. В книгах Уотермена (Waterman, 1995) и Гасфилда (Gusfield, 1997) приводится подробное описание алгоритмов выравнивания последовательностей (а также многих сопутствующих алгоритмов в вычислительной биологии); Мэтьюз и Цукер (Mathews, Zukor, 2004) обсуждают будущее методов решения задачи предсказания вторичной структуры РНК. Алгоритм выравнивания последовательностей, эффективных по затратам памяти, был предложен Хиршбергом (Hirschberg, 1975).

Алгоритм для задачи нахождения кратчайшего пути, описанный в этой главе, основан на исходной работе Беллмана (Bellman, 1958) и Форда (Ford, 1956). Этот базовый метод поиска кратчайших путей был дополнен множеством оптимизаций, обусловленных как теоретическими, так и экспериментальными соображениями; на сайте Эндрю Голдберга приведена новейшая версия кода, написанного им для решения этой задачи (а также ряда других) по материалам работы Черкасски, Голд- берга и Радзика (Cherkassky, Goldberg, Radzik, 1994). Практическое применение методов нахождения кратчайших путей для маршрутизации в Интернете, а так- же достоинства и недостатки разных алгоритмов сетевых приложений описаны в книгах Бертсекаса и Галлагера (Bertekas, Gallager, 1992), Кешава (Keshav, 1997) и Стюарта (Stewart, 1998).

Примечания к упражнениям

Упражнение 5 было создано по мотивам обсуждения с Лилиан Ли; упражнение 6 основано на результатах Дональда Кнута; упражнение 25 основано на результа- тах Димитриса Бертсимаса и Эндрю Ло; упражнение 29 основано на результатах С. Дрейфуса и Р. Вагнера.


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

Еще по теме Примечания и дополнительная литература:

  1. Дополнительная литература
  2. Дополнительная литература
  3. Дополнительная литература
  4. Дополнительная литература
  5. Дополнительная литература
  6. Дополнительная литература
  7. Дополнительная литература
  8. Дополнительная литература
  9. Дополнительная литература
  10. Дополнительная литература