wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Escape
        
(Message started by: william wu on Apr 27^th, 2003, 3:53am)

Title: Escape
Post by william wu on Apr 27^th, 2003, 3:53am

ESCAPE

You are given an n x n grid, and m starting points on that grid, where m <= n². All points on the grid have exactly four neighbors, except for the boundary vertices.

Design an "efficient" algorithm that determines whether there exist m disjoint paths from the starting points to any m different points on the grid boundary. For example, figure (a) below has an escape shown by the bright green paths, but figure (b) does not.

http://www.ocf.berkeley.edu/~wwu/images/riddles/escape_grids.png

(Quick and dirty summary of the problem: Imagine creatures at the starting points, each wanting to escape from the grid by taking routes which do not intersect. Determine if such a set of routes exists.)

Note: Adapted from an exercise problem in Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein.

Title: Re: Escape
Post by DH on Aug 28^th, 2003, 8:17am

Is maximum flow "efficient" enough ?

Title: Re: Escape
Post by James Fingas on Aug 28^th, 2003, 8:59am

If m > 4n-4, then there's no escape!

Title: Re: Escape
Post by DH on Aug 28^th, 2003, 9:09am

Actually when all the points are on the border ( 4n-4 points ) there is escape, but I agree there is an upper limit for m.

Title: Re: Escape
Post by John_Gaughan on Dec 12^th, 2003, 7:45pm

While not part of the original problem, this might help.

[hide]Clearly m >= 4n-4 since if all the points are on the border they can escape. Counting the largest possible m for n the old fashioned way:

n=1, m=1
n=2, m=4
n=3, m=8
n=4, m=12
n=5, m=16
n=6, m=20

I figure that {m = 4n - 4, m>1}
If you fill in all the borders every point can escape. No matter how I rearrange the points, I am never able to add one.

Now for the minimum number of points where escape is guaranteed (i.e. if you add one more point, you can find a counterexample).

n=1, m=1
n=2, m=4
n=3, m=4
n=4, m=4
n=5, m=4
n=5+k (k>0), m=5

Reasoning: imagine a subgraph where n=3. Arrange five points in a plus shape. The point in the center has no escape. Now remove any point from the graph. The other points obviously can escape.

So I have {m=n, n=1; 4 <= m <= 4n-4, n>1} Hopefully this is on the right track... I really want to solve this![/hide]

Title: Re: Escape
Post by James Fingas on Dec 18^th, 2003, 4:45am

I would conjecture that this problem is NP-hard, but I am not good at that sort of thing. However, I have come up with a method to figure out as much as possible before resorting to a brute-force search. Here is my method:

Basic idea: breadth-first fill from the outside in. This constructs the most optimal paths to the easiest starting points. However, the existance of starting vertices near the boundary leads to uncertainty in how to approach starting vertices not near the boundary. Paths from the boundary are extended by one edge at a time. Most often, a path will be able to go only one direction, in which case paths don't join. If a path has a choice about which direction to go, however, it takes both directions at once. In this case, paths are allowed to join.

Implementation:
maintain a queue Q for the breadth-first search. The queue will contain the (x,y) positions of the current ends-of-path. The queue shall be initialized with 4n-8 elements: those boundary vertices that are not corners.

maintain an nxn state array for all vertices. It will store the following values:

paths (2 bits)
xxxxx00 - no path exists to this vertex
xxxxx01 - a path fully passes through this vertex
xxxxx10 - a path partially passes through this vertex

starting vertices (1 bit)
xxxx0xx - this vertex is not a starting vertex
xxxx1xx - this vertex is a starting vertex

side connectivity (4 bits)
xxx1xxx - this vertex is approached from the west
xx1xxxx - this vertex is approached from the north
x1xxxxx - this vertex is approached from the east
1xxxxxx - this vertex is approached from the south

vertices that are seeded into the queue will be initialized so that they will be initialized to ????x01, where one of the ? bits will be set, to keep the path from going out of the nxn grid.

When a vertex location is popped from the front of the queue, you first must check to see which directions you can go in. You will have come from one direction, ruling that one out. There may be xxxxx01 in some direction, meaning you cannot go there. Count up the number of directions in which this path can go. If it is zero, do nothing. If it is one, write ????x01 to the vertex in the direction the path can go, and if that vertex is xxxx0xx then push it onto the back of the queue.

However, if the number of directions is more than one, then write ????x10 to all the vertices the path can go to. For each vertex that is xxxx0xx, push that vertex onto the back of the queue.

There are some border cases that I don't want to get in to, but below I have shown how it works for the simple grid you see at the top of the thread. Darn it all--it contains one of the border cases! Okay, the border cases are the following:

