# 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
Filter by
Sorted by
Tagged with
29k 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
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 ...
• 161
2k 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
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 ...