Questions tagged [heuristics]
In AI, the term "heuristic" is used in the context of non-blind (i.e., informed) search and planning: the problem of finding a sequence of actions to find/generate a desired state from an initial state. Heuristics" are problem relaxations of the original problem. They get as input the current state/search node and output the cost of the relaxed solution from there to goal. This heuristic value is then used for search guidance.
5 questions
13
votes
1
answer
31k
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 ...
- 303
7
votes
4
answers
6k
views
What else can boost iterative deepening with alpha-beta pruning?
I read about minimax, then alpha-beta pruning, and then about iterative deepening. Iterative deepening coupled with alpha-beta pruning proves to quite efficient as compared to alpha-beta alone.
I have ...
- 171
6
votes
2
answers
3k
views
How does A* search work given there are multiple goal states?
When I have read through the fundamentals of AI, I saw a situation (i.e., a search space) which is illustrated in the following picture.
These are the heuristic estimates:
...
- 163
6
votes
1
answer
1k
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 ...
- 163
3
votes
1
answer
2k
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 ...
- 177