загрузка...

АЛГОРИТМЫ - Разработка и применение - 2016 год

Глава 8. NP-полнота и вычислительная неразрешимость

8.6. Задачи о разбиении

В следующих двух разделах рассматриваются две фундаментальные задачи о разбиении, в которых ищутся способы разбиения коллекции объектов на подмножества. Сейчас мы продемонстрируем NР-полноту задачи, которая будет называться задачей о трехмерном сочетании. В следующем разделе будет рассмотрена задача раскраски графа, связанная с разбиением узлов графа.

Задача о трехмерном сочетании

Начнем с обсуждения задачи о трехмерном сочетании, которая может считаться усложненной версией задачи о двудольном паросочетании, которая разбиралась ранее. Задача о двудольном паросочетании может рассматриваться следующим образом: даны два множества X и Y, каждое из которых имеет размер n, и множество Р пар из X х Y. Вопрос: существует ли в Р такое множество из n пар, в котором каждый элемент в X U Y содержится ровно в одной паре? Связь с задачей двудольного паросочетания очевидна: множество Р таких пар просто соответствует ребрам двудольного графа.

Мы уже знаем, как решать задачу двудольного паросочетания за полиномиальное время. Однако ситуация заметно усложняется при переходе от упорядоченных пар к упорядоченным триплетам. Рассмотрим следующую задачу о трехмерном сочетании:

Для заданных непересекающихся множеств X, Y и Z, каждое из которых имеет размер n, и заданного множества T ⊆ X х Y х Z упорядоченных триплетов существует ли в T такое множество из nтриплетов, что каждый элемент X U Y U Z содержится ровно в одном из этих триплетов?

Такой набор триплетов называется идеальным трехмерным сочетанием.

Интересный аспект задачи о трехмерном сочетании, кроме ее связи с двудольным паросочетанием, заключается в том, что она одновременно образует частные случаи как задачи покрытия множества, так и задачи упаковки множества: фактически мы ищем покрытие универсального множества X U Y U Z набором непересекающихся множеств. Конкретнее, задача о трехмерном сочетании является частным случаем задачи покрытия множества, поскольку мы ищем покрытие универсального множества U = X U Y U Z с использованием не более n множеств из заданного набора (триплетов). Аналогичным образом задача о трехмерном сочетании является частным случаем задачи упаковки множества, так как мы ищем n непересекающихся подмножеств универсального множества U = X U Y U Z.

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

Приведенные выше рассуждения легко преобразуются в доказательства того, что Трехмерное сочетаниер Покрытие множества и Трехмерное сочетаниер Упаковка множества. Но это не поможет установить NР-полноту задачи о трехмерном сочетании, потому что эти сведения просто показывают, что задача о трехмерном сочетании может быть сведена к некоторым очень сложным задачам. Нам нужно провести доказательство в обратном направлении: что известная NР-полная задача может быть сведена к задаче о трехмерном сочетании.

(8.20) Задача о трехмерном сочетании является NР-полной.

Доказательство. Как и следовало ожидать, принадлежность задачи о трехмерном сочетании NР доказывается легко. Для заданного набора триплетов T ⊂ X х Y х Z сертификатом, подтверждающим решение, может быть набор триплетов T T. За полиномиальное время можно убедиться в том, что каждый элемент в X U Y U Z принадлежит ровно одному из триплетов в T'.

Для сведения мы снова возвращаемся к задаче 3-SAT. Пожалуй, это выглядит более странно, чем в случае с гамильтоновым циклом, из-за тесной связи задачи о трехмерном сочетании с задачами упаковки множества и покрытия множества; но в действительности закодировать требования к разбиению в любой из этих задач очень трудно. Итак, рассмотрим произвольный экземпляр 3-SAT с n переменными х1, ..., xn и k условиями C1, ..., Ck. Мы покажем, как решить его, если существует возможность обнаружения идеальных трехмерных сочетаний.

Общая стратегия такого сведения очень похожа (на очень высоком уровне) на метод, который использовался в сведении 3-SAT к гамильтоновому циклу. Сначала мы спроектируем регуляторы для кодирования независимых вариантов выбора, задействованных в логическом присваивании каждой переменной; затем будут добавлены регуляторы для кодирования ограничений, наложенных условиями. В этом построении все элементы экземпляра трехмерного сочетания будут изначально называться просто «элементами» без указания того, берутся ли они из X, Y или Z. В конце они естественным образом раскладываются на эти три множества.

Рассмотрим базовый регулятор, связанный с переменной хi. Определим элементы Ai = {аi1, ai2, ..., ai,2k}, образующие ядро регулятора; определим элементы Bi = {bi1, ..., bi,2k} на концах регулятора. Для всех j = 1, 2, ..., 2k определяется триплет tij = (aij, aij+1, bij) с интерпретацией сложения по модулю 2k. Три таких регулятора изображены на рис. 8.9. В регуляторе i триплет tijназывается четным, если j четно, или нечетным, если j нечетно. Аналогичным образом конец bij будет называться четным или нечетным.

