给定一个*n大小的多头非循环图,其中每个节点最多有三个子节点和三个父节点,是否存在非指数算法来识别是否存在n长度路径,其中没有两个节点共享相同的值,并且每个节点都存在一组的价值是多少？
基本上,我有一个n*n迷宫,其中每个空格都有一个随机值(1..n).我需要找到包含每个值的n个节点的路径(从顶部到底部).
现在我正在使用深度优先搜索,但这T(n) = 3T(n-1) + O(1)是O(3^n)一个非理想的解决方案.
要么确认我的恐惧,要么指出我正确的方向将非常感激.
编辑:为了使这更具体,这里是一个解决方案的迷宫(使用深度优先解决方案解决).
1 2 5 5 4 1 5 1 3 5 4 1 2 3 2 5 5 4 4 3 4 2 1 2 4 S3, 5, 1, 3, 4, 2, F4 S3, 5, 1, 3, 4, 2, F2 S3, 5, 1, 3, 4, 2, F4 S3, 5, 3, 2, 4, 1, F3 S3, 5, 3, 2, 4, 1, F3 S3, 5, 3, 2, 4, 1, F3 S4, 5, 3, 2, 4, 1, F3 S4, 5, 3, 2, 4, 1, F3 S4, 5, 3, 2, 4, 1, F3 S4, 5, 1, 3, 4, 2, F4 S4, 5, 1, 3, 4, 2, F2 S4, 5, 1, 3, 4, 2, F4 S5, 4, 3, 2, 5, 1, F3 13 total paths`
A. Rex.. 11
这个问题是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规则的小工具:( _这里的下划线是每次使用此小工具时的新唯一编号)
0 _ 0 a1 0 ¬a1 a2 0 ¬a2
由于第一行,您必须避免使用0.这意味着你要么采取路径"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子句的翻译的完整输出(突出显示对应于将a和b设置为true,c设置为false,并从第一个子句中选择a的路径),左侧是数字,右侧是光泽.小工具被重新排序(第一个子句小工具,然后是每个变量,相等的小工具,然后是未使用的小工具),但这无关紧要,因为它们无论如何都是独立的.
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 ? $v.@{$v{strip($v)}} : $m + neg($v));
$c{($r ? (strip($v).@{$v{strip($v)}}) : $m)} = $c;
$v{strip($v)}->[-1] = ($r ? (strip($v).@{$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++;
}
@FryGuy:最初的问题是,是否存在"迷宫"问题的亚指数解决方案.如果有,那么通过上面的减少它将转化为3SAT的一个.由于这是一个开放的问题,这将是一个重大突破.您对样张不舒服吗？ (2认同)
我对证据感到满意,我只是在阅读它时犯了一个错误,并认为你有一些奇怪的符号.我认为你将使用3-SAT的实例解决Maze-Problem,而不是使用Maze-Problem解决3-SAT问题.第二段可以更清楚. (2认同)
Kevin Loney.. 5
我很确定这可以在多项式时间内完成.我将从一个空集开始,然后从上到下循环遍历行.我将跳过任何类型的代码,并向您展示状态在每个步骤中应该能够从那里组合算法的样子.我很确定最好的情况比O(n ^ 2)略差,使用广度优先搜索的变化并跟踪表中当前的好路径.
编辑:如果这还不够快,你可以通过应用Harlequin的优化来改进它.
例如:
1 2 3
3 2 1
1 2 1
状态0:R = 0 //行P = {} //路径集
// {{Path so far}, Column}
P' = {
{{1}, 0}
{{2}, 1}
{{3}, 2}
}
P = P'
状态1:R = 1 // ROW P = {{{1},0} {{2},1} {{3},2}}
P' = {
{{1 3}, 0}
{{1 2}, 1}
{{2 3}, 0}
{{2 1}, 2}
{{3 2}, 1}
{{3 1}, 2}
}
州2:R = 2 P = {{{1 3},0} {{1 2},1} {{2 3},0} {{2 1},2} {{3 2},1} { {3 1},2}}
P' = {
{{1 3 2}, 1}
{{2 3 1}, 0}
{{3 2 1}, 0}
{{3 2 1}, 2}
{{3 1 2}, 1}
}
结果:
路径计数:5
S1 1 3 2 F2
S2 2 3 1 F1
S3 3 2 1 F1
S3 3 2 1 F3
S3 3 1 2 F2
这个问题是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规则的小工具:( _这里的下划线是每次使用此小工具时的新唯一编号)
0 _ 0 a1 0 ¬a1 a2 0 ¬a2
由于第一行,您必须避免使用0.这意味着你要么采取路径"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子句的翻译的完整输出(突出显示对应于将a和b设置为true,c设置为false,并从第一个子句中选择a的路径),左侧是数字,右侧是光泽.小工具被重新排序(第一个子句小工具,然后是每个变量,相等的小工具,然后是未使用的小工具),但这无关紧要,因为它们无论如何都是独立的.
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 ? $v.@{$v{strip($v)}} : $m + neg($v));
$c{($r ? (strip($v).@{$v{strip($v)}}) : $m)} = $c;
$v{strip($v)}->[-1] = ($r ? (strip($v).@{$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++;
}
我很确定这可以在多项式时间内完成.我将从一个空集开始,然后从上到下循环遍历行.我将跳过任何类型的代码,并向您展示状态在每个步骤中应该能够从那里组合算法的样子.我很确定最好的情况比O(n ^ 2)略差,使用广度优先搜索的变化并跟踪表中当前的好路径.
编辑:如果这还不够快,你可以通过应用Harlequin的优化来改进它.
例如:
1 2 3
3 2 1
1 2 1
状态0:R = 0 //行P = {} //路径集
// {{Path so far}, Column}
P' = {
{{1}, 0}
{{2}, 1}
{{3}, 2}
}
P = P'
状态1:R = 1 // ROW P = {{{1},0} {{2},1} {{3},2}}
P' = {
{{1 3}, 0}
{{1 2}, 1}
{{2 3}, 0}
{{2 1}, 2}
{{3 2}, 1}
{{3 1}, 2}
}
州2:R = 2 P = {{{1 3},0} {{1 2},1} {{2 3},0} {{2 1},2} {{3 2},1} { {3 1},2}}
P' = {
{{1 3 2}, 1}
{{2 3 1}, 0}
{{3 2 1}, 0}
{{3 2 1}, 2}
{{3 1 2}, 1}
}
结果:
路径计数:5
S1 1 3 2 F2
S2 2 3 1 F1
S3 3 2 1 F1
S3 3 2 1 F3
S3 3 1 2 F2
京公网安备 11010802040832号 | 京ICP备19059560号-6 