COMPSCI 171 Lecture Notes - Lecture 4: Admissible Heuristic, Consistent Heuristic, Search Algorithm
10 Dec 2018
School
Department
Course
Professor
Document Summary
Cs 171 - lecture 4 - heuristic search: gbfs, a* Best-first, a* (and if needed for memory limits, rbfs, sma*) A* is optimal with admissible (tree)/consistent (graph) heuristics. A* is quick and easy to code and often works very well. A structured way to add smarts to your solution. Use heuristic function h(n) for each nose. Of optimal cost to goal from node n. G(n) - known path cost so far to node n. H*(n) = true optimal cost from n to goal (unknown to agent) Order the nodes in frontier by an evaluation function. Of total cost to goal through n. Search efficiency depends heavily on heuristic quality. Common sense rule or rules intended to increase the probability of solving some problem. Estimate of (optimal) remaining cost from n to goal. Defined using only the state of node n. H(n) = 0 if n is a goal node. Provides problem-specific knowledge to the search algorithm.
