Я думаю, что эта проблема NP-сложная. Я пытаюсь набросать сокращение от MinSAT. В задаче MinSAT нам дают CNF, и наша цель - минимизировать количество удовлетворенных предложений. Эта проблема NP-сложная, см., Например, http://epubs.siam.org/doi/abs/10.1137/S0895480191220836?journalCode=sjdmec
Разделите вершины на две группы - одни будут представлять литералы, другие - клозами, поэтому где v - количество переменных в CNF (обычно обозначается n ), а c - количество предложений. Направьте ребро от каждой литеральной вершины до вершины предложения, где это происходит. Определите S для литеральной вершины, которая представляет x i как { i , i + v + k } (где k - произвольный параметр), поэтому либо f ( x in=2v+cvncSxi{i,i+v+k}k и е ( ˉ х я ) = я + v + K или F ( ˉ х я ) = я и е ( х я ) = я + v + K . Для каждого выражения-вершины пусть S = { v + 1 , … , v + k , 2 v + k + 1 , …f(xi)=if(x¯i)=i+v+kf(x¯i)=if(xi)=i+v+k , так что k вершин-предложений являются `` маленькими ''.S={v+1,…,v+k,2v+k+1,…,n}k
Теперь у CNF есть назначение, где по крайней мере предложений ложны тогда и только тогда, когда ваша проблема может быть решена для вышеупомянутого примера. Задача MinSAT состоит именно в том, чтобы проверить, есть ли в формуле CNF φ присвоение, которое делает как минимум k предложений ложными, поэтому это показывает, что ваша проблема является NP-сложной.kφk
Чтобы помочь вам понять это сокращение, вот интуиция: маленькие метки ( ) соответствуют значению истины False, а большие метки ( v + k + 1 , … , 2 v + k ) соответствуют Правда. Ограничения для буквальных-вершин , чтобы каждый х я является истинным или ложным , и что ¯ х я1,2,…,v+kv+k+1,…,2v+kИксяИкся¯¯¯¯¯имеет противоположное значение истины. Ребра гарантируют, что если любой литерал имеет значение True, то всем вершинам-предложениям, содержащим его, также присваивается значение True. (В отличие от этого, если всем литералам в предложении присваивается значение False, тогда эта структура графа позволяет назначать вершина-предложение False или True.) Наконец, выбор гарантирует, что k вершин-предложений будет присвоено значение False и c - k из них назначены True. Таким образом, если существует верный топологический вид этого графа, то существует присваивание переменным, которое составляет не менее k из пунктов φККс - кКφfalse (все вершины-предложения, которые были назначены False, плюс, возможно, некоторые из тех, которые были назначены True). И наоборот, если есть присваивание переменным, которое делает по крайней мере из пунктов φ ложным, то существует правильный топологический вид этого графа (мы заполняем метки для буквальных вершин очевидным образом; и для Каждое предложение в φ, которое является истинным, мы присваиваем его соответствующей вершине-предложению метку, которая соответствует Истине; другие вершины-предложения могут получать метки, соответствующие произвольному значению истинности).Кφφ
Обратите внимание, что если вы ослабите проблему, позволив быть произвольным (не обязательно биективным), то он становится полиномиальным. Алгоритм работает аналогично топологической сортировке: вы нумеруете вершины одну за другой, сохраняя множество U ненумерованных вершин, чьи соседние элементы были пронумерованы. По возможности вы выбираете вершину x ∈ U и нумеруете ее с наименьшим элементом в S ( x ), который больше, чем номера ее соседей. Нетрудно видеть, что экземпляр ( G , S ) имеет решение, если предыдущий алгоритм работал ( G ,е U x ∈ U S( х ) ( G , S) заканчивается всеми пронумерованными вершинами.( G , S)
источник
Тривиальное наблюдение состоит в том, что если для всех x , то эта задача разрешима за полиномиальное время путем сокращения до 2SAT.| S( х ) | ≤ 2 Икс
Вот как. Введем переменную для каждой вершины x и каждой i такой, что i ∈ S ( x ) . Для каждой пары вершин x , y , если существует путь от x до y , мы получаем некоторые ограничения: если i ∈ S ( x ) , j ∈ S ( y ) и i > j , то мы получаем ограничение ¬ V X , яvх , я Икс я i ∈ S( х ) х , у Икс Y i ∈ S( х ) j ∈ S( у) я > ж . Биективность дает нам другой набор ограничений: для каждой пары x , y вершин с x ≠ y , если i ∈ S ( x ) и i ∈ S ( y ) , мы добавляем ¬ v x , i ∨ ¬ v y , i . Наконец, требование, чтобы каждой вершине была присвоена метка, дает нам еще один набор ограничений: для каждого x , если S¬ vх , яV ¬ vY, j х , у х ≠ у i ∈ S( х ) i ∈ S( у) ¬ vх , яV ¬ vY, я Икс , мы получаем ограничение v x , i ∨ v x , j . (Обратите внимание, что только последний набор ограничений использует обещание, что | S ( x ) | ≤ 2 для каждого x .)S( x ) = { i , j } vх , я∨ vх , J | S( х ) | ≤ 2 Икс
Я понимаю, что это наблюдение не поможет вам в вашей конкретной ситуации. Прости за это.
источник