迷宫问题的非指数解决方案？

Question

给定一个*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`

Answer 1

这个问题是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++;
}

Answer 2

我很确定这可以在多项式时间内完成.我将从一个空集开始,然后从上到下循环遍历行.我将跳过任何类型的代码,并向您展示状态在每个步骤中应该能够从那里组合算法的样子.我很确定最好的情况比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