DOC PREVIEW
USC CSCI 561 - session06

This preview shows page 1-2-17-18-19-36-37 out of 37 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Last time: Problem-SolvingSlide 2Slide 3Last time: Finding a solutionSlide 5Slide 6A Clean Robust AlgorithmSlide 8Last time: search strategiesEvaluation of search strategiesLast time: uninformed search strategiesThis time: informed searchBest-first searchRomania with step costs in kmGreedy searchPowerPoint PresentationSlide 17Slide 18Slide 19Properties of Greedy SearchSlide 21A* searchSlide 23Slide 24Slide 25Slide 26Slide 27Slide 28Optimality of A* (standard proof)Optimality of A* (more useful proof)Properties of A*Slide 32Proof of lemma: pathmaxAdmissible heuristicsSlide 35Relaxed ProblemNext timeCS 561, Session 61Last time: Problem-Solving•Problem solving: •Goal formulation •Problem formulation (states, operators) •Search for solution•Problem formulation:•Initial state•?•?•?•Problem types: •single state: accessible and deterministic environment•multiple state: ?•contingency: ?•exploration: ?CS 561, Session 62Last time: Problem-Solving•Problem solving: •Goal formulation •Problem formulation (states, operators) •Search for solution•Problem formulation:•Initial state•Operators•Goal test•Path cost•Problem types: •single state: accessible and deterministic environment•multiple state: ?•contingency: ?•exploration: ?CS 561, Session 63Last time: Problem-Solving•Problem solving: •Goal formulation •Problem formulation (states, operators) •Search for solution•Problem formulation:•Initial state•Operators•Goal test•Path cost•Problem types: •single state: accessible and deterministic environment•multiple state: inaccessible and deterministic environment•contingency: inaccessible and nondeterministic environment•exploration: unknown state-spaceCS 561, Session 64Last time: Finding a solutionFunction General-Search(problem, strategy) returns a solution, or failureinitialize the search tree using the initial state problemloop doif there are no candidates for expansion then return failurechoose a leaf node for expansion according to strategyif the node contains a goal state then return the corresponding solutionelse expand the node and add resulting nodes to the search treeendSolution: is ???Basic idea: offline, systematic exploration of simulated state-space by generating successors of explored states (expanding)CS 561, Session 65Last time: Finding a solutionFunction General-Search(problem, strategy) returns a solution, or failureinitialize the search tree using the initial state problemloop doif there are no candidates for expansion then return failurechoose a leaf node for expansion according to strategyif the node contains a goal state then return the corresponding solutionelse expand the node and add resulting nodes to the search treeendSolution: is a sequence of operators that bring you from current state to the goal state.Basic idea: offline, systematic exploration of simulated state-space by generating successors of explored states (expanding).Strategy: The search strategy is determined by ???CS 561, Session 66Last time: Finding a solutionFunction General-Search(problem, strategy) returns a solution, or failureinitialize the search tree using the initial state problemloop doif there are no candidates for expansion then return failurechoose a leaf node for expansion according to strategyif the node contains a goal state then return the corresponding solutionelse expand the node and add resulting nodes to the search treeendSolution: is a sequence of operators that bring you from current state to the goal stateBasic idea: offline, systematic exploration of simulated state-space by generating successors of explored states (expanding)Strategy: The search strategy is determined by the order in which the nodes are expanded.CS 561, Session 67A Clean Robust Algorithm Function UniformCost-Search(problem, Queuing-Fn) returns a solution, or failureopen  make-queue(make-node(initial-state[problem]))closed  [empty]loop doif open is empty then return failurecurrnode  Remove-Front(open)if Goal-Test[problem] applied to State(currnode) then return currnodechildren  Expand(currnode, Operators[problem])while children not empty[… see next slide …]endclosed  Insert(closed, currnode)open  Sort-By-PathCost(open)endCS 561, Session 68A Clean Robust Algorithm [… see previous slide …]children  Expand(currnode, Operators[problem])while children not emptychild  Remove-Front(children)if no node in open or closed has child’s stateopen  Queuing-Fn(open, child)else if there exists node in open that has child’s stateif PathCost(child) < PathCost(node)open  Delete-Node(open, node)open  Queuing-Fn(open, child)else if there exists node in closed that has child’s stateif PathCost(child) < PathCost(node)closed  Delete-Node(closed, node)open  Queuing-Fn(open, child)end[… see previous slide …]CS 561, Session 69Last time: search strategiesUninformed: Use only information available in the problem formulation•Breadth-first•Uniform-cost•Depth-first•Depth-limited•Iterative deepeningInformed: Use heuristics to guide the search•Best first•A*CS 561, Session 610Evaluation of search strategies•Search algorithms are commonly evaluated according to the following four criteria:•Completeness: does it always find a solution if one exists?•Time complexity: how long does it take as a function of number of nodes?•Space complexity: how much memory does it require?•Optimality: does it guarantee the least-cost solution?•Time and space complexity are measured in terms of:•b – max branching factor of the search tree•d – depth of the least-cost solution•m – max depth of the search tree (may be infinity)CS 561, Session 611Last time: uninformed search strategiesUninformed search:Use only information available in the problem formulation•Breadth-first•Uniform-cost•Depth-first•Depth-limited•Iterative deepeningCS 561, Session 612This time: informed searchInformed search:Use heuristics to guide the search•Best first•A*•Heuristics•Hill-climbing•Simulated annealingCS 561, Session 613Best-first search•Idea:use an evaluation function for each node; estimate of “desirability”expand most desirable unexpanded node.•Implementation:QueueingFn = insert successors in decreasing order of desirability•Special cases:greedy searchA* searchCS 561, Session 614Romania with step costs in kmCS 561, Session 615Greedy search•Estimation function:h(n) =


View Full Document

USC CSCI 561 - session06

Download session06
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view session06 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view session06 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?