Задачи упорядочения - NP-полнота и вычислительная неразрешимость

До настоящего момента рассматривались задачи, которые (как, например, задачи о независимом множестве и вершинном покрытии) подразумевали перебор подмножеств набора объектов; также были представлены задачи (как, например, 3-SAT), основанные на поиске комбинаций 0/1 в наборе переменных. Еще один тип вычислительно сложных задач связан с поиском по множеству всех перестановок коллекции объектов.

Задача коммивояжера

Вероятно, самой известной из задач упорядочения является задача коммивояжера. Представьте коммивояжера, который должен посетить n городов v₁, v₂, ..., v_n. Коммивояжер начинает с города v₁, в котором он живет, и хочет найти маршрут — порядок, в котором он посетит все остальные города и вернется домой. Требуется найти маршрут с минимальным суммарным расстоянием всех поездок.

Чтобы формализовать эту задачу, мы воспользуемся предельно обобщенной концепцией расстояния: для каждой упорядоченной пары городов (v_i, v_j) задается неотрицательное число d(v_i, v_j), которое считается расстоянием от v_i до v_j. От расстояний не требуется ни симметричность (может оказаться, что d(v_i, v_j) ≠ d(v_j, v_i)), ни выполнение неравенства треугольника (сумма d(v_i, v_j) и d(v_j, v_k) может быть меньше “прямого” расстояния d(v.,v_k)). Это делается для того, чтобы формулировка задачи была как можно более общей. Дело в том, что задача коммивояжера естественным образом встречается во многих приложениях, которые не имеют отношения к городам и коммивояжерам. Например, формулировка задачи коммивояжера применяется в таких областях, как планирование оптимальных перемещений манипулятора, который должен просверлить отверстия в n точках на поверхности микросхемы; или для обслуживания запросов ввода/вывода к диску; или для упорядочения выполнения n программных модулей для минимизации времени переключения контекста.

Итак, для заданного множества расстояний требуется упорядочить города в маршрут с i₁ = 1, чтобы свести к минимуму общее расстояние Требование i₁ = 1 просто “ориентирует” маршрут так, чтобы он начинался в исходном городе, а слагаемые в сумме просто задают расстояние от текущего города в маршруте до следующего. (Последнее слагаемое в сумме определяет расстояние, необходимое для того, чтобы коммивояжер мог вернуться домой в конце маршрута.)

А вот как выглядит задача коммивояжера в версии с принятием решения:

Для заданного набора расстояний между n городами и границы D существует ли маршрут, длина которого не превышает D?

Задача о гамильтоновом цикле

У задачи коммивояжера имеется естественная аналогия, которая образует одну из фундаментальных задач в теории графов. Для заданного направленного графа G = (V, E) цикл C в графе Gназывается гамильтоновым циклом, если он посещает каждую вершину ровно один раз, — иначе говоря, он “обходит” все вершины без повторений. Например, направленный граф на рис. 8.6 содержит несколько гамильтоновых циклов; в одном из них узлы посещаются в порядке 1, 6, 4, 3, 2, 5, 1, а в другом — в порядке 1, 2, 4, 5, 6, 3, 1.

Рис. 8.6. Направленный граф, содержащий гамильтонов цикл

Задача о гамильтоновом цикле формулируется просто:

Содержит ли заданный направленный граф G гамильтонов цикл?

Доказательство NР-полноты задачи о гамильтоновом цикле

Сейчас мы покажем, что обе задачи являются NP-полными. Для этого сначала будет установлена NP-полнота задачи о гамильтоновом цикле, а затем задача о гамильтоновом цикле будет сведена к задаче о коммивояжере.

(8.17) Задача о гамильтоновом цикле является NP-полной.

Доказательство. Сначала мы покажем, что задача о гамильтоновом цикле принадлежит NP. Для направленного графа G = (V, E) сертификатом, подтверждающим наличие решения, является упорядоченный список вершин гамильтонового цикла. По этому списку можно проверить за полиномиальное время, что каждая вершина входит в список ровно один раз, а каждая последовательная пара соединена ребром; эти проверки установят, что упорядочение определяет гамильтонов цикл.

Рис. 8.7. Сведение задачи 3-SAT к задаче о гамильтоновом цикле; часть 1

