Question 5239 – Artificial-Intelligence

Heuristic Search Strategies:
A key component of an evaluation function is a heuristic function h(n), which estimates the cost of the cheapest path from node ‘n’ to a goal node
→ In connection of a search problem “heuristics” refers to a certain (but loose) upper or lower bound for the cost of the best solution
→ Goal states are nevertheless identified: in a corresponding node ‘n’ it is required that h(n)=0
E.g., a certain lower bound bringing no information would be to set h(n) ≅0
→ Heuristic functions are the most common form in which additional knowledge is imported to the search algorithm
Generating admissible heuristics from relaxed problems
→ To come up with heuristic functions one can study relaxed problems from which some restrictions of the original problem have been removed
→ The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem (does not overestimate)
→ The optimal solution in the original problem is, by definition, also a solution in the relaxed problem
Example:
→ heuristic h​ 1​ for the 8-puzzle gives perfectly accurate path length for a simplified version of the puzzle, where a tile can move anywhere
→ Similarly h​ 2​ gives an optimal solution to a relaxed 8-puzzle, where tiles can move also to occupied squares
→ If a collection of admissible heuristics is available for a problem, and none of them dominates any of the others, we can use the composite function h(n)=max{ h​ 1​ (n), …, h​ m​ (n) }
→ The composite function dominates all of its component functions and is consistent if none of the components overestimates.