heuristic-search.pdfVIP

1Heuristic Search Russell and Norvig: Chapter 4 CSMSC 421 – Fall 2003 Modified Search Algorithm 1. INSERT(initial-node,FRINGE) 2. Repeat: If FRINGE is empty then return failure n REMOVE(FRINGE) s STATE(n) If GOAL?(s) then return path or goal state For every state s’ in SUCCESSORS(s) Create a node n’ INSERT(n’,FRINGE) Search Algorithms Blind search – BFS, DFS, uniform cost no notion concept of the “right direction” can only recognize goal once it’s achieved Heuristic search – we have rough idea of how good various states are, and use this knowledge to guide our search Best-first search Idea: use an evaluation function f(n) for each node Estimate of desirability Expand most desirable unexpanded node Implementation: fringe is queue sorted by descreasing order of desirability Greedy search A* search 2Heuristic Websters Revised Unabridged Dictionary (1913) (web1913) Heuristic \Heu*ristic\, a. [Greek. to discover.] Serving to discover or find out. The Free On-line Dictionary of Computing (15Feb98) heuristic 1. programming A rule of thumb, simplification or educated guess that reduces or limits the search for solutions in domains that are difficult and poorly understood. Unlike algorithms, heuristics do not guarantee feasible solutions and are often used with no theoretical guarantee. 2. algorithm approximation algorithm. From WordNet (r) 1.6 heuristic adj 1: (computer science) relating to or using a heuristic rule 2: of or relating to a general formulation that serves to guide investigation [ant: algorithmic] n : a commonsense rule (or set of rules) intended to increase the probability of solving some problem [syn: heuristic rule, heuristic program] Informed Search Add domain-specific information to select the best path along which to continue searching Define a heuristic function, h(n), that estimates the “goodness” of a node n. Specifically, h(n) = estimated cost (or distance) of minimal cost path from n to a goal state. The heuristic function is