Покажем, что 3-SAT ≤_р Гамильтонов цикл. Почему мы выполняем сведение к 3-SAT? Столкнувшись с задачей о гамильтоновом цикле, мы на самом деле понятия не имеем, что выбрать для сведения; задача достаточно сильно отличается от всех задач, которые мы видели до сих пор, так что реальной основы для выбора нет. В такой ситуации одна из возможных стратегий заключается в возврате к 3-SAT, потому что комбинаторная структура этой задачи очень проста. Конечно, эта стратегия гарантирует по крайней мере некоторый уровень сложности при сведении, потому что переменные и условия необходимо будет выразить на языке графов.

Итак, рассмотрим произвольный экземпляр 3-SAT с переменными х₁, ..., x_n и условиями C₁, ..., C_k. Необходимо показать, как решить эту задачу, если имеется возможность обнаружения гамильтоновых циклов в направленных графах. Как обычно, стоит сосредоточиться на важнейших ингредиентах 3-SAT: значения переменных можно задать по своему усмотрению, и для выполнения каждого условия есть три возможности.

Начнем с описания графа, содержащего 2ⁿ разных гамильтоновых циклов, естественно соответствующих возможным 2ⁿ логическим присваиваниям значений переменных. После этого мы добавим узлы для моделирования ограничений, накладываемых условиями.

Мы строим n путей P₁, ..., P_n, где P_i состоит из узлов v_i1, v_i2, ..., v_ib для величины b, которая, как предполагается, немного больше количества условий k; допустим, b = 3k + 3. Существуют ребра из v_ij к v_ij+1 и в обратном направлении, от v_ij+1 к v_ij. Таким образом, обход P_i может осуществляться “слева направо” от v_i1 к v_ib, или “справа налево”, от v_ib к v_i1.

Эти пути связываются следующим образом: для всех i = 1, 2, ..., n - 1 мы определяем ребра из v_i1 в v_i+1,1 и в v_i+1,b. Также определяются ребра из v_ib в v_i+1,1 и v_i+1,b. В граф добавляются два дополнительных узла s и t; мы определяем ребра из s в v₁₁ и v_1b; из v_n1 и v_nb, в t и из t в s.

Построение до настоящего момента изображено на рис. 8.7. Здесь важно задержаться и подумать, как выглядят гамильтоновы циклы на нашем графе. Так как из t выходит только одно ребро, мы знаем, что любой гамильтонов цикл C должен использовать ребро (t, s). После входа в s цикл C может идти по пути P₁ либо слева направо, либо справа налево; какое бы направление ни было выбрано, затем он идет по пути P₂ либо слева направо, либо справа налево; и т. д., вплоть до завершения P_n и входа в t. Другими словами, существуют ровно 2ⁿ разных гамильтоновых циклов, и они соответствуют n независимым выборам направления обхода каждого P_i.

Эта структура естественно моделирует n независимых вариантов присваивания значений переменных x₁, ..., x_n в экземпляре 3-SAT. Следовательно, каждый гамильтонов цикл будет однозначно идентифицироваться следующим логическим присваиванием: если C проходит P_i слева направо, то x_i присваивается 1; в противном случае х. присваивается 0.

Теперь добавим узлы для моделирования условий; экземпляр 3-SAT является выполнимым в том, и только в том случае, если останется хотя бы один гамильтонов цикл. Рассмотрим конкретный пример — условие

C₁ = x₁ V х₂ V х₃.

На языке гамильтоновых циклов это условие означает: “Цикл должен проходить Р₁ слева направо; или он должен проходить Р₂ справа налево; или он должен проходить Р₃ слева направо”. Итак, мы добавляем узел с₁ (рис. 8.8), который делает именно это. (Некоторые ребра не показаны на рисунке для ясности.) Для некоторого значения l узел с₁ имеет ребра из v_1l, v_2,l+1 и v_3l, а также ребра в v_1,l+1, v_2l и v_3,l+1. Следовательно, он легко вставляется в любой гамильтонов цикл, который проходит Р₁ слева направо, для чего узел с₁ посещается между v_1l и v_1,l+1; аналогичным образом с₁ может быть вставлен в любой гамильтонов цикл, проходящий Р₂ справа налево или Р₃ слева направо. Он не может быть вставлен в гамильтонов цикл, который не делает ничего из перечисленного.

