Questions tagged [admissible-heuristic]
For questions related to admissible heuristics, which are heuristics that never overestimate the cost of reaching a goal.
8
questions
4
votes
2answers
167 views
If an heuristic is not admissible, can it be consistent?
I am solving a problem in which, according to the given values, the heuristic is not admissible. According to my calculation from other similar problems, it should be consistent, as well as keeping in ...
6
votes
1answer
54 views
Can two admissable heuristics not dominate each other?
I am working on a project for my artificial intelligence class. I was wondering if I have 2 admissible heuristics, A and B, is it possible that A does not dominate B and B does not dominate A? I am ...
5
votes
1answer
89 views
How do we determine whether a heuristic 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 heuristics.
Currently, I explored the Manhattan and Euclidean distances. ...
2
votes
1answer
70 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
1answer
97 views
Is the minimum and maximum of a set of admissible and consistent heuristics also consistent and admissible?
Let's suppose I have a set of heuristics $H$ = {$h_1, h_2, ..., h_N$}.
If all heuristics in $H$ are admissible, does that mean that a heuristic that takes the $\min(H)$ (or $\max(H)$ for that matter) ...
3
votes
1answer
158 views
How do I find whether this heuristic is or not admissible and consistent?
I was given the following problem to solve.
Given a circular trail divided by $n> 2$ segments labeled $0 \dots n-1$. In the beginning, an agent is at the start of segment number $0$ (the edge ...
2
votes
1answer
159 views
Why Nilsson's Sequence Score isn't an admissible heuristic?
I understand what an admissible heuristic is, I just don't know how to tell whether one heuristic is admissible or not. So, in this case, I'd like to know why Nilsson heuristic isn't admissible.
8
votes
1answer
6k 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 ...
