Questions tagged [a-star-search]
The a-star-search tag has no usage guidance.
8
questions
0
votes
2answers
31 views
Coefficients in cost function in A-star
I'd like to expand on this question :
https://stackoverflow.com/questions/52420788/why-does-the-a-star-algorithm-need-gn
Dijkstra's algorithm uses cost function $f(n) = g(n)$
whereas A* uses cost ...
0
votes
1answer
23 views
Can Dijkstra's algorithm outperform A star, in terms of vertices checked?
I know Dijkstra's algorithm can be seen as a specific case of A star, when the estimation heuristic used simply returns 0, so I know that A star with this specific heuristic can not check more ...
2
votes
2answers
128 views
A* without heuristic more efficient than Dijkstra
I am using the module networkx to operate on graphs made from OpenStreetMap.
I wanted to compare the shortest path algorithm to ...
2
votes
2answers
30 views
cheap multi agent path planning algorithms
I am trying to make a tower defence game where some critters are trying to make their ways through a 2D grid-like obstacle course. The idea is these critters cannot walk into the obstacles or into ...
2
votes
0answers
35 views
Heuristic for searching for solutions on an 8-puzzle variant with non-unique tiles
I'm trying to perform an A* search on a particular N-puzzle variant in which some tiles are identical. More specifically, assuming an $m \times m$ grid, there are m colors with m tiles of each. The ...
0
votes
0answers
201 views
How can an A* algorithm visit all nodes?
Is it possible to find the shortest path and visit all the nodes in a graph by A* algorithm? If yes, how?
0
votes
1answer
18 views
Term for an A*-like pathfinding strategy where only the heuristic goal distance matters
I am trying to find a proper term for the A*-like best-first pathfinding strategy where the node to expand next is the one with the least estimated distance from the goal, regardless of its distance ...
2
votes
2answers
77 views
Does an optimal path imply the heuristic is admissible?
If we are given an A$^*$ path search with some heuristic $h$ that yields an optimal path, without knowing that the heuristic is admissible beforehand, would this imply that $h$ is admissible?
