# Tag Info

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 ...
• 9,037

### Is the summation of consistent heuristic functions also consistent?

No, it will not necessary be consistent or admissible. Consider this example, where $s$ is the start, $g$ is the goal, and the distance between them is 1. s --1-- g Assume that $h_0$ and $h_1$ are ...
• 361
Accepted

### Can two admissable heuristics not dominate each other?

This is possible. Admissibility only asserts that the heuristic will never overestimate the true cost. With that being said, it is possible for one heuristic in some cases to do better than another ...
• 1,086

### 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)$ ...
• 37k

### If an heuristic is not admissible, can it be consistent?

If a heuristic is not admissible, can it be consistent? No. Consistency implies admissibility. In other words, if a heuristic is consistent, it is also admissible. However, admissibility does not ...
• 37k

### If an heuristic is not admissible, can it be consistent?

For a heuristic to be admissible, it must never overestimate the distance from a state to the nearest goal state. For a heuristic to be consistent, the heuristic's value must be less than or equal to ...
• 9,037

### 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 ...
Accepted

• 1,723
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 ...
• 1,723
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 ...
• 361
1 vote

### If $h_i$ are consistent and admissible, are their sum, maximum, minimum and average also consistent and admissible?

The issue is that you must include assumptions about hopping into your heuristic. In particular, if you are considering individual cars then you must assume that they might be able to hop all of the ...
• 361
1 vote
Accepted

### Why isn't Nilsson's Sequence Score an admissible heuristic function?

I will use the 8-puzzle game to show you why Nilson's sequence score heuristic function is not admissible. In the 8-puzzle game, you have a $3 \times 3$ board of (numbered) squares as follows. ...
• 37k

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