Algorithms and Data Structures - 会津大学公式 ...

1 1/1 Algorithms and data Structures13th Lecture: Heuristic SearchYutaka Watanobe, Jie Huang, Yan Pei,Wenxi Chen, Qiangfu Zhao, Wanming ChuUniversity of AizuLast Update: 2020/12/1Y. Watanobe, J. Huang, Y. Pei, W. Chen, Q. Zhao, W. ChuUniversity of AizuAlgorithms and data First SearchBreadth First SearchIterative DeepeningIDA*A*Y. Watanobe, J. Huang, Y. Pei, W. Chen, Q. Zhao, W. ChuUniversity of AizuAlgorithms and data (1)Some problems involved searching through a vast number ofpotential solutions to find an algorithm starts from the initial point and searches forward oncertain paths to find the goal (solution).

2 For some of the problems, we know there is asuccess searchpaththat definitely leads to the such kind of problems, we can design Algorithms whichsearch the solutions on the success Watanobe, J. Huang, Y. Pei, W. Chen, Q. Zhao, W. ChuUniversity of AizuAlgorithms and data (2)On the other hand, there are many problems for which we do notknow which paths lead to the way to solve these problems is to exhaustively search everypossible , there may be too many possible paths to search is related to a great number of operations. So,we need some techniques to bound the number of possiblepaths to increase the search Watanobe, J.

3 Huang, Y. Pei, W. Chen, Q. Zhao, W. ChuUniversity of AizuAlgorithms and data (1)Backtrackingis a systematic way to go through all the possibleconfigurations of a search space (all the possible paths).In backtracking search , when we know we can not go forwardanymore on some possible path, we go backward to find is an example of backtracking Watanobe, J. Huang, Y. Pei, W. Chen, Q. Zhao, W. ChuUniversity of AizuAlgorithms and data (2)Backtracking is quite widely applicable as generalproblem-solving example, they form the basis for many programs that playgames such as this case, a partial solution is some legal positioning of all thepieces on the board, and the descendant of a node in theexhaustive search tree is a position that can be the result ofsome legal backtracking search is typically done with quite sophisticatedpruning rules so that only interesting positions are search techniques are also used for otherapplications in artificial Watanobe, J.

4 Huang, Y. Pei, W. Chen, Q. Zhao, W. ChuUniversity of AizuAlgorithms and data Queens Problem (1)Backtracking technique can be used to solve the classic eightqueens problem:put eight queens on a chess-board such that none of themthreatens any of others (a queen threatens the squares in thesame row, in the same column, or on the same diagonals).012345670 1 2 3 4 5 6 7Y. Watanobe, J. Huang, Y. Pei, W. Chen, Q. Zhao, W. ChuUniversity of AizuAlgorithms and data Queens Problem (2)An obvious way to solve this problem consists of trying all theways of placing eight queens on a chess-board, checking eachtime to see whether a solution has been approach is of no practical use, since the number ofpossible positions we have to check would be:(648)=4;426;165;368 Can we do it better?

5 Y. Watanobe, J. Huang, Y. Pei, W. Chen, Q. Zhao, W. ChuUniversity of AizuAlgorithms and data Queens Problem (3)First, we know that two queens can not be in the same row. So,eight queens should be put in eight rows, one queen in one each queen has 8 positions to put in the row, there are88=16;777;216 positions. Similarly, two queens can not be inthe same , if the queen in the first row has been put in theith column,the other queens can not be in theith this, we can reduce the possible positions to 8!=40; Watanobe, J. Huang, Y. Pei, W. Chen, Q.

6 Zhao, W. ChuUniversity of AizuAlgorithms and data for 8 Queens Problem (1)Backtracking allows us to do much better than the above. Usinga recursive call, we can realize a backtracking algorithm for eightqueens problem as follows:We put the queen of the first row at any position of the we put the queen of the second row to a position of the rowthat is not threatened by the queen of the first Watanobe, J. Huang, Y. Pei, W. Chen, Q. Zhao, W. ChuUniversity of AizuAlgorithms and data for 8 Queens Problem (2)Assume, we have putiqueens in the firstirows such that noneof them threatens any of others.

7 We put the queen of the (i+ 1)throw to a position of the row that is not threatened by any of we can not find such a position for the queen of the (i+1)throw, we go back to theith row to find another non-threatenedposition for the queen of theith row (if no such position exists wego back further to (i-1)th row) and then try Watanobe, J. Huang, Y. Pei, W. Chen, Q. Zhao, W. ChuUniversity of AizuAlgorithms and data (1)Assume the rows, columns, and diagonals of chess-board isdefined as in the next Figure:012345670 1 2 3 4 5 6 7ij012345670 1 2 3 4 5 6 7ij012345670 1 2 3 4 5 6 7row: x = icol: x = jY.

8 Watanobe, J. Huang, Y. Pei, W. Chen, Q. Zhao, W. ChuUniversity of AizuAlgorithms and data (2)Assume the rows, columns, and diagonals of chess-board isdefined as in the next Figure:ij012345670 1 2 3 4 5 6 7j8 9 10 11 12 13 140123456714 13 12 11 10 9 8idpos: x = i + jdneg: x = i - j + (N - 1)01234567012345670 1 2 3 4 5 6 7Y. Watanobe, J. Huang, Y. Pei, W. Chen, Q. Zhao, W. ChuUniversity of AizuAlgorithms and data (3)We use a 1 8 integer array row[8] to express the positions ofthe queens at each row. That is, row[0], row[1].

9 , row[7] areused to keep the positions (column) of queens in the row 0, 1, ..,7, , we use a 1 8 integer array col[8] to show if each positionof a given row is threatened by a queen in the same a given rowi, col[j] ==freemeans there is no queen in thejth column, otherwise a queen has been put in the same columnand we can not put the queen of the given row at thejth Watanobe, J. Huang, Y. Pei, W. Chen, Q. Zhao, W. ChuUniversity of AizuAlgorithms and data (4)We also have to consider the threatens from the queens on thesame shown in the Figure there are 15 positive diagonals (at 45degrees) and 15 negative diagonals (at 135 degrees).

10 We use two other arrays dpos[15] and dneg[15] to denote if aposition is threatened by a queen on the same positive diagonaland negative diagonal, [x] ==freemeans that there is no queen on the diagonalwith numberx, otherwise there is a queen on define dneg[x].Y. Watanobe, J. Huang, Y. Pei, W. Chen, Q. Zhao, W. ChuUniversity of AizuAlgorithms and data (5)When we have a queen at the position p[i][j] (theith row and thejth column), we know that the positions on the positive diagonali+jand the positions on the negative diagonali j+(N 1),whereNis the size of chess-board (8 in 8-queens problem), arethreatened by this , when we have put a queen at the position p[i][j], we setdpos[i+j] and dneg[i j+n 1] to Watanobe, J.