大学计算机基础大学计算机基础 (38).ppt

Typical algorithm III:divide-and-conquer and backtrackingDivide-and-conquerThe basic idea of divide-and-conque is to divide a problem with scale of n into several smaller subproblems which are similar to the original problem,then solve these subproblems respectively,finally combine the results of each subproblem to get the solution of the whole problem.The divided subproblem is usually similar to the original problem,so the divide-and-conquer strategy can be used recursively to solve it.Example:find the position of integer x in an ascending order of N integers R n.Analysis:the integer sequence to be searched has been sorted in ascending order,using the method of binsearch.The basic idea is:the ordered data to be searched is divided into two subsets by the intermediate element,one of which is RL,the value of the element is less than or equal to the intermediate element,and the other is RH,the value of the element is more than or equal to the intermediate element.If the value of the intermediate element is equal to the given value x,the search is successful;if the value of the intermediate element is more than the given value x,do binsearch in the subset RL;otherwise,if the value of the intermediate element is less than the given value x,do binsearch in the subset RH.startinput digit groupoutputendQuestionWhat other questions are suitable for solving using divide-and-conquer?BacktrackingBacktracking is also called cut-and-try method.Its basic idea is:in the process of solving some problems,first select a possible situation to explore.When it is found that the tentative operations are not the best choice,it needs to go back a step(backtracking),and choose again to continue the tentative until the solution of the problem is found or the problem is proved to be unsolved.Analysis:place n queens on the n n chessboard,so that no one queen can directly capture other queens,that is,any two Queens can not be in the same row,the same column or the same diagonal.Example:using backtracking to solve the n queen problem.(1)First,check from the first place.If it cant be placed,then check the second position of the row.Check in turn until a place where a queen can be placed is found in the row.Then save the current status and go to the next row to repeat the retrieval of the above method.Natural language description of backtracking algorithm:assuming the current state of a row,check whether all positions of the row can put a queen.There are two retrieval states:(2)If no queen can be placed in all positions of the row after checking,it means that the position of the queen in the previous row cannot make all queens positionp proper,so it is necessary to go back to the previous row and recheck the position behind the Queens position.Backtracking Taking the four queens as an example,we can build a solution space tree,by exploring the solution space tree,we can get the possible solution of the four queens problem.Solution space treeSolution space treeQuestionWhat other typical cases?MazeDepth-First-Search of Graphs 0-1 Backpack