views:

797

answers:

5

Given a n*n-sized multi-headed acyclic graph where each node has at most three children and three parents, is there an non-exponential algorithm to identify whether a n-length path exists where no two nodes share the same value, and every value of a set is accounted for?

Basically, I have an n*n maze where each space has a random value (1..n). I need to find a path (from the top to the bottom) of n nodes that includes every value.

Right now I'm using a depth-first search, but that is T(n) = 3T(n-1) + O(1), which is O(3^n), a non-ideal solution.

Either confirming my fears, or pointing me in the right direction would be much appreciated.

Edit: to make this a little bit more concrete, here is a maze with solutions (solved using the depth-first solution).

 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`
+4  A: 

I'm pretty sure this can be done in polynomial time. I would start with a an empty set and then loop through the rows top to bottom. I'm going to skip any kind of code and show you what the state would look like at each step you should be able to put together an algorithm from there. I'm pretty sure the best case is slightly worse than O(n^2) using a variation of breadth first search and keeping track of the current good paths in a table.

EDIT: If this still isn't fast enough you can improve it by applying Harlequin's optimization.

For Example:

1 2 3
3 2 1
1 2 1

State 0: R = 0 // Row P = {} // Path Set

// {{Path so far}, Column}

P' = {
 {{1}, 0}
 {{2}, 1}
 {{3}, 2}
}

P = P'

State 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}
}

State 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}
}

Result:
Path Count: 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

Kevin Loney
+1, assuming it is actually a tree. If it is actully a mutli-headed acyclic graph, or better still a proper maze with cycles and all it becomes more interesting. I wonder if the question is stated correctly?
Shane MacLaughlin
Cycles aren't the issue, it's the vast number of possible paths. Added some data, because I may have misworded the question.
Mike Douglas
@Kevin, whether I work from a head or a leaf, don't I still have T(n) = 3T(n-1) performance?
Mike Douglas
@Mike I was assuming you were working with a maze with walls which is obviously incorrect.
Kevin Loney
I described a possible optimization below: http://stackoverflow.com/questions/535859/non-exponential-solution-to-maze-problem/536189#536189
Svante
@Kevin Loney: Your algorithm runs in worst-case exponential time (indeed, there are exponentially many path sets). See my post.
A. Rex
Note that this isn't polynomial, but rather exponential. However, it has significant pruning, so I think the running time should be reasonable.
FryGuy
A: 

Look up A* search. It is your friend.

chaos
A* is for shortest path I think. He needs a path that visits all nodes from 1 to n only once.
Staale
Considering the distance is fixed, and the weighting changes (from 0 to inf) based on previously visited nodes, A* would be really hard to apply.
Mike Douglas
+2  A: 

You can try the ant colony optimization. It quickly yields very good results that are very close to the perfect solution.

Aaron Digulla
+1  A: 

One optimization for Kevin Loney's solution might be to merge partial paths that contain the same elements at the same column. You would have to note the number of merges with the path if you want to know the number of solutions at the end.

Example: In your 5x5 example, when you arrive at the third row, the third column has three paths leading to it that contain (1 2 5) in some order. You don't have to follow these separately from this point, but can merge them. If you want to know the number of solutions at the end, you just have to adjust your path data structure, e.g. three (1 (1 2 5)) would merge to (3 (1 2 5)).

Svante
+8  A: 

This problem is NP-complete, and so it is not known whether or not there is a polynomial-time solution. (The standard provisos of possibly being easy in practice, etc., all apply.) One possible reduction is from 3SAT.

Suppose we have a 3SAT instance, such as (a ∨ b ∨ c) ∧ (¬a ∨ ¬b ∨ ¬c). I will show how to use "gadgets" to build an instance of your problem. Before we begin, rewrite the 3SAT problem as (a1 ∨ b1 ∨ c1) ∧ (¬a2 ∨ ¬b2 ∨ ¬c2) together with a1 = a2, b1 = b2, and c1 = c2; that is, make each occurrence of a variable unique, but then add the condition that different occurrences of the same variable must be equal.

First, we make sure that you must pick the number 0 in the first row, so that we can use it later as a "sentinel" that you must avoid.

 0   0   0

Now, we build a gadget that enforces the a1 = a2 rule: (The underscore _ here is a new unique number in every use of this gadget)

 0   _   0 
 a1  0  ¬a1
 a2  0  ¬a2

Because of the first row, you must avoid the 0s. This means you either take the path "a1, a2" or the path "¬a1, ¬a2"; the former will correspond to (slightly confusingly) setting a to false, while the latter will correspond to a setting a to true. This is because our clause gadget is really easy then, because we simply write down the clause, e.g. (again _ here is a new variable each time):

 0   _   0 
 a1  b1  b2

or

 0   _   0 
¬a1 ¬b1 ¬b2

Finally, since you've only used one of a1 and ¬a1, etc., we let you take the ones you haven't used freely:

 0   _   0 
 a1 ¬a1  0

Now, this doesn't quite work, because one of a1 and ¬a1 might have been used in the variable choice gadget, while the other could have been used in a clause. So, we include a new variable @i for each clause that you can take instead of one of the variables. So if variable a1 appears in clause 1, we have

 0   _   0 
 a1 ¬a1  @1

Here's the complete output of a translation of the original 3SAT clause (highlighting the path corresponding to setting a and b to true, c to false, and picking a from the first clause), with numbers on the left and gloss on the right. The gadgets are re-ordered (first clause gadgets, then for each variable, the equality gadget and then unused gadget), but this doesn't matter since they're independent anyway.

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 <

(If you want the whole thing to be square, just include a bunch of zeros at the end of each line.) It's fun to see that no matter how you solve this, at heart, you're solving that 3SAT problem.

At the end of my post is a hastily-written Perl program that generates one of your problems from an input of the form

a b c
-a -b -c

The number of variables in the resulting instance of your problem is 11C + V + 1. Give the program the -r switch to produce gloss instead of numbers.

# 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++;
}
A. Rex
That is really complicated, and I'm not sure how it maps to the original problem statement.
FryGuy
@FryGuy: The original question was whether or not there was a sub-exponential solution to a "maze" problem. If there was, then it would translate into one for 3SAT by the reduction above. Since this is currently an open problem, this would be a big breakthrough. Are you uncomfortable with proofs?
A. Rex
I'm comfortable with proofs, I just made a mistake in reading it and thinking you had wierd notation. I thought that you were going to solve Maze-Problem using an instance of 3-SAT, rather than solving 3-SAT using Maze-Problem. The second paragraph could be clearer.
FryGuy