Примечания и дополнительная литература
В области комбинаторной оптимизации изучались многие расширения и ва- риации на тему задачи о рюкзаке.
Как упоминалось в этой главе, псевдополино- миальная граница, встречающаяся в области динамического программирования, может стать неприемлемой при большом размере входных данных; в таких случаях динамическое программирование часто объединяется с другими эвристиками для практического решения больших экземпляров задачи о рюкзаке. Книга Мартелло и Тота (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 основано на результатах С. Дрейфуса и Р. Вагнера.
Еще по теме Примечания и дополнительная литература:
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература