CSC 411 1st Edition Lecture 5 Outline of Last Lecture I. Problem Solving by Searchinga. Searchb. What is a problem?c. Goal testingOutline of Current Lecture I. Graph Searcha. Graph Search Problemi. Path searchii. Configuration searchCurrent LectureGraphical representation of a search problem- Typical example: route findingo Map corresponds to the graph, nodes to cities, links valid moves via available connectionsGraph Search- Tile puzzle: find a sequence of moves from the initial configuration to the goal configurationo Nodes correspond to states of the gameo Links to valid moves made by the playerGraph Search Problem- Search problems that can be often represented or converted into a graph search problem:o Initial state: state (configuration) we want to start search from (e.g. start city, initial game positiono Operators: transform one state to another (e.g. valid connections between cities,valid moves in tile puzzle)o Goal condition: defines the target state (destination, winning position)o Search space: is now defined indirectly through initial state + operatorsThese notes represent a detailed interpretation of the professor’s lecture. GradeBuddy is best used as a supplement to your own notes, not as a substitute.Two Types of Graph Search Problems- Path searcho Find a path between states S and T (e.g. traveling salesman, tile puzzle)o Additional goal criterion: minimum length (cost) path- Configuration search (constraint satisfaction search)o Find a state (configuration) satisfying the goal condition (e.g. n-queens problem)o Additional goal criterion: “soft” preferences for configurations, e.g. minimum cost designEven better solution to the N-Queens Problem- Smaller search spaceo Operators: add a queen to the leftmost unoccupied column such that it does not attack already placed queensSearch process- Exploration of the state space through successive application of operators from the initial state- Search tree = structure representing the exploration traceo Is built on-line during the processo Branches correspond to explored paths, and leaf nodes to the exploration