Это будут единственные триплеты, содержащие элементы Ai, поэтому мы уже можем что-то сказать о том, как они должны покрываться в любом идеальном сочетании: необходимо использовать либо все четные триплеты в регуляторе i, либо все нечетные триплеты в гаджете i. На этой идее основан наш метод кодирования идеи о том, что хi задается значение 0 или 1; выбор всех четных триплетов представляет назначение хi = 0, а выбор всех нечетных триплетов представляет назначение хi = 1.

Решение о четности/нечетности также может рассматриваться с другой точки зрения — в контексте концов регуляторов. Решив использовать четные триплеты, мы покрываем четные концы регуляторов и оставляем нечетные концы свободными; для нечетных триплетов покрываются четные концы регуляторов, а нечетные концы остаются свободными. Таким образом, решение о присваивании х можно рассматривать следующим образом: свободные нечетные концы соответствуют 0, тогда как свободные четные концы соответствуют 1. Пожалуй, такое представление упростит понимание оставшейся части построения.

Пока что выбор четности/нечетности может приниматься независимо для каждого из n регуляторов переменных. Теперь добавим элементы для моделирования условий и ограничения выбираемых вариантов присваивания. Как и в доказательстве (8.17), рассмотрим пример условия

На языке трехмерных сочетаний это означает: «Сочетание по центрам регуляторов должно оставить свободными четные концы первого регулятора; или оно должно оставить свободными нечетные концы второго регулятора; или оно должно оставить свободными нечетные концы третьего регулятора». Итак, мы добавляем регулятор условия, который делает именно это. Он состоит из множества двух элементов ядра P1 = {p1, p'1} и трех триплетов, их содержащих. Один триплет имеет форму (p1, p'1, b1j) для четного конца b1j; другой включает p1, p'1и нечетный конец b2j'; и третий включает p1, p'1и четный конец b3,j". Только эти три триплета покрывают P1, поэтому мы знаем, что один из них должен использоваться; тем самым точно обеспечивается соблюдение условия.

В общем случае для условия Cj создается регулятор с двумя элементами ядра Pj = {рj, p'j}, а также определяются три триплета, содержащие Pj. Предположим, условие Сj содержит литерал t. Если t = хi, мы определяем триплет (рj, p'j, bi,2j); если то определяется триплет (рj, p'j, bi,2j-1). Только регулятор условия j использует концы bim c m = 2j или m = 2j - 1; таким образом, регуляторы условий никогда не «конкурируют» друг с другом за свободные концы.

Построение почти закончено, но осталась еще одна проблема. Допустим, множество условий имеет выполняющее присваивание. В этом случае для каждого регулятора переменной принимается соответствующий выбор четности/нечетности; для каждого регулятора условия остается как минимум один свободный конец, так что все элементы ядер регуляторов условий также получают покрытие. Проблема в том, что покрытие получили еще не все концы. Мы начали с n ∙ 2k = 2nk концов; триплеты {tij} обеспечили покрытие nk из них, а регуляторы условий — еще k. Остается обеспечить покрытие еще (n - 1)k концов.

Проблема решается очень простым приемом: в конструкцию добавляются (n - 1)k «регуляторов завершения». Регулятор завершения i состоит из двух элементов ядра Qi = {qi, q'i} и триплета (qi, qi, b) для каждого конца b в каждом регуляторе переменной. Это последняя часть построения.

Итак, если множество условий имеет выполняющее присваивание, то в каждом регуляторе переменной делается соответствующий выбор четности/нечетности; как и прежде, при этом остается как минимум один свободный конец для каждого регулятора условия. Использование регуляторов завершения для покрытия всех оставшихся концов гарантирует, что покрытие обеспечено для всех элементов ядер в регуляторах переменных, условий и завершения, а также для всех концов.

И наоборот, предположим, что в построенном экземпляре существует идеальное трехмерное сочетание. Тогда, как упоминалось выше, в каждом регуляторе переменной сочетание выбирает либо все четные {tij}, либо все нечетные {tij}. В первом случае в экземпляре 3-SAT задаются хi = 0, а во втором — хi = 1. Теперь рассмотрим условие Cj; было ли оно выполнено? Так как два элемента ядра в Pj получили покрытие, по крайней мере один из трех регуляторов переменных, соответствующих литералам из Cj, сделал «правильный» выбор решения четности/нечетности, что привело к присваиванию, удовлетворяющему Cj.

Доказательство практически завершено, осталось ответить на последний вопрос: действительно ли мы сконструировали экземпляр трехмерного сочетания? Имеется набор элементов и триплеты, содержащие некоторые из них, но действительно ли эти элементы можно разбить на соответствующие множества X, Y и Z равного размера?

К счастью, ответ на этот вопрос положителен. Мы можем определить X как множество всех aij c четными j, множество всех pj и множество всех qi. Y определяется как множество всех аij с нечетными j, множество всех p'j и множество всех q'j. Наконец, Z определяется как множество всех концов bij. Легко убедиться в том, что каждый триплет содержит по одному элементу из множеств X, Y и Z. ■

Рис. 8.9. Сведение задачи 3-SAT к задаче о трехмерном сочетании





загрузка...

загрузка...