1) If the current vertex is xxxxx01, and the path can go in only one direction: into a vertex of xxxxx10, then you overwrite that vertex. But then you have to go back one step along the path that you just overwrote, to see if it becomes an xxxxx01 path or not. If so, you must immediately redo that path.

2) There must be more border cases ... I would really like to restrict the joining of the xxxxx10 paths more, but I can't see a valid way to do so.

I'm thinking that we should first do all the xxxxx01 paths, quitting when we get to a decision, and then do all the xxxxx10 paths, one at a time, from each ending point where there was a decision. This would eliminate the border cases I've mentioned. Then you could just combine all the individual answers to get a cumulative answer. We'd call the xxxxx01 round the "deterministic round", and the various xxxxx10 rounds "quantum rounds" (just for fun). The deterministic round is over when no more deterministic decisions can be made. That is to say, if you can't make a decision about one node, push it onto the queue again. Only when you've gone through the entire queue and still can't make any decisions do you give up.

Therefore, the simple case William gives is solved in the deterministic round, but the second one I show has a couple quantum rounds (shown). The problem is that the final state, although it's all we can show for sure using this method, is fundamentally no better than any initial state (that's why I think this problem is in NP-hard).

Title: Re: Escape
Post by towr on Dec 18^th, 2003, 7:48am

where you say 'end of quatum round 1' in the image, you can allocate the corresponding exit point with that starting point, since you can't reach any of the others.. You can do that in polynomial time (worst case O(n²)).
And since there's than only one starting point left, you can allocate it one of the remaining exit points easily enough in polynomial time as well..

Title: Re: Escape
Post by James Fingas on Dec 18^th, 2003, 8:33am

Yes, very true. I'm sure that there are a number of simplifications like that that can be made in the quantum rounds. These simplifications are not generally applicable, (but then again, neither is my boundary BFS method!), and I think that some of them (including the one you mention) are not guaranteed to preserve the answer if an answer exists. I'll try to come up with a counter-example.

The hard part is probably not in finding out which exit point the starting points go to, (although there could theoretically be a superpolynomial number of combinations), but in finding the appropriate path to those exits that doesn't block anybody else's exit.

I would like to design a good greedy algorithm to solve the problem most of the time. A greedy way to pick paths might be to pick a starting point and generate a straightforward escape path (BFS would be good), then try to generate all the other escape paths one at a time. If that doesn't work, delete some of them (which ones?) and then generate some more.

Or perhaps we could generate the escape paths individually, then sum them to see which vertices are the most contested, then generate the paths which would like to go through those vertices first.

Title: Re: Escape
Post by towr on Dec 18^th, 2003, 9:31am

Maybe a twosided approach would be best, not just go from the exit points to the starting points, but also going the other way.
For example
When a starting point is surrounded on all sides by others you allready know there isn't any solution.
When it's surrounded on three sides you know that it has to be connected via the 4th (open) side, which means you can drop another node from the graph (if you were to use a graph to represent the grid. I've approached it as repeatedly cutting parts from a graph).

Title: Re: Escape
Post by James Fingas on Dec 18^th, 2003, 12:56pm

That's the way I initially thought about the problem. It could have some merit, but I think you can usually tell a lot more when you start from the boundary. But it's a good suggestion. Maybe we could add that as a second "deterministic round". All the starting points that haven't been connected up after the first deterministic round are the starting points for another deterministic round, with almost exactly the same rules as before.

Title: Re: Escape
Post by towr on Dec 19^th, 2003, 1:34am

I've thought up another necessary condition for there to be a solution.. We allready know there can be at most 4n-4 starting points in the whole grid, but the same goes for any k*k subgrid, there can only be 4k-4 startingpoints in that as well. Obvious enough of course..
Perhaps after the deterministic rounds it'd be more helpfull to check if there are more potential exitpoints than starting points in every subgrid, because there are bound to be dead ends.
And it might be worthwhile to detect areas that are surrounded by starting points, because that means those starting points have to be reached from the outside, and you can probably propagate them outwards.
There's also a few interesting patterns, f.i. when you have doubles line of starting points:


*****         *          * * 
*****  and   ***  and   *****
            ** **       * * *
            *   *

these are equivalent to
*
* *
* *
* *
* *
*
(so if there's another startingpoint in the area that the expanded pattern would occupy it's not solvable)

Title: Re: Escape
Post by DH on Jan 16^th, 2004, 7:44am

I think I should expand on my initial post. Maybe you can tell me what's my error.

Construct the following flow network:
Add a source node and from that node construct oriented edges with maximum capacity 1 to all starting points.
Add a destination node and construct oriented edges with maximum capacity 1 from all border points to the destination node.

Transform all nodes from the grid as shown in the picture.The maximum capacity for each edge is 1.

Compute the maximum flow for the network. If the maximum flow is equal to m then a solution exists.