For questions related to the A* (or A) search algorithm, which is a very famous state-space search algorithm and widely taught in Computer Science and Artificial Intelligence. A* is a best-first search algorithm that is guaranteed to find the optimal solution given an admissible heuristic function, so A* is also an informed search algorithm, as opposed to e.g. depth-first search, which is an uninformed search algorithm.
Questions tagged [a-star]
38 questions
14
votes
3 answers
What are the differences between A* and greedy best-first search?
What are the differences between the A* algorithm and the greedy best-first search algorithm? Which one should I use? Which algorithm is the better one, and why?
Marosh Fatima
- 375
- 1
- 3
- 10
13
votes
1 answer
Why is A* optimal if the heuristic function is admissible?
A heuristic is admissible if it never overestimates the true cost to reach the goal node from $n$. If a heuristic is consistent, then the heuristic value of $n$ is never greater than the cost of its successor, $n'$, plus the successor's heuristic…
Wizard
- 303
- 1
- 2
- 6
7
votes
1 answer
How do we determine whether a heuristic function is better than another?
I am trying to solve a maze puzzle using the A* algorithm. I am trying to analyze the algorithm based on different applicable heuristic functions.
Currently, I explored the Manhattan and Euclidean distances. Which other heuristic functions are…
m2rik
- 333
- 1
- 9
7
votes
1 answer
A* is similar to Dijkstra with reduced cost
According to this Wikipedia article
If the heuristic $h$ satisfies the additional condition $h(x) \leq d(x, y) + h(y)$ for every edge $(x, y)$ of the graph (where $d$ denotes the length of that edge), then $h$ is called monotone, or consistent. In…
Shrey Shrivastava
- 71
- 2
6
votes
1 answer
How is iterative deepening A* better than A*?
The iterative deepening A* search is an algorithm that can find the shortest path between a designated start node and any member of a set of goals.
The A* algorithm evaluates nodes by combining the cost to reach the node and the cost to get from…
Huma Qaseem
- 179
- 1
- 3
- 12
6
votes
2 answers
How does A* search work given there are multiple goal states?
When I have read through the fundamentals of AI, I saw a situation (i.e., a search space) which is illustrated in the following picture.
These are the heuristic estimates:
h(B)=9
h(D)=10
h(A)=2
h(C)=1
If we use the A* algorithm, the node $B$ will…
hellojoshhhy
- 163
- 3
5
votes
1 answer
How do I show that uniform-cost search is a special case of A*?
How do I show that uniform-cost search is a special case of A*? How do I prove this?
dua fatima
- 323
- 1
- 2
- 10
4
votes
1 answer
What is a good heuristic function for A* to solve the "blocks world" game?
I am developing a heuristic solution for the blocks world problem.
I tried using the number of blocks out of place as my $h(n)$. It seems a little ineffective.
Can someone please point out a suitable heuristic for the problem and explain with a few…
user3758749
- 41
- 1
- 3
3
votes
3 answers
What heuristic to use when doing A* search with multiple targets?
Usually, using the Manhattan distance as a heuristic function is enough when we do an A* search with one target. However, it seems like for multiple goals, this is not the most useful way. Which heuristic do we have to use when we have multiple…
dragan
- 31
- 1
- 2
3
votes
1 answer
Is there an error in A* optimality proof Russel-Norvig 4th edition?
In "AI: A Modern Approach", 4th edition, by Russell and Norvig, they give a purported proof that A* is cost-optimal for any admissible heuristic. The given proof seems most certainly wrong. They want to show that all nodes on the optimal path are…
vdbuss
- 81
- 3
3
votes
1 answer
What are the differences between Q-Learning and A*?
Q-learning seems to be related to A*. I am wondering if there are (and what are) the differences between them.
Gonçalo Peres
- 191
- 1
- 4
- 11
3
votes
1 answer
Is A* with an admissible but inconsistent heuristic optimal?
I understand that, in tree search, an admissible heuristic implies that $A*$ is optimal. The intuitive way I think about this is as follows:
Let $P$ and $Q$ be two costs from any respective nodes $p$ and $q$ to the goal. Assume $P
Harry Stuart
- 161
- 3
3
votes
1 answer
A* and uniform-cost search are apparently incomplete
Consider the following diagram of a graph representing a search space.
If we start at $B$ and try to reach goal state $E$, the lowest-cost first search (LCFS) (aka uniform-cost search) algorithm fails to find a solution. This is because, $B$…
KGhatak
- 165
- 6
2
votes
1 answer
How is the cost of the path to each node computed in A*?
How is the cost of the path to each node $n$ computed in the A* algorithm? Do we need to add the cost of the path to the parent node $p$ to the cost of the path of the child node $n$?
Jazba
- 31
- 2
2
votes
1 answer
If $h_1(n)$ is admissible, why does A* tree search with $h_2(n) = 3h_1(n)$ return a path that is at most thrice as long as the optimal path?
Consider a heuristic function $h_2(n) = 3h_1(n)$. Where $h_1(n)$ is admissible.
Why are the following statements true?
$A^*$ tree search with $h_2(n)$ will return a path that is at most thrice as long as the optimal path.
$h_2(n) + 1$ is…
Jia Rong
- 21
- 2