Submitted by: Submitted by lundchut
Views: 183
Words: 1860
Pages: 8
Category: Science and Technology
Date Submitted: 11/07/2012 02:30 AM
Informed or Heuristic Search Artificial Intelligence
A* Search
Use knowledge about the problem domain to explore the search space more efficiently Domain knowledge is contained in a heuristic (evaluation) function
CS 4633/6633 Artificial Intelligence
CS 4633/6633 Artificial Intelligence
Heuristic Functions
Heuristic: problem-specific knowledge that reduces expected search effort. Heuristic functions evaluate the relative desirability of expanding a node. Heuristics are often estimates of the distance, or cost, from the current state to the goal Time spent evaluating the heuristic function must be recovered by a reduction in search time.
¡ ¡ ¡ ¡
Notation
h(n) = estimated cost of the cheapest path from the state at node n to a goal state Require that h(n) = 0 if n is a goal state
CS 4633/6633 Artificial Intelligence
CS 4633/6633 Artificial Intelligence
Examples
1 7 6 2 8 3 4 5 3 6 1 4 7 2 5 8
Best-first search
Nodes on frontier (or fringe) of search tree are stored in open list Implement open list as a priority queue in which nodes are sorted according to some heuristic evaluation function The node that is expanded next is the one that seems “best” according to the evaluation function
Initial State
Goal
Heuristic Function 1: Number of misplaced tiles Heuristic Function 2: Total Manhattan distance
CS 4633/6633 Artificial Intelligence
CS 4633/6633 Artificial Intelligence
Greedy Search
Korf calls this “pure heuristic search” in his survey paper The priority queue is sorted in increasing order of h(n) The frontier node that is thought to be “closest” to the goal state is always expanded next
CS 4633/6633 Artificial Intelligence
Characteristics of Greedy Search
Resembles depth-first search (prefers a single path until it hits a dead-end.) Not optimal. Why? Not complete. Why? Worst case time complexity O(bm) where m is the maximum depth of search Space complexity same as time...