На более общем уровне узел с. определяется для каждого условия C_j. В каждом пути Р_i позиции узлов 3j и 3j + 1 резервируются для переменных, участвующих в условии С_j. Предположим, условие С_i содержит литерал t. Если t = х_i, то добавляются ребра (v_i,3j, c_j) и (c_j, v_i,3j+1); если то добавляются ребра (v_i,3j+1, c_j) и (c_j, v_i,3j).

На этом построение графа G завершается. Далее, в соответствии с приведенной выше общей схемой доказательства ЛР-полноты, мы утверждаем, что экземпляр 3-SAT выполним в том, и только в том случае, если G содержит гамильтонов цикл.

Для начала предположим, что для экземпляра 3-SAT существует выполняющее присваивание; тогда мы определяем гамильтонов цикл в соответствии с приведенным выше неформальным планом. Если х. в выполняющем присваивании задается значение 1, то путь Р_i обходится слева направо; в противном случае обход производится справа налево. Для каждого условия C_j, так как оно выполняется вследствие присваивания, будет по крайней мере один путь Р_i, в котором обход будет осуществляться в “правильном” направлении относительно узла с_j, и его можно вставить в маршрут по ребрам, инцидентным v_i,3j и v_i,3j+1.

И наоборот, предположим, что в G существует гамильтонов цикл C. Здесь важно заметить следующее: если C входит в узел с_j по ребру из v_i,3j, то он должен выходить по ребру в v_i,3j+1. В противном случае у v_i,3j+1 останется только один непосещенный сосед, а именно v_i,3j+2, поэтому маршрут не сможет посетить этот узел и сохранить гамильтоново свойство. И симметрично, если маршрут входит из v_i,3j+1, он должен немедленно выйти в v_i,3j. Следовательно, для каждого узла с_j узлы, находящиеся непосредственно до и после с_j в цикле C, соединяются ребром e в G; следовательно, если удалить с_j из цикла и вставить это ребро e для каждого j, мы получим гамильтонов цикл C' для подграфа G - {с₁, ..., с_k}. Это наш исходный подграф, до добавления узлов условий; как упоминалось ранее, любой гамильтонов цикл в этом подграфе должен полностью пройти каждый путь Р_i в том или ином направлении. Соответственно мы используем C' для определения следующего логического присваивания для экземпляра 3-SAT. Если C' проходит Р_i слева направо, то мы задаем х_i = 1; в противном случае задается х_i = 0. Так как больший цикл Cсмог посетить узел каждого условия с_j, по крайней мере один из путей проходился в “правильном” направлении относительно узла с_j, поэтому с определенным нами присваиванием выполняются все условия.

Установлено, что экземпляр 3-SAT выполним в том, и только в том случае, если G содержит гамильтонов цикл; на этом наше доказательство завершается.

Рис. 8.8. Сведение задачи 3-SAT к задаче о гамильтоновом цикле; часть 2

Доказательство NР-полноты задачи коммивояжера

Вооружившись базовым результатом сложности задачи о гамильтоновом цикле, мы можем перейти к демонстрации сложности задачи коммивояжера.

(8.18) Задача коммивояжера является NP-полной.

Доказательство. Легко увидеть, что задача коммивояжера принадлежит NP: сертификат представляет собой перестановку городов, а сертифицирующий алгоритм проверяет, что длина соответствующего маршрута не превышает заданной границы.

Теперь покажем, что Гамильтонов цикл ≤_Р Коммивояжер. Для заданного направленного графа G = (V, E) определяется следующий экземпляр задачи коммивояжера. Каждому узлу v_i графа Gсоответствует город v'_i. Мы определяем d(v'_i, v'_j) равным 1, если в G существует ребро (v_i, v_j), и 2 — в противном случае.

Утверждается, что G содержит гамильтонов цикл в том, и только в том случае, если в экземпляре задачи коммивояжера имеется маршрут длины не более n. Если G содержит гамильтонов цикл, то упорядочение соответствующих городов определяет маршрут длины n. И наоборот, предположим, что существует маршрут длины не более n. Выражение для длины маршрута представляет собой сумму n слагаемых, каждое из которых не менее 1; следовательно, все слагаемые должны быть равны 1. Следовательно, каждая пара узлов G, соответствующих соседним городам маршрута, должна быть соединена ребром; из этого следует, что упорядочение соответствующих узлов должно образовать гамильтонов цикл. ■

