非指数的解决迷宫问题？
https://stackoverflow.com/questions/535859
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
给定一个* 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`
解决方案
此问题是NP完全，所以它不知道是否存在是一个多项式时间的解决方案。 （可能易于在实践中的标准附带条件，等，所有适用。）的一种可能的减少是从3SAT。
假设我们有一个3SAT实例，例如（a∨b∨C）∧（¬A∨¬b∨¬c）。我将展示如何使用“小工具”建立你的问题的一个实例。在我们开始之前，改写3SAT问题与A1 = A2，B1 = B2，和C1 = C2（A1∨B1∨C1）∧（∨¬a2∨¬b2¬c2）在一起;即，使可变独特的每次出现，但然后添加条件，不同的出现相同变量的必须相等。
首先，我们确保你必须选择数字0在第一行，这样我们就可以在以后使用它作为一个“定点”，你必须避免的。
0 0 0
现在，我们建立一个能够执行A1 = A2规则的小工具：（此处下划线_在每次使用这个小工具的一个新的唯一编号）
0 _ 0
a1 0 ¬a1
a2 0 ¬a2
由于在第一行的，则必须避免0。这意味着你要么采取的路径“A1，A2”或路径“¬a1，¬a2”;前者将对应于（略容易混淆）设置为false，而后者将对应于一个设置为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++;
}
其他提示
我敢肯定，这可以在多项式时间内完成。我将与顶部开始通过行空集，然后循环至底部。我要跳过任何类型的代码，并显示您的状态是什么样子的每一步，你应该能够从那里拼凑的算法。我确信最好的情况下比使用宽度的变化首先搜索和跟踪当前好的路径的一个表中为O（n ^ 2）稍差。
编辑：如果这还不够快，你可以改善它通过应用的丑角的优化。
例如：
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
您可以尝试蚁群优化。它很快产生，是非常接近完美的解决方案很好的效果。
有关凯文Loney的解决方案的一个优化可能是合并包含在同一列中的相同元件部分路径。你必须要注意与路径合并的数量，如果你想知道在端到端解决方案的数量。
实施例：在你的5×5的例子中，当你在第三行到达，第三列有三个路径以某种顺序导致它含有（1 2 5）。你不必从这个角度分别遵循这些，但可以将它们合并。如果你想知道在端到端解决方案的数量，你只需要调整你的路径的数据结构，例如3（1（1 2 5））将合并至（3（1 2 5））。
查找A *搜索。这是你的朋友。
