New version page

Pitt CS 1571 - Problem solving by searching

Upgrade to remove ads
Upgrade to remove ads
Unformatted text preview:

1CS 1571 Intro to AIM. HauskrechtCS 1571 Introduction to AILecture 3Milos [email protected] Sennott SquareProblem solving by searchingCS 1571 Intro to AIM. HauskrechtCourse administriviaInstructor: Milos Hauskrecht5329 Sennott [email protected]: Swapna Somasundaran5422 Sennott [email protected] web page:http://www.cs.pitt.edu/~milos/courses/cs1571/2CS 1571 Intro to AIM. HauskrechtSolving problems by searching• Some problems have a straightforward solution– Just apply the formula, or follow a standardized procedureExample: solution of the quadratic equation– Hardly a sign of intelligence• More interesting problems require search:– more than one possible alternative needs to be explored before the problem is solved – the number of alternatives to search among can be very large, even infinite.CS 1571 Intro to AIM. HauskrechtSearch example: Traveler problem• Find a route from one city (Arad) to the other (Bucharest)3CS 1571 Intro to AIM. HauskrechtExample. Puzzle 8.• Find the sequence of the empty tile moves from the initial game position to the designated target position Initial position Goal positionCS 1571 Intro to AIM. HauskrechtExample. N-queens problem.Find a configuration of n queens not attacking each otherA goal configurationA bad configuration4CS 1571 Intro to AIM. HauskrechtA search problemis defined by:• A search space:– What is it?• A goal conditionCS 1571 Intro to AIM. HauskrechtA search problemis defined by:• A search space:– What is it?– A set of objects among which we search for the solution. – What is the search space for the puzzle 8 problem?• A goal condition5CS 1571 Intro to AIM. HauskrechtA search problemis defined by:• A search space:– What is it?– A set of objects among which we search for the solution. – What is the search space for the puzzle 8 problem?– A sequence of moves. • A goal condition– Give an example of a goal condition for the map problem.CS 1571 Intro to AIM. HauskrechtA search problemis defined by:• A search space:– What is it?– A set of objects among which we search for the solution. – What is the search space for the puzzle 8 problem?– A sequence of moves. • A goal condition– Give an example of a goal condition for the map problem.– A path from A to B.– The shortest path from A to B.6CS 1571 Intro to AIM. HauskrechtSearch• Search (process)– The process of exploration of the search space• The efficiency of the search depends on:– The search space and its size– Method used to explore (traverse) the search space– Condition to test the satisfaction of the search objective(what it takes to determine I found the desired goal object)• Important to remember !!!– Conveniently chosen search space and the exploration policy can have a profound effect on the efficiency of the solutionCS 1571 Intro to AIM. HauskrechtGraph search• Many search problems can be naturally represented as graph search problems• Typical example: Route finding– Map corresponds to the graph, nodes to cities, links to available connections between cities– Goal: find a route (path) in the graph from S to TstarttargetSTABCDEFGHIJKL7CS 1571 Intro to AIM. HauskrechtGraph search• Less obvious conversion:Puzzle 8. Find a sequence of moves from the initial configuration to the goal configuration.– nodes corresponds to states of the game, – links to valid moves made by the playerstarttargetCS 1571 Intro to AIM. HauskrechtSearch problemSearch problems that can be represented or converted into a graph search problems can be defined in terms of: • Initial state– State (configuration) we start to search from (e.g. start city, initial game position)• Operators: – Transform one state to another (e.g. valid connections between cities, valid moves in Puzzle 8)• Goal condition: – Defines the target state (destination, winning position)• Search space (the set of objects we search for the solution) :– is now defined indirectly through: the initial state + operators8CS 1571 Intro to AIM. HauskrechtGraph search problem• States - game positions, or locations in the map that are represented by nodes in the graph• Operators - connections between cities, valid moves• Initial state – start position, start city• Goal state – target position (positions), target city (cities)starttargetSTABCDEFGHIJKLCS 1571 Intro to AIM. HauskrechtN-queensSome problems can be converted to the graph search problems• But some problems are harder and less intuitive– Take e.g. N-queens problem.• Problem: – We look for a configuration, not a sequence of moves– No distinguished initial state, no operators (moves) Goal configuration9CS 1571 Intro to AIM. HauskrechtN-queensHow to choose the search space for N-queens?• Ideas? CS 1571 Intro to AIM. HauskrechtN-queensHow to choose the search space for N-queens?• Ideas? Search space:– all configurations of N queens on the board• Can we convert it to a graph search problem?• We need states, operators, initial state and goal condition. …..…goalinitial10CS 1571 Intro to AIM. HauskrechtN-queensSearch space:– all configurations of N queens on the board• Can we convert it to a graph search problem?• We need states, operators, initial state and goal state. …goalinitialStates are: N-queen configurationsInitial state: ?Operators (moves)?CS 1571 Intro to AIM. HauskrechtN-queensSearch space:– all configurations of N queens on the board• Can we convert it to a graph search problem?• We need states, operators, initial state and goal condition. …goalsinitialInitial state: an arbitrary N-queen configurationOperators (moves): change a position of one queen11CS 1571 Intro to AIM. HauskrechtN-queensIs there an alternative way to formulate the N-queens problem as a search problem?• Ideas? CS 1571 Intro to AIM. HauskrechtN-queensIs there an alternative way to formulate the N-queens problem as a search problem?• Search space: configurations of 0,1,2, … N queens• Graph search: – States configurations of 0,1,2,…N queens– Operators: additions of a queen to the board– Initial state: 0 queens on the boardstart12CS 1571 Intro to AIM. HauskrechtstartTarget 1Graph searchA trick: generate a configuration step by step (one queen per step)• States (nodes) correspond to configurations of 0,1,2,3,4 queens• Links (operators) correspond to the addition of a queen• Initial state: no queens placed on


View Full Document
Download Problem solving by searching
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 Problem solving by searching 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 Problem solving by searching 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?