Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 21. Кратчайшие пути. EMST минимальное эвклидово остовное дерево
|
|
Обозначения:
EMST минимальное эвклидово остовное дерево
ТС транзитивное замыкание
APSP кратчайшие пути для всех пар
SSSP кратчайшие пути для единственного источника
SSLP наиболее длинные пути для единственного источника
(+) (в сетях с неотрицательными весами)
(±) (в сетях с весами, которые могут быть неотрицательными)
(DAG) (в ациклических сетях)
DC разностные ограничения
HP гамильтоновы пути
JS(WD) планирование заданий (с конечными сроками)
=> применение сведения
Верхние границы. Если мы имеем эффективный алгоритм решения задачи В и можем доказать, что А сводится к В, то мы имеем эффективный алгоритм и для решения задачи А. Возможно, что существует другой лучший алгоритм для А, однако эффективность В является верхней границей того, что можно достичь для А. Например, наше доказательство того, что задача планирования работ сводится к задаче поиска наиболее длинных путей в ациклических сетях, превращает наш алгоритм решения второй задачи в эффективный алгоритм решения первой задачи.
Нижние границы. Если известно, что любой алгоритм для задачи А требует определенных ресурсов, и можно доказать, что А сводится к В, то мы знаем, что В имеет, по крайней мере, те же самые требования к ресурсам, поскольку из существования лучшего алгоритма для В следовало бы существование лучшего алгоритма для А (до тех пор пока стоимость сведения будет ниже стоимости алгоритма В). Другими словами, эффективность А в лучшем случае достигает нижней границы того, что можно получить для В. Например, эта технология применялась в разделе 19.3 для того, чтобы показать, что вычисление транзитивного замыкания является таким же трудоемким, как умножение логических матриц, и в разделе 20.7 - чтобы показать, что вычисление эвклидового MST столь же трудоемко, как сортировка.
Неразрешимость. В частности, можно доказать, что некоторая задача неразрешима, показав, что к ней сводится другая неразрешимая задача. Например, свойство 21.18 говорит о том, что задача поиска кратчайших путей неразрешима, поскольку к ней сводится задача поиска гамильтонова пути, которая неразрешима.
Помимо этих общих результатов, ясно, что более детальная информация об эффективности определенных алгоритмов для решения специфических задач может непосредствен-
Часть 5. Алгоритмы на графах
но быть применена к другим задачам, которые сводятся к первым. Когда мы ищем верхнюю границу, мы можем анализировать алгоритм, связанный с данным, проводить эмпирические исследования и т.п., дабы определить, получено ли лучшее решение задачи. Во время разработки качественного универсального алгоритма можно затратить усилия на разработку и тестирование качественной реализации и затем создать соответствующий АТД, что позволит расширить применимость.
Мы используем сведение в качестве базового инструментального средства в этой и следующей главах. Акцент делается на общей применимости рассматриваемых задач и общей применимости решающих их алгоритмов - за счет сведения к ним других задач. Важно также иметь представление о взаимоотношениях между моделями в иерархической структуре их проблемных формулировок. Например, линейное программирование является общей формулировкой, которая важна не только потому, что к ней сводятся многие задачи, но также и из-за того, что известно, что эта задача не относится к NP-труд-ным. Другими словами, не известно способа сведения общей задачи поиска кратчайших путей (или любой другой NP-трудной задачи) к линейному программированию. Результаты подобного рода подробно обсуждаются в части 8.
Не все задачи являются разрешимыми, но к настоящему времени уже наработаны хорошие общие модели, подходящие для широкого класса задач, для которых известны методы решения. Кратчайшие пути в сетях — это наш первый пример такой модели. По мере продвижения ко все более общим проблемным областям, мы попадаем в область исследования операций (OR, operations research), которая занимается анализом математических методов принятия решений и главной целью которой является развитие и изучение таких моделей. Одна ключевая проблема при исследовании операций заключается в нахождении модели, которая в наибольшей степени подходит для решения задачи и которая умещает эту задачу в данную модель. Эта область исследований известна также как математическое программирование (название, данное до наступления эры компьютеров, т.е. перед новой трактовкой слова " программирование"). Сведение — это современная концепция, которая представляет по сути то же, что и математическое программирование, и является основой нашего понимания стоимости вычислений для широкого круга приложений.