Глава 21. Кратчайшие пути. Теперь предположим, что имеется эффективное сведение NP-трудной задачи А к кон­кретной задаче В

Теперь предположим, что имеется эффективное сведение NP-трудной задачи А к кон­кретной задаче В. Доказательство проведем от противного: если мы имеем эффектив­ный алгоритм для В, то мы могли бы воспользоваться им для решения любого экзем­пляра А за полиномиальное время с помощью сведения (преобразуем данный экземпляр А к экземпляру В, решаем эту задачу, затем преобразуем полученное реше­ние). Однако не существует известного алгоритма, который гарантировал бы такое решение для А (поскольку А является NP-трудной), так что допущение о существо­вании алгоритма с полиномиальным временем для задачи В некорректно - В также является NP-трудной задачей. ■

Продемонстрированная методика является чрезвычайно важной, поскольку она ис­пользовалась для того, чтобы показать, что огромное множество задач относятся к NP-трудным, предоставляя на выбор широкий круг задач, с помощью которых строились доказательства NP-трудности новой задачи. Например, в разделе 17.7 мы столкнулись с одной из классических NP-трудных задач — с задачей поиска гамильтонова пути, в ко­торой требуется определить, существует ли простой путь, содержащий все вершины дан­ного графа. Она была одной из первых задач, в отношении которой было показано, что она является NP-трудной (см. раздел ссылок). Довольно просто получить формулировку, в соответствии с которой из свойства 21.17 следует, что задача кратчайших путей отно­сится к NP-трудным:

Свойство 21.18. В сетях, в которых веса ребер могут быть отрицательными, задачи по­иска кратчайших путей являются NP-трудными.

Доказательство: Наше доказательство состоит в сведении задачи о гамильтоновом пути к задаче о кратчайших путях. Другими словами, мы покажем, что для решения зада­чи о гамильтоновом пути можно использовать любой алгоритм, с помощью которого можно найти кратчайшие пути в сетях с отрицательными весами ребер. Для заданно­го неориентированного графа мы строим сеть с ребрами в обоих направлениях, со­ответствующими каждому ребру в графе, и со всеми ребрами, имеющими веса -1. Крат­чайший (простой) путь, начинающийся в любой вершине этой сети, имеет длину 1 — V тогда и только тогда, когда граф имеет гамильтонов путь. Обратите внимание, что эта сеть изобилует отрицательными циклами. Не только каждый цикл в графе соответству­ют отрицательному циклу в сети, но также каждое ребро в графе соответствует циклу с весом -2 в данной сети.

Результат этих рассуждений состоит в том, что задача поиска кратчайших путей явля­ется NP-трудной, поскольку, если бы мы могли разработать эффективный алгоритм для задачи поиска кратчайших путей в сетях, то мы должны были бы иметь эффектив­ный алгоритм для задачи поиска гамильтонова пути в графах. ■

Как только будет обнаружено, что данная задача является NP-трудной, естественным будет разыскать те варианты этой задачи, которые можно решить. Для задач поиска крат­чайших путей мы стоим перед выбором между наличием массы эффективных алгоритмов для ациклических сетей или для сетей, в которых веса ребер не являются отрицательны­ми, и отсутствием хорошего решения для сетей, которые могли бы содержать циклы и отрицательные веса. Есть ли какие-либо другие виды сетей, которые нас могут заинте­ресовать? Это является темой раздела 21.7. Там, например, будет показано, что задача календарного планирования работ с конечными сроками сводится к варианту задачи по-

Часть 5. Алгоритмы на графах

иска кратчайших путей, которую можно эффективно решить. Типична следующая ситу­ация: поскольку нас интересуют наиболее трудные вычислительные задачи, мы направ­ляем усилия на определение вариантов тех задач, которые мы можем надеяться решить.

Как показывают эти примеры, сведение — это простая технология, которая полезна при разработке алгоритмов, поэтому мы часто прибегаем к нему. При этом мы либо смо­жем решить новую задачу путем доказательства того, что она сводится к задаче с извест­ным решением, либо мы сможем доказать, что новая задача будет сложной, показав, что задача, о которой известно, что она сложная, сводится к рассматриваемой задаче.

В таблице 21.3 дан более подробный обзор различных последствий применения сведе­ния между четырьмя общими классами задач, которые обсуждались в главе 17. Обратите внимание, что существует несколько случаев, когда сведение не дает новой информации; например, хотя выбор и сводится к сортировке, а задача нахождения наиболее длинных путей в ациклических сетях сводится к задаче нахождения кратчайших путей в общих се­тях, эти утверждения не проливают свет на относительную трудность задачи. В других слу­чаях сведение либо может, либо нет, предоставлять новую информацию; еще в некото­рых случаях последствия сведения действительно глубоки. Чтобы продолжить развитие этих концепций, мы нуждаемся в строгом и формальном описании концепции сведения, о чем мы подробно поговорим в части 8; здесь мы просто неформально подведем итог наиболее важных практических применений сведения вместе с примерами, которые уже были представлены.

Таблица 21.3. Последствия сведения________________________________________

Эта таблица подводит итог некоторых последствий сведения задачи А к другой задаче В, с примерами, которые обсуждались в этом разделе. Глубокие последствия случаев 9 и 10 заходят настолько далеко, что мы в общем случае предполагаем, что нет возможности обосновать такие сведения (см. часть 8). Сведение наиболее полезно в следующих случаях: 1, 6, 11 и 16 - для изучения нового алгоритма для А или обоснования нижней границы для В; 13 - 15 - для изучения новых алгоритмов для А; 12 - для того, чтобы убедиться в сложности В.