Эта проблема NP-полная, и поэтому неизвестно, существует ли решение с полиномиальным временем. (Стандартная оговорка, возможно, простая на практике, и т. Д., все применяются.) Одно возможное сокращение - от 3SAT.
Предположим, что у нас есть экземпляр 3SAT, такой как (a ∨ b ∨ c) ∧ (¬a ∨ ¬b ∨ ¬c). Я покажу, как использовать «гаджеты» для создания экземпляра вашей проблемы. Прежде чем мы начнем, перепишите проблему 3SAT как (a1 ∨ b1 ∨ c1) ∧ (¬a2 ∨ ¬b2 ∨ ¬c2) вместе с a1 = a2, b1 = b2 и c1 = c2; т. е. сделать каждое вхождение переменной уникальной, но затем добавить условие, что разные вхождения одной и той же переменной должны быть равны.
Прежде всего, мы должны убедиться, что вы должны выбрать номер 0 в первой строке, чтобы мы могли использовать его позже как «дозор», которого вы должны избегать.
0 0 0
Теперь мы строим гаджет, который следит за соблюдением правила a1 = a2: (The подчеркивание _ здесь новый уникальный номер, в каждом использовании этого гаджета)
0 _ 0
a1 0 ¬a1
a2 0 ¬a2
Из первой строки , вы должны избегать 0s. Это означает, что вы либо проходите путь «a1, a2», либо путь «¬a1, ¬a2»; первый будет соответствовать (слегка путающе), устанавливая значение a в false, в то время как последнее будет соответствовать настройке a в true. Это связано с тем, что гаджет нашей категории действительно прост, потому что мы просто записываем предложение, например. (Опять _ здесь новую переменную каждый раз):
0 _ 0
a1 b1 b2
или
0 _ 0
¬a1 ¬b1 ¬b2
Наконец, так как вы использовали только одну из a1 и ¬a1 и т.д., мы позволяем вам взять те, которые вы не использовали свободно:
0 _ 0
a1 ¬a1 0
Теперь, это не совсем работает, потому что один из a1 и ¬a1 мог быть использовано в переменном выборе гаджет, в то время как другие могли быть использованы в пункт. Итак, мы включаем новую переменную @i для каждого предложения, которое вы можете взять вместо одной из переменных. Таким образом, если переменная a1 появляется в пункте 1, мы имеем
0 _ 0
a1 ¬a1 @1
Вот полный вывод перевода исходного пункта 3SAT (выделив путь, соответствующий настройке а и Ь истинно, с к ложным, и выбирая из первого предложения), с цифрами слева и с блеском справа.Гаджеты переупорядочиваются (гаджеты первого предложения, затем для каждой переменной, гаджет равенства и затем неиспользуемый гаджет), но это не имеет значения, так как они независимы в любом случае.
0 0 < 0 . . < .
0 8 < 0 . _ < .
2 < 4 6 a1 < b1 c1
0 16 < 0 . _ .
11 13 15 < -a2 -b2 -c2<
0 17 < 0 . _ < .
2 0 3 < a1 . -a1<
10 0 11 < a2 . -a2<
0 18 < 0 . _ < .
2 3 1 < a1 -a1 @1 <
0 19 < 0 . _ .
10 < 11 9 a2 < -a2 @2
0 20 < 0 . _ < .
4 0 5 < b1 . -b1<
12 0 13 < b2 . -b2<
0 21 < 0 . _ < .
4 < 5 1 b1 < -b1 @1
0 22 < 0 . _ < .
12 < 13 9 b2 < -b2 @2
0 23 < 0 . _ < .
6 < 0 7 c1 < . -c1
14 < 0 15 c2 < . -c2
0 24 < 0 . _ < .
6 7 < 1 c1 -c1< @1
0 25 < 0 . _ < .
14 15 9 < c2 -c2 @2 <
(Если вы хотите, все, что нужно быть квадратным, просто включает кучу нулей в конце каждой строки.) Это интересно видеть, что независимо от того, как вы решить эту проблему, в глубине души, вы решая эту проблему 3SAT.
В конце моего поста является поспешно написанная программа на Perl, который генерирует одну из ваших проблем от входа формы
a b c
-a -b -c
Число переменных в полученном экземпляре вашей проблемы является 11C + V + 1. Дайте программе переключатель -r для создания блеска вместо цифр.
# Set useful output defaults
$, = "\t"; $\ = "\n";
# Process readability option and force sentinel
my $r = "0";
if($ARGV[0] =~ /-r/) { shift; $r = "."; }
print $r, $r, $r;
# Clause gadgets
my(%v, %c, $m, $c);
$m = 1;
while(<>) {
my(@v, @m);
$c = $m++;
chomp; @v = split;
for my $v (@v) {
push @{$v{strip($v)}}, -1; # hack, argh!
push @m, ($r ? [email protected]{$v{strip($v)}} : $m + neg($v));
$c{($r ? (strip($v)[email protected]{$v{strip($v)}}) : $m)} = $c;
$v{strip($v)}->[-1] = ($r ? (strip($v)[email protected]{$v{strip($v)}}) : $m);
$m += 2 unless $r;
}
print $r, newv(), $r;
print @m;
}
# Variable gadget
for my $v (sort keys %v) {
# Force equal
print $r, newv(), $r;
for my $n (@{$v{$v}}) {
print $n, $r, ($r ? "-".$n : $n+1);
}
# Unused
for my $n (@{$v{$v}}) {
print $r, newv(), $r;
print $n, ($r ? "-".$n : $n+1), ($r ? "\@".$c{$n} : $c{$n});
}
}
# Strip leading -
sub strip {
my($v) = @_;
return substr $v, neg($v);
}
# Is this variable negative?
sub neg {
my($v) = @_;
return "-" eq substr($v, 0, 1);
}
# New, unused variable
sub newv {
return "_" if $r;
return $m++;
}
следует ли это помечать как домашнюю работу? –
Это не то, что я прошу «код, kthxbye». В рамках более масштабного программирования я столкнулся с проблемой, и мне интересно, выполнил ли я наилучшую работу, или если я буду придерживаться головы в CLRS и Knuth в течение еще нескольких часов и посмотреть, «Что-то не хватает. –
Кроме того, формулировка - все мое. Нам было дано наивное описание, которое я обобщил во втором абзаце. –