8
$\begingroup$

So, suppose i have a maze, which has a start point and an end point, marked with Orange and red respectively and my goal is to find the minimum distance between them. The blocked path is represented by black colour and the open path is represented by white colour . However there are two modification done in this.

  1. There are some cells which are must visit, marked in grey colour.
  2. Any cell can be visited any number of times(even the start, finish and must visit points)

    for ex-
      █=Black, ░=white, G=grey, R=Red, O=orange
    
             ██████                 █████
             ██G███                 █░GG█
    MAZE1 => █O░GR█     MAZE2  =>   █O███
             ██G███                 █░░R█
             ██████                 █████
    

Here in this case ans will be

MAZE1 => M[2][1] => [2][2] => [1][2] => [2][2] => [3][2] => [2][2] => [2][3] => [2][4]  = 7
MAZE2 => M[1][1] => [1][2] => [2][2] => [3][2] => [3][3] => [3][2] => [2][2]            = 6

As you can see, the nodes appear multiple times

First i thought of using recursion technique (backtracking) but couldn't come to an algorithm. and

So i thought of using this way.

  1. I will keep track of all the coordinates of must visit points, start and end points
  2. Find the distance between each node(like in selection sort we compare each and every term, just like that, we get the minimum distance between each node (using BFS))
  3. Then apply some minimum distance algorithm. I thought of TSP but it says nodes must be visited exactly once.Here it can be multiple times. I found chinese postman problem, but don't know if it can be applied here. Floyd warshall algorithm is there but it doesn't include every point

How should i proceed, any idea?

$\endgroup$
3
  • $\begingroup$ Is there any restriction on the structure of the maze? For example, must the possible paths through it form a tree, rather than a general graph? That may or may not affect the complexity of the problem but it would certainly be good to clarify. $\endgroup$ Commented Aug 22, 2014 at 9:21
  • $\begingroup$ Do you have more details on the maze structure. Depending on what it looks like, you can have many optimizations. For example, consider the maze routing is "perfect". In that case, the graph for your maze is a tree, which means you can heuristically simplify your graph to speed up navigation. $\endgroup$ Commented Aug 22, 2014 at 15:41
  • 1
    $\begingroup$ This smells NP-hard to me. How large are the parameters? About how many grey nodes do you have? how many white nodes? This might impact what kinds of algorithms will work well. $\endgroup$
    – D.W.
    Commented Aug 22, 2014 at 16:20

1 Answer 1

8
$\begingroup$

Most real mazes are trees and there is a polynomial time algorithm for this problem on trees. For ease of description, orient all edges of the tree to point away from the start vertex. Now, for each vertex, delete any child if the subtree rooted at that child contains no vertices that must be visited (i.e., contains no grey or red vertices). The result is a tree where every leaf is grey or red (there may be grey and red vertices in the interior of the tree, too). Now perform a depth-first traversal of the tree, investigating the children of each node in arbitrary order, except that, if one of the children is on the path from the start to the red (end) node, that child is investigated last. If the red node was a leaf, you are done; if not, take the unique path from the leaf you finished at to the red node. The total distance is twice the number of edges in the reduced tree, minus the number of edges on the shortest path from the start to the red vertex.

For general graphs, the problem is NP-hard. Consider the special case where the "maze" actually has no black squares. What we have is, essentially, a so-called rectlinear TSP, where the start, end and grey squares are the "cities". Rectilinear TSP is metric TSP using the Manhattan distance as the metric. The input is a set of points with 2D integer co-ordinates. Observe that metric TSP doesn't care whether you revisit cities or not because it obeys the triangle inequality: if the shortest route from A to B is via C, and the salesman has already visited C, he'll just drive straight past; in the maze world, we don't care whether he stops or not, since he's allowed to stop in a city as many times as he wants. Rectilinear TSP is NP-hard: see Garey, Graham and Johnson, Some NP-Complete Problems (Proc. 8th STOC, pp. 10–22, 1976; ACM DL).

To prove NP-hardness of the maze problem, we need to demonstrate a reduction from rectilinear TSP. This isn't quite trivial because the maze problem has specified and distinct start and end squares but I'm reducing from rectilinear TSP, in which the salesman starts at any city he chooses and returns to that city at the end. But observe that it doesn't matter what the start city is, since the tours ABCDA and CDABC have exactly the same length: forcing the tour to start at a particular city doesn't actually change the answer. So, if I'm allowed to cheat once more and put the red and orange squares in the same place, I'll do that. But you probably mean that squares have a unique colour, so here's the full reduction:

Take the northern-most of the cities and make it be the start square (if there are multiple cities equally far north, choose any one of them. Make every other city a grey square. Place the end square one square to the north of the start square and colour black the squares north, east and west of the end square. Make every other square white.

Because of the black walls, any route from the start square to the end square must revisit the start square immediately before going to the end. The end square and its black walls are outside the convex hull of the original cities, so no optimal tour of the original cities would have gone through those squares. Therefore, a shortest route from the start square to the end square consists of a solution to the rectilinear TSP problem (a shortest tour from the start city, through all the other cities and back to the start city), followed by the one-square move from the start square to the end square. This completes the reduction.

$\endgroup$
3
  • $\begingroup$ I agree that you are right when marking the start city at the right place, using the topological characteristic of rectilinear TSP. I don't think I agree with the second city's last course of moving though. I had to spent lot of effort to get there and I had no source of references. Nevertheless, just for formality, the certificate when showing the problem is at least in NP is still trivia and valid? I know researching the route is above what is readily seen, however is the other part easy enough? $\endgroup$
    – InformedA
    Commented Aug 29, 2014 at 6:39
  • $\begingroup$ @randomA I don't understand what you're saying about the second city: I don't mention the second city anywhere. I believe my reduction is correct. The problem isn't in NP, since NP is a class of decision problems and this is an optimization problem. Sure, I could give you what I claim is the optimal route and you can check in polytime that it has the length I claim it does but how would you check it was optimal? The decision version (is there a route with length at most $k$?) is clearly in NP: the certificate is the route. $\endgroup$ Commented Aug 29, 2014 at 8:13
  • $\begingroup$ I was asking for the the decision problem. But thanks $\endgroup$
    – InformedA
    Commented Aug 29, 2014 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.