DOC PREVIEW
Penn CIT 594 - State Space Searches

This preview shows page 1-2-20-21 out of 21 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 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 21 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 21 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 21 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

State-Space SearchesState spacesExample 1: MazeExample 2: The 15-puzzleExample 3: Missionaries and cannibalsStatesOperationsThe state spaceExample 3, revisitedState-space searchingThe basic search algorithmHeuristic searchingHeuristicsBest-first searchingIterative deepeningThe A* algorithmThe A* formula: f(N) = g(N) + h(N)How good is A*?IDA*ConclusionThe EndState-Space Searches2State spacesA state space consists ofA (possibly infinite) set of statesThe start state represents the initial problemEach state represents some configuration reachable from the start stateSome states may be goal states (solutions)A set of operatorsApplying an operator to a state transforms it to another state in the state spaceNot all operators are applicable to all statesState spaces are used extensively in Artificial Intelligence (AI)3Example 1: MazeA maze can be represented as a state spaceEach state represents “where you are” in the mazeThe start state represents your starting positionThe goal state represents the exit from the mazeOperators (for a rectangular maze) are: move north, move south, move east, and move westEach operator takes you to a new state (maze location)Operators may not always apply, because of walls in the maze4Example 2: The 15-puzzleThe start state is some (almost) random configuration of the tilesThe goal state is as shownOperators areMove empty space upMove empty space downMove empty space rightMove empty space leftOperators apply if not against edge 3 10 13 7 9 14 6 1 4 15 2 11 8 5 12Start state: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Goal state:5Example 3: Missionaries and cannibalsAn old puzzle is the “Missionaries and cannibals” problem (in various guises)The missionaries and cannibals wish to cross a riverThey have a canoe that can hold two peopleIt is unsafe to have cannibals outnumber missionariesMMMCCCInitial stateMMMCCCGoal state6StatesA state can be represented by the number of missionaries and cannibals on each side of the riverInitial state: 3m,3c,canoe / 0m,0cGoal state: 0m,0c / 3m,3c,canoeWe assume that crossing the river is a simple procedure that always works (so we don’t have to represent the canoe being in the middle of the river)However, this is redundant; we only need to represent how many missionaries/cannibals are on one side of the riverInitial state: 3m,3c,canoeGoal state: 0m,0c7OperationsAn operation takes us from one state to anotherHere are five possible operations:Canoe takes 1 missionary across river (1m)Canoe takes 1 cannibal across river (1c)Canoe takes 2 missionaries across river (2m)Canoe takes 2 cannibals across river (2c)Canoe takes 1 missionary and 1 cannibal across river (1m1c)We don’t have to specify “west to east” or “east to west” because only one of these will be possible at any given time8The state space3m, 2c3m, 1c2m, 3c1m, 3c2m, 2c1m2m2c1m1c1c1c3m, 2c,canoe2m, 3c,canoe1m1m1c3m, 3c,canoeetc.etc.etc.etc.9Example 3, revisited3 missionaries, 3 cannibals, 1 canoeThe canoe can hold at most two peopleCannibals may never outnumber missionaries (on either side)Initial state is (3, 3, 1), representing the number of missionaries, cannibals, boats on the initial sideThe goal state is (0, 0, 0)Operators are addition or subtraction of the vectors (1 0 1), (2 0 1), (0 1 1), (0 2 1), (1 1 1)Operators apply if result is between (0 0 0) and (3 3 1)10State-space searchingMost problems in AI can be cast as searches on a state spaceThe space can be tree-shaped or graph-shapedIf a graph, need some way to keep track of where you have been, so as to avoid loopsThe state space is often very, very largeWe can minimize the size of the search space by careful choice of operatorsExhaustive searches don't work—we need heuristics11The basic search algorithm Initialize: put the start node into OPEN while OPEN is not empty take a node N from OPEN if N is a goal node, report success put the children of N onto OPEN Report failureIf OPEN is a stack, this is a depth-first searchIf OPEN is a queue, this is a breadth-first searchIf OPEN is a priority queue, sorted according to most promising first, we have a best-first search12Heuristic searchingAll the previous searches have been blind searchesThey make no use of any knowledge of the problemIf we know something about the problem, we can usually do much, much betterExample: 15-puzzleFor each piece, figure out how many moves away it is from its goal position, if no other piece were in the wayThe total of these gives a measure of distance from goalThis is a heuristic measure13HeuristicsA heuristic is a rule of thumb for deciding which choice might be bestThere is no general theory for finding heuristics, because every problem is differentChoice of heuristics depends on knowledge of the problem space14Best-first searchingUse the same basic search algorithmChoose from OPEN the “best” node, that is, the one that seems to be closest to a goalGenerally, even very poor heuristics are significantly better than blind search, but...No guarantee that the best path will be foundNo guarantee on the space requirements15Iterative deepening Set LIMIT to zero do forever Do a depth-first search up to LIMIT levels deep If a goal is found, return success, else add 1 to LIMITEach time through the loop we start all over!If we find a path, it will be a shortest possible pathOnly requires linear space, because it only uses DFSIncreased time requirements are only linear16The A* algorithmSuppose:You keep track of the distance g(N) that each node N that you visit is from the start state You have some heuristic function, h(N), that estimates the distance between node N and a goalThen:f(N) = g(N) + h(N) gives you the (partially estimated) distance from the start node to a goal nodeThe A* algorithm is: choose from OPEN the node N with the smallest value of f(N)17The A* formula: f(N) = g(N) + h(N)g(N) is the (known) distance from start to Nh(N) is the (estimated) distance from N to a goalf(N) is just the sum of thesef(N) is our best guess as to the distance from start to a goal, passing through NstartNgoalf(N)g(N)h(N)18How good is A*?Memory usage depends on the heuristic functionIf h(N) =


View Full Document

Penn CIT 594 - State Space Searches

Documents in this Course
Trees

Trees

17 pages

Searching

Searching

24 pages

Pruning

Pruning

11 pages

Arrays

Arrays

17 pages

Stacks

Stacks

30 pages

Recursion

Recursion

25 pages

Hashing

Hashing

24 pages

Recursion

Recursion

24 pages

Graphs

Graphs

25 pages

Storage

Storage

37 pages

Trees

Trees

21 pages

Arrays

Arrays

24 pages

Hashing

Hashing

24 pages

Recursion

Recursion

25 pages

Graphs

Graphs

23 pages

Graphs

Graphs

25 pages

Stacks

Stacks

25 pages

Recursion

Recursion

25 pages

Quicksort

Quicksort

21 pages

Quicksort

Quicksort

21 pages

Graphs

Graphs

25 pages

Recursion

Recursion

25 pages

Searching

Searching

24 pages

Counting

Counting

20 pages

HTML

HTML

18 pages

Recursion

Recursion

24 pages

Pruning

Pruning

11 pages

Graphs

Graphs

25 pages

Load more
Download State Space Searches
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 State Space Searches 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 State Space Searches 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?