Both A* and Dijkstra will visit 2^64 nodes if you let them search a path from (INT_MIN,INT_MIN) to (INT_MAX,INT_MAX) on an empty grid. 2^64 is huge...
My proposed algorithms both need only 1 step. And compute the exact answer, at least for an empty grid i am sure of it.
Robots on a 2D grid with obstacles to a target... is Dijkstra the best solution?
Quote:Original post by DrEvil
On an empty grid A* will shoot straight to the goal.
Depends on how you implement it. If you are using a depth-first traversal with taxicab it's true, but it then needs to store all intermediate steps in it's queue. Which is around 32 GBytes of data for (min,min) to (max,max).
If you use breadth-first traversal you fill a bounding box of start and end and need only 16 GByte of data.
DFS is around 2^33 steps which still takes ages, if one step was 1 CPU-cycle it is several seconds. In reality it's at least 100 times slower.
As we are looking for the shortest path with the least number of turns shooting straight to the target doesn't help as you would need all shortest paths to decide which one has the least number of turns.
If you encode the turnnumber in you metric, like (distance<<32+turns) you will find the right path directly, but still need 32 GByte of data...
If you encode the turnnumber in you metric, like (distance<<32+turns) you will find the right path directly, but still need 32 GByte of data...
Quote:Original post by TrapQuote:Original post by DrEvil
On an empty grid A* will shoot straight to the goal.
Depends on how you implement it. If you are using a depth-first traversal with taxicab it's true, but it then needs to store all intermediate steps in it's queue. Which is around 32 GBytes of data for (min,min) to (max,max).
If you use breadth-first traversol you fill a bounding box of start and end and need only 16 GByte of data.
DFS is around 2^33 steps which still takes ages, if one step was 1 CPU-cycle it is several seconds. In reality it's at least 100 times slower.
If you used BFS or DFS then it wouldn't be A*. A* is a blend of best first and Dijkstra. A*, IMPLEMENTED PROPERLY, will go straight for the goal in an empty grid. Don't know why you are even bringing up int min - int max searches, it has nothing to do with anything. Your solution couldn't handle that kind of memory either. Even the OP's example numbers were not even close to to numbers that large, well under even a signed short. It's still a large grid yes, and it will still not be a cheap search. I'd venture to guess that he probably doesnt need that kind of density in the graph anyways, and should probably use fewer nodes by increasing the size of the nodes, but even with that size of a graph, with simple rectangular obstacles A* would be pretty good still.
Quote:Original post by Trap
As we are looking for the shortest path with the least number of turns shooting straight to the target doesn't help as you would need all shortest paths to decide which one has the least number of turns.
If you encode the turnnumber in you metric, like (distance<<32+turns) you will find the right path directly, but still need 32 GByte of data...
Not really, you can build that straight into the search by penalizing the paths that change directions.
My solution sketch is independent of path length and exponential on obstacle number.
A* is linear with path length and independent of obstacle number.
If there are lots of obstacles A* is better, if there is lots of empty space and few obstacles my solution is better.
I brought up an int min to int max search because of the weak specification of the problem. It is the hardest problem with a short input that fullfills the specs of the problem.
What is the meaning of "best first" in this problem? Distance to node + estimated distance to goal is equal for all nodes in the bounding box of start and goal. Take the one with the lowest distance to goal estimate?
A* is linear with path length and independent of obstacle number.
If there are lots of obstacles A* is better, if there is lots of empty space and few obstacles my solution is better.
I brought up an int min to int max search because of the weak specification of the problem. It is the hardest problem with a short input that fullfills the specs of the problem.
What is the meaning of "best first" in this problem? Distance to node + estimated distance to goal is equal for all nodes in the bounding box of start and goal. Take the one with the lowest distance to goal estimate?
Hmm Look at nehe lesson 21 that has a player, a grid and an enemy wich moves and each level has an extra enemy. Maybe that could be of use as maybe the base or a reference.
Quote:Original post by Trap
What is the meaning of "best first" in this problem? Distance to node + estimated distance to goal is equal for all nodes in the bounding box of start and goal. Take the one with the lowest distance to goal estimate?
Not sure what you are saying here. Best first is a specific pathfinding algorithm that uses the distance to goal heuristic only. Distance to current node is given cost, which A* uses in addition to the estimated distance to goal heuristic. Dijkstra uses only the given cost. You seem to be mixing up algorithms in some of your responses. Not only does your proposed algorithm sound unnecessarily complex, but it wouldn't produce an optimal path, which is one of the requirements the OP posted, unless maybe in an empty grid, which is unlikely to ever be the case of a search.
If he used A* and penalized paths that change directions to favor straight paths he could do it all in one search. Dijkstra and A*(without an underestimated heuristic) are the only options guaranteed to find an optimal path, so if that is indeed a requirement then those would likely be the choices he has. A* expands less of the grid than Dijkstra which makes it faster. Dijkstra only considers the given cost, A* considers given cost + heuristic cost. The heuristic cost is what allows it to bee-line for the goal if it can. It also allows you to tweak its speed an accuracy by tweaking the heurisic weight. By tweaking 1 number you can make it behave more like best first or Dijkstra.
I can't prove nor disprove that my algorithm sketch finds the optimal solution, can you?
Ok, while trying to give an example i found my error in thinking about best first. Thanks for making me think harder about it :)
Ok, while trying to give an example i found my error in thinking about best first. Thanks for making me think harder about it :)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
