![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 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), которая занимается анализом математических методов принятия решений и главной целью которой является развитие и изучение таких моделей. Одна ключевая проблема при исследовании операций заключается в нахождении модели, которая в наибольшей степени подходит для решения задачи и которая умещает эту задачу в данную модель. Эта область исследований известна также как математическое программирование (название, данное до наступления эры компьютеров, т.е. перед новой трактовкой слова " программирование"). Сведение — это современная концепция, которая представляет по сути то же, что и математическое программирование, и является основой нашего понимания стоимости вычислений для широкого круга приложений.
|