Reach end while going through all required points

3
votes

Given a grid of width W and height H containing 5 type of symbols : 

'S' means starting position
'E' means ending position
'C' means checkpoints
'.' means open position and player can pass through it
'#' means closed block that player cant pass through.

The aim of the player is to reach end from start in minimum distance but he need to pass all the checkpoints in the grid .

We need to find this minimum distance.

Some moves allowed to player are :

  1. Player can move only by one step in horizontal or vertical(up,down,left,right) direction.
  2. Diagonal movement is NOT permitted.
  3. Distance is defined as number of movements to the different blocks.
  4. Player can pass opened blocks,checkpoints,start and end points more than once if necessary.
  5. If its not possible to arrive at goal from start then we need to tell that its not possible.

Example :

Let W=5 and H=5 

# # # # #
# . C C #
# S # # #
# . . E #
# # # # #

Then here answer is 9 as path is :

(1,2)=>(1,1)=>(2,1)=>(3,1)=>(2,1)=>(1,1,)=>(1,2)=>(1,3)=>(2,3)=>(3,3)

Now W and H can go up to 100 and maximum number of checkpoints can be at max 18

One of a basic approach can be to use all pair shortest path in here.But As their can be 10000 nodes so complexity of O(N^3) by using alogrithms like Floyd-Warshall Or Dijkstra's will not serve the purpose.

So is their an better approach for this question?

3
algorithm
Do you need the best solution, or just 'good enough'? Have you tried greedy algorithm? – tobias_k
@tobias_k Best solution in what sense.Obviously the path should be minimum of all possible paths.And greedy in what sense.? – code test
Yes, "greedy" can be "wrong" if you need the absolutely best solution. That's why I asked. Also, why would you have to consider all the 10.000 cells in the grid for all-pairs-shortest-path? It seems that finding the shortest paths between all the checkpoints should be enough. – tobias_k
Related question: stackoverflow.com/q/25368709/1639625 – tobias_k
@mbeckish This question has nothing to do with minimum spanning trees. – Sneftel

3 Answers

1
votes

The cost of finding paths between checkpoints is the least of your concerns. For N being the number of checkpoints, that'll grow to O(N*W*H), assuming you just do BFS out from each checkpoint (and the start and end nodes). Once you've got that easy part done, though, you still have to decide on an ordering for the checkpoints. As other commenters have pointed out, this is the travelling salesman problem, and you're not going to make it efficient -- it is unavoidably O(N!). For comparison, if we discard constant factors and use W=H=100, N=18, the cost of the shortest paths is 180000 "time units"... and the cost of finding the best ordering for the checkpoints is 6402373705728000 "time units". That, you may have noticed, is a bigger number.

1
votes

Use pathfinding algorithm like A* to find paths between two points then you have to decompose your problem into following :-

cost(S,E) = cost(S,C1)+cost(C2,C3)..cost(C3,C4)..cost(Ck,E)

There are k! sequence of k checkpoints so your algorithm will be O(k!*N^2) and there cannot be better algorithm as this problem is reduced to TSP.

0
votes

Well I encountered a same sort of problem in the past. I'll tell you the way I did it.

First I used Dijkstra's for finding out distances from S to C1....Ck

Then again for distances from C1....Ck then from C2...Ck and so on .

This will give you the shortest path from each check point to all the others including the start and end.

Now create an adjacency matrix between each of the checkpoints including start and goal.

In the end use travelling salesman to figure out the shortest route through the checkpoints.

If you don't know how to implement TSP then skip the last two steps i.e from Adjacency matrix and use Bruteforce to figure out the shortest path (will take more time ,but eventually does the job).

I hope it helps