Questions tagged [a-star-search]
The a-star-search tag has no summary.
27 questions
1
vote
1
answer
155
views
Tree Search $A^*$ With an Admissible Heuristic Does Not Necessarily Return an Optimal Solution
I know that the title of this post is wrong, but I got stuck on an example. Consider the graph below, which I obtained from here.
To the best of my knowledge, the tree search version of $A^*$ fails ...
- 111
1
vote
2
answers
110
views
Why Can Johnson’s Algorithm Handle Negative Weights but A* Cannot?
I'm trying to understand why Johnson’s algorithm can handle graphs with negative edge weights by using a potential function, while A* cannot, even though both use similar weight adjustments.
Johnson’s ...
- 125
1
vote
2
answers
265
views
Shortest path between two nodes with time-dependent edge weights
I have city traffic data. The roads are represented as a directed graph (a road can have traffic both ways, at most two-lane roads included), vertices being points on a map where two or more road ...
- 111
0
votes
0
answers
77
views
A* (A-star) search algorithm including closest distance from a node to an obstacle in heuristic and step cost
I want to include the distance of a node to the closest obstacle in the cost function, so that the path length is not only minimal, but also not near obstacles.
We know that:
Dijkstra's algorithm uses ...
- 1
1
vote
1
answer
208
views
Simplified Memory Bounded A*
I have been studying the SMA* algorithm and I am having trouble understanding the backup operation. Specifically, I don't understand why the f value of a child node should be the maximum of its own f ...
- 11
0
votes
2
answers
247
views
How to avoid costly square root operations in A* algorithm?
As a reminder, in an A* algorithm, vertices in the priority queue are sorted according to their priority $f = g + h$, where $g$ is the cost of getting to this vertex from the start vertex, and $h$ is ...
- 827
1
vote
2
answers
314
views
Optimality of A* algorithm
In the book Artificial Intelligence a Modern Approach 4th edition, the author claims that the A* algorithm is cost-optimal if the heuristic function is ...
- 111
0
votes
0
answers
212
views
How is this "pathmax modification," $f(n^\prime) = \max(g(n^\prime) + h(n^\prime), f(n))$, useful?
I am studying the concept of heuristics in search algorithms, and the $A^*$ search algorithm in particular. I am told the following:
Greedy search minimises estimated path-cost to goal.
But it's ...
- 227
1
vote
1
answer
210
views
A* pseudocode problem
What is the difference between this two pseudocode and which one should i implement?
...
- 11
0
votes
1
answer
544
views
Any-goal bidirectional A* pathfinding reference
I want to solve the problem of finding a shortest path on a directed weighted graph from a certain node to any of a specified set of destination nodes (preferably the closest one, but that's not that ...
- 131
2
votes
1
answer
1k
views
Difference between cost and the heuristic function in A* search
Looking at the image above, thinking in terms of A* search. I don't fully understand the heuristic function. The cost makes sense, so thinking in terms of a traditional map or navigation scenario. I'd ...
- 123
3
votes
0
answers
243
views
A* (A-star) path finding in continuous environments with "sticky slower" areas
I have a search problem, finding the shortest path for 3 vehicles to their parking spots, in a continuous environment (inputs are continuous for velocity, turn speed) and the location is continuous, ...
- 207
2
votes
1
answer
152
views
D* Lite - can edge costs be asymmetric?
I'm trying to modify the original D* Lite algorithm adding a margin constraint wrt to any nearby obstacle to be satisfied for each selected cell in the path. This causes the edge cost function between ...
- 145
1
vote
2
answers
902
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 ...
- 13
0
votes
1
answer
664
views
Using A* path finding is giving me inaccurate results
So I am using A* pathfinding 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 ...
- 21