Примечания и дополнительная литература
Как упоминалось в главе 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) формализуются понятия жадных алгоритмов и алгоритмов «жадного типа», а также приводятся сравнения с другими теоретическими рабо- тами по данному вопросу.
Еще по теме Примечания и дополнительная литература:
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Список дополнительной литературы
- Дополнительная литература