Questions tagged [a-star-search]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3
votes
1answer
52 views

Are there graphs for which A* cannot be admissible?

Wikipedia states that "On infinite graphs with a finite branching factor and edge costs that are bounded away from zero $ (d(x,y)>\varepsilon >0$ for some fixed $\varepsilon$), A* is guaranteed ...
2
votes
2answers
126 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?
2
votes
2answers
346 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
41 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
23 views

Finding multiple paths through a grid such that every grid square is equally used

Setup Here’s the setup: I have an $N$ x $N$ grid of tiles, and a list of $M$ agents that need to move across the grid. Each agent has its own start tile $S(a)$, end tile $E(a)$, and an exact number ...
2
votes
0answers
41 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 ...
1
vote
0answers
450 views

Comparing classical tree-search algorithms (BFS,DFS,A*,IDS) - when to use one or the other?

I have a question about classical tree-search algorithms as I will have an exam soon and this is the type of questions they might be asking. Although I know how to compare the complexities, optimality,...
0
votes
1answer
26 views

Why doesn't A* give the optimal path for navigating from A to R in this state space?

Well, I have heard that the A* algorithm is optimal and complete. However, when trying to navigate from A to R using A*, it outputs the path, A --> E --> R, although there is a shorter path, A --> M --...
0
votes
2answers
162 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
77 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 ...
0
votes
1answer
25 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 ...
0
votes
0answers
289 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?