# Questions tagged [consistent-heuristic]

For questions related to consistent heuristics, which are heuristics whose estimate is always less than or equal to the estimated distance from any neighboring vertex to the goal, plus the cost of reaching that neighbor.

13 questions
Filter by
Sorted by
Tagged with
1 vote
21 views

### Doesn't an admissible heuristic ensure optimality in the graph-search version of A*?

I'm reading a text book "Artificial Intelligence - A Modern Approach (3rd Edition)". In page 95, the book mentions that "A* has the following properties: the tree-search version of A* ...
• 11
96 views

### How do we know that $c(n,a,G) = h^{\ast}(n)$, in the proof that if a heuristic is consistent then it is admissible?

I found a proof that if a heuristic $h$ is consistent, then it is admissible, but I'm confused by one of the steps in the proof. The proof is by induction on $k$, the number of actions from a node $n$ ...
546 views

### Can A* be non-optimal if it uses an admissible but inconsistent heuristic with graph search?

The book "Artificial Intelligence: A Modern Approach" (4th edition, global version) says "With an admissible heuristic, A* is cost-optimal...". An admissible heuristic is one ...
• 1
268 views

### Is possible to perform an early goal test with A* using a consistent heuristic?

I have a doubt about A* goal test. As far as I know an early goal test is performed when a node (representing a certain state) is inserted in the frontier or, to conform with AIMA terminology, when is ...
• 21
199 views

### Is $\min(h_1(s),\ h_2(s))$ consistent?

If $h_1(s)$ is a consistent heuristic and $h_2(s)$ is a admissible heuristic, is $\min(h_1(s),\ h_2(s))$ consistent?
• 21
3k 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$ ...
• 161
1 vote