Обратите внимание: возможная асимметричность расстояний в задаче коммивояжера (d(v'_i, v'_j) ≠ d(v'_j, v'_i)) сыграла важнейшую роль; так как граф из экземпляра задачи о гамильтоновом цикле является направленным, наше сведение дало экземпляр задачи коммивояжера с асимметричными расстояниями.

Собственно, аналогия задачи о гамильтоновом цикле для ненаправленных графов также является ЖР-полной; хотя здесь доказательство не приводится, оно строится на относительно несложном сведении от задачи для направленного графа. При использовании задачи о гамильтоновом цикле в ненаправленном графе точная аналогия (8.18) может использоваться для доказательства ЖР-полноты задачи коммивояжера с симметричными расстояниями.

Конечно, в самом известном частным случае задачи коммивояжера расстояния определяются множеством из п точек на плоскости. Задачу о гамильтоновом цикле можно свести и к этому частному случаю, хотя сделать это намного сложнее.

Расширения: задача о гамильтоновом пути

Иногда бывает полезно рассмотреть разновидность задачи о гамильтоновом цикле, в которой не обязательно возвращаться к начальной точке. Для заданного направленного графа G = (V, E) путь Р в G называется гамильтоновым путем, если каждая вершине входит в него ровно один раз. (Путь может начинаться с любого узла и заканчиваться на любом узле при условии соблюдения указанного ограничения.) Такой путь состоит из разных узлов v_i1, v_i2, ..., и v_in, в определенном порядке, образующих все множество вершин V; в отличие от гамильтонова цикла, наличие ребра из v_in обратно в v_i1 не обязательно. Задача о гамильтоновом пути формулируется так:

Содержит ли заданный направленный граф G гамильтонов путь?

Используя сложность задача о гамильтоновом цикле, мы покажем следующее.

(8.19) Задача о гамильтоновом пути является ЖР-полной.

Доказательство. Прежде всего задача о гамильтоновом пути принадлежит ЖР: сертификатом может быть путь в G, а сертифицирующий алгоритм проверяет, что он действительно является путем и каждый узел входит в него ровно один раз.

Один из способов демонстрации ХР-полноты задачи о гамильтоновом пути заключается в сведении от 3-SAT, почти идентичного тому, которое мы использовали для задачи о гамильтоновом цикле: мы строим граф, изображенный на рис. 8.7, с тем отличием, что в него не включается ребро из t в s. Если в измененном графе нет ни одного гамильтонова пути, он должен начинаться в s (так как s не имеет входящих ребер) и завершаться в t (так как t не имеет выходящих ребер). Одно изменение позволяет более или менее дословно применить аргумент, использованный в сведении гамильтонова цикла, для обоснования того, что выполняющее присваивание для экземпляра 3-SAT существует в том, и только в том случае, если существует гамильтонов путь.

Альтернативный способ демонстрации ХР-полноты гамильтонова пути основан на доказательстве Гамильтонов цикл ≤_Р Гамильтонов путь. Для заданного экземпляра задачи о гамильтоновом цикле, заданном направленным графом G, строится граф G' по следующим правилам: мы выбираем произвольный узел v в G и заменяем его двумя новыми узлами v' и v''. Все ребра, выходившие из v в G, теперь выходят из v'; а все ребра, входившие в v в G, теперь входят в v''. А точнее, каждое ребро (v, w) в G заменяется ребром (v', w); а каждое ребро (u, v) в Gзаменяется ребром (u, v''). На этом построение G' завершается.

Утверждается, что G' содержит гамильтонов путь в том, и только в том случае, если G содержит гамильтонов цикл. Предположим, что C — гамильтонов цикл в G; рассмотрим обход этого цикла, начиная и заканчивая в узле v. Легко увидеть, что то же упорядочение узлов образует в G' гамильтонов путь, который начинается с v' и завершается в v''. И наоборот, предположим, что Р — гамильтонов путь в G'; очевидно, он должен начинаться в v' (так как v' не содержит входящих ребер) и заканчиваться в v" (так как v" не содержит выходящих ребер). Если заменить v' и v" на v, то это упорядочение узлов образует гамильтонов цикл в G.