Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Глава 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), которая занимается анализом математических методов принятия решений и главной целью которой является развитие и изучение таких моделей. Одна ключевая проблема при исследовании операций заключается в нахождении модели, которая в наибольшей степени подходит для решения задачи и которая умещает эту задачу в данную модель. Эта область исследований известна также как математичес­кое программирование (название, данное до наступления эры компьютеров, т.е. перед но­вой трактовкой слова "программирование"). Сведение — это современная концепция, которая представляет по сути то же, что и математическое программирование, и являет­ся основой нашего понимания стоимости вычислений для широкого круга приложений.




mylektsii.ru - Мои Лекции - 2015-2018 год. (0.009 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал