Questions tagged [a-star]
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.
30
questions
13
votes
1answer
14k views
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 ...
7
votes
3answers
32k views
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?
7
votes
1answer
166 views
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),...
6
votes
1answer
8k views
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 ...
6
votes
2answers
873 views
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:
...
5
votes
1answer
619 views
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 ...
4
votes
1answer
6k views
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?
3
votes
1answer
1k views
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.
3
votes
1answer
392 views
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 ...
2
votes
1answer
71 views
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$?
2
votes
1answer
403 views
Understanding the proof that A* search is optimal
I don't understand the proof that $A^*$ is optimal.
The proof is by contradiction:
Assume $A^*$ returns $p$ but there exists a $p'$ that is cheaper. When $p$ is chosen from the frontier, assume $...
2
votes
3answers
5k views
What heuristic to use when doing A* search with multiple targets? [closed]
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 ...
2
votes
1answer
81 views
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 ...
2
votes
1answer
348 views
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$ ...
2
votes
1answer
90 views
2
votes
0answers
45 views
Why do we use the tree-search version of breadth-first search or A*?
In Artificial Intelligence A Modern Approach, search algorithms are divided into tree-search version and graph-search version, where the graph-search version keeps an extra explored set to avoid ...
2
votes
0answers
41 views
How does heuristic work with multiple agents?
I have a question for heuristic search with multiple agents. I know how heuristic search works with one agent (ex. one Pacman) but I don't really understand it with multiple agents. Let's say we have ...
2
votes
0answers
114 views
How can I assign agents to tasks based on time and affinity?
I am working on an assignment problem.
Consider $K$ agents $A_1, \dots A_K$ and $N$ tasks $T_1, \dots T_N$. Each task has a certain time $t(T_i)$ to be completed and each agent has a matching (or ...
2
votes
1answer
135 views
In the graph search version of A*, can I stop the search the first time I encounter the goal node?
I am going through Russel and Norvig's Artificial Intelligence: A Modern Approach (3rd edition). I was reading the part regarding the A* algorithm
A* graph search version is optimal when heuristic ...
1
vote
2answers
85 views
Is there any situation in which breadth-first search is preferable over A*?
Is there any situation in which breadth-first search is preferable over A*?
1
vote
1answer
375 views
What is the difference between the heuristic function and the evaluation function in A*?
I am reading college notes on state search space. The notes (which are not publicly available) say:
To do state-search space, the strategy involves two parts: defining a heuristic function, and ...
1
vote
1answer
133 views
What does a consistent heuristic become if an edge is removed in A*?
For the A* algorithm, a consistent heuristic is defined as follows:
if, for every node $n$ and every successor $m$ of $n$ generated by any action $a$, $h(n) \leq c(n,m) + h(m)$.
Suppose the edge $c(...
1
vote
1answer
111 views
How can I calculate the shortest path between two 2d vector points in an environment with obstacles?
I have a 2D plane, with a fixed height and width of 10M. The plane has an agent (or robot) in the point $(1, 2.2)$, and an electric outlet in the point $(8.2, 9.1)$. The plane has a series of ...
1
vote
1answer
139 views
Which heuristics guarantee the optimality of A*?
The following is a statement and I am trying to figure out if it's true or false and why.
Given a non-admissible heuristic function, A* will always give a solution if one exists, but there is no ...
1
vote
1answer
59 views
Doesn't the number of explored nodes with IDA* increase linearly?
I think I'm misunderstanding the description of IDA* and want to clarify.
IDA* works as follows (quoting from Wiki):
At each iteration, perform a depth-first search, cutting off a branch when its ...
0
votes
2answers
336 views
How can the A* algorithm be optimized?
How can the A* algorithm be optimized?
Any references that shows the optimization of A* algorithm are also appreciated.
0
votes
1answer
4k views
How do you calculate the heuristic value in this specific case?
The A* algorithm uses the "evaluation function" $f(n) = g(n) + h(n)$, where
$g(n)$ = cost of the path from the start node to node $n$
$h(n)$ = estimated cost of the cheapest path from $n$ to the ...
0
votes
0answers
28 views
Given an admissible/consistent heuristic $h(n)$, would the tree and graph search versions of A* return the optimal path with $g(n)=2h(n)$?
I know that, if the heuristic function is admissible and consistent, then the A* algorithm always returns an optimal solution. But for the following situation, does A* search return optimal solution?
...
0
votes
0answers
62 views
Comparing heuristics in A* search and rescue operation
I was reading a research paper titled A Comparative Study of A-star Algorithms for Search and rescue in Perfect Maze (2011).
I have some doubts regarding it:
1.
The Evaluation Function of $\mathrm{A}^...
0
votes
0answers
29 views
Incorrect node expansion in game board with A* search
I have the following game board below, and we're using A* search to find the optimal path from the agent to the key. There are 8 directions. Up, down, left, right have a cost of 1, and diagonal ...
