Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

Hot answers tagged

16 votes
Accepted

What are the differences between Q-Learning and A*?

Q-learning and A* can both be viewed as search algorithms, but, apart from that, they are not very similar. Q-learning is a reinforcement learning algorithm, i.e. an algorithm that attempts to find a ...
user avatar
  • 33.2k
13 votes
Accepted

Why is A* optimal if the heuristic function is admissible?

This is well covered in the corresponding chapter of Russell & Norvig (chapter 3.5, pages 93 to 99 (Third Edition)). Check that out for more details. First, let's review the definitions: Your ...
user avatar
11 votes
Accepted

How is iterative deepening A* better than A*?

A* is a best-first search algorithm, which means that it is an algorithm that uses both "past knowledge", gathered while exploring the search space, denoted by $g(n)$, and an admissible heuristic ...
user avatar
  • 33.2k
9 votes
Accepted

What are the differences between A* and greedy best-first search?

Both algorithms fall into the category of "best-first search" algorithms, which are algorithms that can use both the knowledge acquired so far while exploring the search space, denoted by $g(n)$, and ...
user avatar
  • 33.2k
6 votes
Accepted

How do I show that uniform-cost search is a special case of A*?

Yes, UCS is a special case of A*. UCS uses the evaluation function $f(n) = g(n)$, where $g(n)$ is the length of the path from the starting node to $n$, whereas A* uses the evaluation function $f(n) =...
user avatar
  • 33.2k
5 votes

How does A* search work given there are multiple goal states?

Yes. If you leave A* running (i.e. do not impose a goal condition on a newly-encountered state), all states will be explored, just as they would be in breadth- or depth- first search.
user avatar
3 votes
Accepted

A* and uniform-cost search are apparently incomplete

You forgot to calculate and take into account the costs of the actual paths. You forgot to accumulate the cost of the edges for going forward and backward multiple times! The evaluation function of ...
user avatar
  • 33.2k
3 votes

How is the cost of the path to each node computed in A*?

The evaluation function in A* is $f(n) = g(n) + h(n)$, where $g(n)$ is the cost of the path from the starting node to $n$ and $h(n)$ is an estimate of the distance from $n$ to the goal node. To ...
user avatar
  • 33.2k
3 votes

What is a good heuristic function for A* to solve the "blocks world" game?

You may start assigning penalties for undesirable conditions in a state like: 1) Number of blocks outside stack 0. Supose you penalize with 10 units each block outside stack 0, then the starting ...
user avatar
  • 176
2 votes

What heuristic to use when doing A* search with multiple targets?

If by "visit multiple targets", you mean "visit several points in the fastest order", you are no longer in a simple path-finding-style search problem, but instead in an optimization problem. This is ...
user avatar
2 votes
Accepted

How do you calculate the heuristic value in this specific case?

The most obvious heuristic would indeed simply be the straight-line distance. In most cases, where you have, for example, x and y...
user avatar
  • 9,326
2 votes

What are the differences between A* and greedy best-first search?

According to the book Artificial Intelligence: A Modern Approach (3rd edition), by Stuart Russel and Peter Norvig, specifically, section 3.5.1 Greedy best-first search (p. 92) Greedy best-first ...
2 votes
Accepted

How can I calculate the shortest path between two 2d vector points in an environment with obstacles?

The usual way to solve this kind of problem is to construct a configuration space: extruding all the polygonal obstacles by sliding the polygon corresponding to the robot around them (some slides). ...
user avatar
2 votes

How do we determine whether a heuristic function is better than another?

In the A* algorithm, at each iteration, a node is chosen which minimizes a certain function, called the evaluation function, which, in the case of A*, is defined as $$f(n)=g(n)+h(n)$$ where $g(n)$ ...
user avatar
  • 33.2k
2 votes

Understanding the proof that A* search is optimal

The key phrase here is because heuristics are admissible In other words, the heuristics never overestimate the path length: $$cost(n) + heuristic(n) \le cost(\text{any path going through n})$$ And ...
user avatar
2 votes

Is there any situation in which breadth-first search is preferable over A*?

The only general situation that comes to my mind where BFS could be preferred over A* is when your graph is unweighted and the heuristic function is $h(n) = 0, \forall n \in V$. However, in that case, ...
user avatar
  • 33.2k
2 votes
Accepted

What is the difference between the heuristic function and the evaluation function in A*?

What is the difference between the heuristic function and the evaluation function in A*? The evaluation function, often denoted as $f$, is the function that you use to choose which node to expand ...
user avatar
  • 33.2k
2 votes
Accepted

What does a consistent heuristic become if an edge is removed in A*?

Consistency is a property of heuristics. You can think of consistency as the common sense idea that our guess at the time to go from $A \rightarrow B \rightarrow C$ cannot be more than the time to go ...
user avatar
1 vote

Is there an error in A* optimality proof Russel-Norvig 4th edition?

You did not compute $g(n)$ correctly. A* expands according to the evaluation function $f(n) = g(n) + h(n)$, where $g(n)$ is the cost of the path from the start node to $n$. Initially, you add $A$ to ...
user avatar
  • 33.2k
1 vote

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?

The sketch of the proof for your first question: for an open node $n$, if $f_1(n) = g(n) + h_1(n)$, in the same situation in using $h_2$, it will be $f_2(n) = g(n) + 3 h_1(n)$. Hence, all the time ...
user avatar
  • 1,663
1 vote

Is there any situation in which breadth-first search is preferable over A*?

There is an inherent assumption in heuristic search that the heuristic function points you in the right direction. A* largely depends on how good the heuristic function is. Two nice properties for the ...
user avatar
  • 3,093
1 vote

Is A* with an admissible but inconsistent heuristic optimal?

It depends on what you mean by optimal. A* will always find the optimal solution (that is, the algorithm is admissible) as long as the heuristic is admissible. (Note that the definition of admissible ...
user avatar
  • 351
1 vote

A* is similar to Dijkstra with reduced cost

What you are doing when calculating $d'(x,y)$: $d(x,y)$: calculating the original edge distance from $x$ to $y$ $h(y)$: plus the heuristic from $y$ to the goal $h(x)$: minus the heuristic from $x$ to ...
user avatar
1 vote
Accepted

How can the A* algorithm be optimized?

Check below reference url for A* algorithms ... https://takinginitiative.wordpress.com/2011/05/02/optimizing-the-a-algorithm/ https://en.wikipedia.org/wiki/Heap_%28data_structure%29
user avatar
1 vote

How can the A* algorithm be optimized?

The first step of optimisation is to measure where inside the implementation most time is spent -- you don't actually optimise the algorithm itself, but a specific implementation of it. This step ...
user avatar
  • 5,047
1 vote

What kind of search method is A*?

A* is an informed search algorithm. A* informed because it is based on the use of a heuristic function, which estimates the distance of each node to the goal, that is, the heuristic function provides ...
user avatar
  • 33.2k
1 vote

What are the differences between A* and greedy best-first search?

What you said isn't totally wrong, but the A* algorithm becomes optimal and complete if the heuristic function h is admissible, which means that this function never overestimates the cost of reaching ...
user avatar
  • 11
1 vote
Accepted

How does A* search work given there are multiple goal states?

Question 1: First of all, you state that that the goal G2 will be found first by relying on the expansion order R, B, D, G2. This is wrong. It is extremely easy to ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible