4
$\begingroup$

I got an unweighted, undirected graph, with $N$ vertices, where each vertex has degree $K$. In my case its a grid with dynamic obstacles.

My goal is to output a map, based on given location on the grid, with the shortest path to all the cells on the grid, some thing like this:

4 3 2 3
3 2 1 2
4 x x 3
5 6 5 4

The starting position is at node with the weight of 1. X represent the obstacles.

I achieve this goal using Breadth-first-search. My question is how can I reduce the cost of the next search if:
Only my location on the grid is changed, and/or,
if only the location of the obstacles is changes and/or
if both my location and the location of the obstacles is changed.

As for now I perform full recalculation in all those cases.

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ Look at A*, or better yet, incremental A* also known as D*. There are many variants of D* out there as well. (By the way, is your graph really $K$-regular? Your example doesn't look $K$-regular. At first, you say your graph is unweighted, but then you talk about a "node with weight of 1" and your picture seems to support this too. Can you edit accordingly?) $\endgroup$
    – Juho
    Jun 10, 2014 at 12:38
  • $\begingroup$ @Juho my graph is indeed unweighted(May be except obstacles that I do not know how to refer them), the example is the desired output. Aren't D* is more expensive than BFS,O(N)? $\endgroup$
    – Ilya Gazman
    Jun 11, 2014 at 0:03

1 Answer 1

Reset to default
1
$\begingroup$

You have two very different situations in the next search condition. If the graph is set up to represent a grid, then the obstacles are simply removed edges to the vertex where the obstacle is, by moving obstacles you have changed the graph, so any new problem is a search on a new graph and the old results are meaningless. For any two verticies, to see if the new obstacles block the old path is easy, however to see if replacing the edges from the old graph will shorten the path requires you to redo path finding. So in the case of the obstacles changing any algorithm would involve much more work then just redoing the BFS, which is quite simple. As for a changed user position you could sacrifice initial cost and search for all other searches upfront, depending on how many times you want to call the algorithm this may or may not pay off, this case is very situation dependent.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ So what you are basically saying is: "I got no clue"? $\endgroup$
    – Ilya Gazman
    Jun 11, 2014 at 21:57
  • $\begingroup$ No, what I am saying is that for the last two any method of storing results and extrapolating from them would be have a higher time complexity then a breadth first search. If you want to put it bluntly the answer is you cant change a problems parameters and then expect to use the previous results. As for changing the user position there is no method with your previous results that will recalculate the grids values in less then O(|V|) time. $\endgroup$
    – lPlant
    Jun 11, 2014 at 23:56

Your Answer

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

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