CS 561, Sessions 8-91Administrativia • Assignment 1 due tuesday 9/24/2002 BEFORE midnight• Midterm exam 10/10/2002CS 561, Sessions 8-92Last 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:• Greedy search – queue first nodes that maximize heuristic “desirability” based on estimated path cost from current node to goal;•A* search –queue first nodes that maximize sum of path cost so far and estimated path cost to goal.• Iterative improvement – keep no memory of path; work on a single current state and iteratively improve its “value.”• Hill climbing – select as new current state the successor state which maximizes value.• Simulated annealing – refinement on hill climbing by which “bad moves” are permitted, but with decreasing size and frequency. Will find global extremum.CS 561, Sessions 8-93Exercise: Search AlgorithmsThe following figure shows a portion of a partially expanded search tree. Each arc between nodes is labeled with the cost of the corresponding operator, and the leaves are labeled with the value of the heuristic function, h.Which node (use the node’s letter) will be expandednext by each of the following search algorithms?(a) Depth-first search(b) Breadth-first search(c) Uniform-cost search(d) Greedy search(e) A* search5D5AC541963h=15BF GEh=8h=12h=10 h=10h=18Hh=20h=14CS 561, Sessions 8-94Depth-first searchNode queue: initialization# state depth path cost parent #1A00--CS 561, Sessions 8-95Depth-first searchNode queue: add successors to queue front; empty queue from top# state depth path cost parent #2B1313C 1 19 14D1511A00--CS 561, Sessions 8-96Depth-first searchNode queue: add successors to queue front; empty queue from top# state depth path cost parent #5E2726F2827G2828H2922B1313C 1 19 14D1511A00--CS 561, Sessions 8-97Depth-first searchNode queue: add successors to queue front; empty queue from top# state depth path cost parent #5E2726F2827G2828H2922B1313C 1 19 14D1511A00--CS 561, Sessions 8-98Exercise: Search AlgorithmsThe following figure shows a portion of a partially expanded search tree. Each arc between nodes is labeled with the cost of the corresponding operator, and the leaves are labeled with the value of the heuristic function, h.Which node (use the node’s letter) will be expandednext by each of the following search algorithms?(a) Depth-first search(b) Breadth-first search(c) Uniform-cost search(d) Greedy search(e) A* search5D5AC541963h=15BF GEh=8h=12h=10 h=10h=18Hh=20h=14CS 561, Sessions 8-99Breadth-first searchNode queue: initialization# state depth path cost parent #1A00--CS 561, Sessions 8-910Breadth-first searchNode queue: add successors to queue end; empty queue from top# state depth path cost parent #1A00--2B1313C 1 19 14D151CS 561, Sessions 8-911Breadth-first searchNode queue: add successors to queue end; empty queue from top# state depth path cost parent #1A00--2B1313C 1 19 14D1515E2726F2827G2828H292CS 561, Sessions 8-912Breadth-first searchNode queue: add successors to queue end; empty queue from top# state depth path cost parent #1A00--2B1313C 1 19 14D1515E2726F2827G2828H292CS 561, Sessions 8-913Exercise: Search AlgorithmsThe following figure shows a portion of a partially expanded search tree. Each arc between nodes is labeled with the cost of the corresponding operator, and the leaves are labeled with the value of the heuristic function, h.Which node (use the node’s letter) will be expandednext by each of the following search algorithms?(a) Depth-first search(b) Breadth-first search(c) Uniform-cost search(d) Greedy search(e) A* search5D5AC541963h=15BF GEh=8h=12h=10 h=10h=18Hh=20h=14CS 561, Sessions 8-914Uniform-cost searchNode queue: initialization# state depth path cost parent #1A00--CS 561, Sessions 8-915Uniform-cost searchNode queue: add successors to queue so that entire queue is sorted by path cost so far; empty queue from top# state depth path cost parent #1A00--2B1313D1514C 1 19 1CS 561, Sessions 8-916Uniform-cost searchNode queue: add successors to queue so that entire queue is sorted by path cost so far; empty queue from top# state depth path cost parent #1A00--2B1313D1515E2726F2827G2828H2924C 1 19 1CS 561, Sessions 8-917Uniform-cost searchNode queue: add successors to queue so that entire queue is sorted by path cost so far; empty queue from top# state depth path cost parent #1A00--2B1313D1515E2726F2827G2828H2924C 1 19 1CS 561, Sessions 8-918Exercise: Search AlgorithmsThe following figure shows a portion of a partially expanded search tree. Each arc between nodes is labeled with the cost of the corresponding operator, and the leaves are labeled with the value of the heuristic function, h.Which node (use the node’s letter) will be expandednext by each of the following search algorithms?(a) Depth-first search(b) Breadth-first search(c) Uniform-cost search(d) Greedy search(e) A* search5D5AC541963h=15BF GEh=8h=12h=10 h=10h=18Hh=20h=14CS 561, Sessions 8-919Greedy searchNode queue: initialization# state depth path cost total parent #cost to goal cost1A002020--CS 561, Sessions 8-920Greedy searchNode queue: Add successors to queue, sorted by cost to goal.# state depth path cost total parent #cost to goal cost1A002020--2B13141713D15152014 C 1 1918371Sort keyCS 561, Sessions 8-921Greedy searchNode queue: Add successors to queue, sorted by cost to goal.# state depth path cost total parent #cost to goal cost1A002020--2B13141715G2881627E27101726H29101928F28122023D15152014 C 1 1918371CS 561, Sessions 8-922Greedy searchNode queue: Add successors to queue, sorted by cost to goal.# state depth path cost total parent #cost to goal cost1A002020--2B13141715G2881627E27101726H29101928F28122023D15152014 C 1 1918371CS 561, Sessions 8-923Exercise: Search AlgorithmsThe following figure shows a portion of a partially expanded search tree. Each arc between nodes is labeled with the cost of the corresponding operator, and the leaves are labeled with the value of the heuristic function, h.Which node (use the node’s letter) will be expandednext by each of the following search algorithms?(a) Depth-first search(b) Breadth-first search(c) Uniform-cost search(d) Greedy search(e) A* search5D5AC541963h=15BF GEh=8h=12h=10 h=10h=18Hh=20h=14CS 561, Sessions 8-924A* searchNode queue: initialization# state depth path
View Full Document
Unlocking...