<<
>>

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

Благодаря своей концептуальной четкости и интуитивной привлекательности, жадные алгоритмы изучаются уже давно и нашли множество применений в ком- пьютерных науках. В этой главе основное внимание уделялось ситуациям, для ко- торых жадный алгоритм находит оптимальное решение.
Жадные алгоритмы также часто используются в качестве простых эвристик даже тогда, когда оптимальность решения не гарантирована. В главе 11 рассматриваются жадные алгоритмы, кото- рые находят решения, близкие к оптимальным.

Как упоминалось в главе 1, задача интервального планирования может рассма- триваться как частный случай задачи поиска независимого множества для графа, представляющего перекрытия в наборе интервалов. Графы, которые встречаются в таких задачах, называются интервальными графами и были тщательно изучены; за информацией, например, обращайтесь к книге Голамбика (Golumbic, 1980). Не только задача поиска независимого множества, но и многие другие вычислитель- ные задачи существенно упрощаются для особого случая интервальных графов.

Задача интервального планирования и задача планирования для минимизации максимальной задержки — два представителя категории базовых задач плани- рования, для которых простой жадный алгоритм выдает оптимальное решение. Описания многих других взаимосвязанных задач можно найти в работе Лоулера, Ленстры, Ринноя Кана и Шмойса (Lawler, Lenstra, Rinnoy Kan and Shmoys, 1993).

Автором оптимального алгоритма кэширования и его анализа является Бе- лади (Belady, 1966). Как упоминалось в тексте, в реальных условиях алгоритмы кэширования должны применять решения по вытеснению в реальном времени, без информации о будущих запросах. Такие стратегии кэширования будут рас- сматриваться в главе 13.

Алгоритм нахождения кратчайших путей в графе с неотрицательными длина- ми ребер предложил Дейкстра (Dijkstra, 1959).

Обзоры методов решения задачи минимального остовного дерева (вместе с историческим обзором) можно найти в статьях Грэма и Хелла (Graham, Hell, 1985) и Несетрила (Nesetril, 1997).

Алгоритм одиночной связи является одним из самых распространенных под- ходов к общей задаче кластеризации; в книгах Андерберга (Anderberg, 1973), Дуды, Харта и Сторка (Duda, Hart, Stork, 2001), а также Джейна и Дьюбса (Jain, Dubes, 1981) представлены различные методы кластеризации.

Алгоритм построения оптимальных префиксных кодов разработан Хаффманом (Huffman, 1952); более ранние методы, упоминаемые здесь, встречаются в книгах

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

Фано (Fano, 1949), а также Шеннона и Уивера (Shannon, Weaver, 1949). Общий обзор методов сжатия данных приведен в книге Белла, Клири и Уиттен (Bell, Cleary, Witten, 1990), а также в статье Лелевера и Хиршберга (Lelewer, Hirschberg, 1987). В более общем смысле эта тема относится к теории передачи информации, занимающейся методами представления и кодирования цифровых данных. Од- ной из фундаментальных работ в этой области является книга Шеннона и Уивера (Shannon, Weaver, 1949); в более позднем учебнике Кавера и Томаса (Cover, Thomas, 1991) приводится подробная информация по теме.

Авторами алгоритма нахождения ориентированного дерева с минимальной стоимостью обычно называют Чу и Лю (Chu, Liu, 1965) и Эдмондсу (Edmonds, 1967), разработавших его независимо друг от друга. Как упоминалось в главе, этот многофазный метод расширяет наши представления о том, что собой представляет жадный алгоритм. Он также важен с точки зрения линейного программирования, поскольку в этом контексте может рассматриваться как фундаментальное прак- тическое применение метода ценообразования, или прямо-двойственного метода (primal-dual technique), при разработке алгоритмов. Книга Немхаузера и Волси (Nemhauser, Wolsey, 1988) развивает эти связи с линейным программированием. Метод будет описан в главе 11 в контексте аппроксимирующих алгоритмов.

Как было сказано в начале главы, трудно дать точное определение того, что же следует считать жадным алгоритмом. В поисках такого определения даже непо- нятно, можно ли провести аналогию со знаменитым критерием непристойности судьи Стюарта из Верховного суда США («Когда я её вижу, я знаю, что это такое»), поскольку в научном сообществе нет единой точки зрения (и даже интуитивных представлений) относительно границы между жадными и нежадными алгорит- мами. Проводились исследования, направленные на формализацию классов жад- ных алгоритмов: из примеров можно упомянуть влиятельную теорию матроидов (Edmonds, 1971; Lawer, 2001). В статье Бородина, Нильсена и Ракоффа (Borodin, Nielsen, Rackoff, 2002) формализуются понятия жадных алгоритмов и алгоритмов «жадного типа», а также приводятся сравнения с другими теоретическими рабо- тами по данному вопросу.

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

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

  1. Дополнительная литература
  2. Дополнительная литература
  3. Дополнительная литература
  4. Дополнительная литература
  5. Дополнительная литература
  6. Дополнительная литература
  7. Дополнительная литература
  8. Дополнительная литература
  9. Дополнительная литература
  10. Дополнительная литература
  11. Список дополнительной литературы
  12. Дополнительная литература