algorithm - 迷宫问题的非指数解？

Question

给定一个 n*n 大小的多头无环图，其中每个节点最多有三个 child 和三个 parent ，是否存在非指数算法来确定是否存在 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 设置为真，c 为假，并从第一个子句中选择 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++;
}