Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
State space search includes State space of the 8-puzzle, State space of tic-tac-toe, Search Strategies, Breadth-first search of the 8-puzzle, Depth first search, Iterative Deepening. | 16/03/2016 State space search anhtt-fit@mail.hut.edu.vn State Space Search Define problem in form of a state space and use a search algorithm to find a solution The problem space consists of: a state space which is a set of states representing the possible configurations of the world a set of operators which can change one state into another The problem space can be viewed as a graph where the states are the nodes and the arcs represent the operators. 1 16/03/2016 State space of the 8-puzzle Size of search space: 8/16-puzzle 8-puzzle: 8! = 40,320 different states 16-puzzle: 16! =20,922,789,888,000 ≈ 1013 different states Game works by moving tiles Simplification: assume only blank tile is moved Legal moves: blank up, down, left, right Keep blank tile on board State space consists of two disconnected subgraphs 2 16/03/2016 State space of tic-tac-toe Size of search space: tic-tac-toe Start is empty board Goal is board with 3 Xs in a row, column or diagonal Path from start to end gives a series of moves in a winning game Vocabulary is (blank, X, O) 39 = 19,683 ways to arrange (blank, X, O) in 9 spaces No cycles possible: why? Represented as DAG (directed acyclic graph) 9! = 362,880 different paths can be generated: why? 3 16/03/2016 Search Strategies Traverse the graph from an initial state to find a goal Alternative search strategies: Depth-first: visit children before siblings (= alg. backtrack) Breadth-first: visit graph level-by-level Best-first: order unvisited nodes through heuristic, finding best candidate for next step Breadth-First search 4 16/03/2016 Breadth-first search of the 8-puzzle Goal Quiz 1 Write a program to print out solutions for the 8puzzle game using the BFS algorithm. Question to solve: How to represent a state of 8-puzzle game in memory? How to compare two states? How to generate sub-states from a state? How to store states in two collections (open and closed)? How to print a state in the .
