Questions tagged [admissible-heuristic]
For questions related to admissible heuristics, which are heuristics that never overestimate the cost of reaching a goal.
17
questions
2
votes
1answer
36 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?
-1
votes
0answers
28 views
How to know suitable search algorithm from heuristic values?
If we consider the following evaluation function with path cost $g(n)$ and admissible heuristic $h(n)$ for a heuristic search problem.
$ f(n) = (w*g(n)) + ((1-w) + h(n)) $
Where the value of w is $ 0....
2
votes
1answer
74 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 ...
0
votes
0answers
23 views
Can an inadmissable heuristic be consistent? [duplicate]
If something is inadmissible, can we just assume it's also inconsistent?
Also, I understand how to check if a heuristic is inadmissible, but I'm still a bit confused on checking consistency.
If I have ...
0
votes
0answers
22 views
Satisficing searches - how does speedy search compensate for higher execution costs
While reading AI: A Modern Approach (4th ed), I have some difficulty in coming to terms with the usefulness of a satisficing search. Generally speaking, I understand that in real life situations we ...
2
votes
1answer
250 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$ ...
1
vote
1answer
108 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 ...
2
votes
1answer
448 views
If $h_i$ are consistent and admissible, are their sum, maximum, minimum and average also consistent and admissible?
Consider the following question:
$n$ vehicles occupy squares $(1, 1)$ through $(n, 1)$ (i.e., the bottom row) of an $n \times n$ grid. The vehicles must be moved to the top row but in reverse order; ...
3
votes
1answer
299 views
Is the summation of consistent heuristic functions also consistent?
Imagine that we have a set of heuristic functions $\{h_i\}_{i=1}^N$, where each $h_i$ is both admissible and consistent (monotonic). Is $\sum_{i=1}^N h_i$ still consistent or not?
Is there any proof ...
4
votes
2answers
3k 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
142 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
506 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 ...
2
votes
1answer
312 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
1k 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
300 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
518 views
Why isn't Nilsson's Sequence Score an admissible heuristic function?
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's sequence score heuristic ...
10
votes
1answer
13k 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 ...
