Questions tagged [a-star-search]
The a-star-search tag has no usage guidance.
17
questions
1
vote
2answers
61 views
Should your heuristic for an A* search algorithm be the same scale as your actual weights?
I'm a bit confused about the scale of heuristics for implementing A* search. $f(n)$ is the total cost of travelling to a node $n$. It is calculated by $f(n) = g(n) + h(n)$. $g(n)$ is the cost of the ...
0
votes
0answers
33 views
A* search tree version - Can a node be in the frontier multiple times
I took an exam today and it had a question on A* tree search version, we only briefly skimmed over this on the material, focusing more on the graph search version.
In the example in the question text ...
0
votes
0answers
13 views
What's the best way to combine multiple A* searches?
I have a graph that looks like this
The highlights nodes must be visited, and the blue node must be visited last, the stickman must be the start of the path. The weights are the Euclidean distance ...
0
votes
1answer
62 views
Using A* path finding is giving me inaccurate results
So i am using A* path finding to find a path from a person, to a node on a graph. This person has a few 'must pass' nodes that they must go through. So my solution was to run the algorithm for each of ...
0
votes
0answers
43 views
Pseudocode for A-star algorithm removes nodes from the currentList which are not in the list
I am trying to implement A star algorithm with Python. I am trying with this pseudocode found on Medium:
...
3
votes
1answer
93 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
0answers
32 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 ...
0
votes
1answer
28 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 --...
2
votes
0answers
2k 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
2answers
329 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
109 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
622 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
48 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
49 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
358 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
31 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
227 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?
