数据结构第六章第五节.ppt

《数据结构第六章第五节.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、6.7回溯法和树的遍历回溯的一般描述回溯法的基本框架应用举例6.7.1回溯的一般描述回溯法(Backtracking)“通用的解题法”基本原理：以“深度优先”的方式系统地“搜索”一个问题的一组解或所有解适用场合适合于求解组合数较大的问题问题的解必须能用一个n元组表示X=(x1,x2,…,xn),xiSi,(i=1,2,…n)mi=

2、Si

3、,(i=1,2,…n)求出使得规范函数P(x1,x2,…,xn)取极大值（或极小值或满足规范函数的约束条件）的所有向量应用条件（1）xi0即Si={所有非负实数}（2）xi=0或xi=1即Si={0,1}（3）lixi

4、ui即Si={a,liaui}显式约束可以与所求解的问题的实例I有关，也可以无关。满足显示约束的所有元组确定问题的一个“可能的”解空间显式约束：限定每个x只能从一个给定的集合上取值隐式约束：规定I的解空间中那些实际上满足规范函数的元组。隐式约束描述了xi必须“彼此相关”的情况约束条件例八皇后问题(i+1,j+1)(i+1,j)(i+1,j-1)(i,j+1)(i,j)(i,j-1)(i-1,j+1)(i-1,j)(i-1,j-1)N皇后问题QQQQQQQQ1234567812345678八皇后问题X=(x1,x2,…,x8)（2）显式约束条件：（1）问

5、题解表达式：Si={1,2,3,4,5,6,7,8},1i8（3）隐式约束条件：(xixj)&&(abs(xi-xj)abs(i-j))1i,j8（4）解空间：888！X=(4,6,8,2,7,6,3,5)?x1=1x2=2x2=4x2=33443x2=1x2=4x2=334x1=2244223324341311413x2=1x2=4x2=224x1=31413424131x2=1x2=3x2=223x1=413123231214皇后问题的状态空间树11xx212xxxx12x3123xxxx1xxx2123xxx123xx4x(1,1)(1,2

6、)(1,3)(1,4)(2,1)(2,2)(2,3)(2,4)(2,1)(2,2)(2,3)(2,4)(3,1)(3,2)(3,3)(3,4)(3,1)(3,2)(3,3)(3,4)(4,1)(4,2)(4,3)(4,4)(4,1)(4,2)(4,3)(3,1)并查集的树表示intBACKTRACK(n){//这是对回溯法控制流程的抽象描述。每个解都在x[1..n]中生成，一个解一//经确定就立即印出。在x[1],…x[k]已选定的情况下，T(x[1],…,x[k-1])给出//x[k]所有可能的取值。限界函数B(x[1],…x[k])判断哪些元素x[k]满

7、足隐式约//束条件k=1;while(k>0){if还剩有未检验过的x[k],使得x[k]T(x[1],…,x[k])andB(x[1],…,x[k])==TRUE{if(x[1],…,x[k])是一条已抵达答案结点的路径print(x[1],…x[k]);elsek=k+1;//考虑下一个集合}//ifelsek=k-1;//回溯到先前的集合}//while}//BACKTRACK并查集的树表示voidRBACKTRACK(k){//这是对回溯法控制流程的抽象地递归描述。进入算法时，解//向量X[1..n]的前k-1个分量x[1],…,x[k-1]已赋值

8、for满足下式的每个x[k]x[k]T(x[1],…,x[k])andB(x[1],…,x[k])==TRUE{if(x[1],…,x[k])是一条已抵达答案结点的路径print(x[1],…,x[k]);elseRBACKTRACK(k+1);}//for}//BACKTRACK置行计数i=1;放置第一个棋子，将棋子位置压入堆栈；while(i<=4){i++;在i行的适当位置放置一个棋子，检查位置的合法性；if位置合法，then将棋子位置压入堆栈；else{while(栈不空){删除栈顶元素；i--;在第i行重试下一个合法位置；if找到一个合法位置，t

9、hen{将新位置压入堆栈;break；}}//while((栈不空))}//else}//while(i<=4)四皇后四皇后voidplace(inti,intn){//进入本函数时，在nxn棋盘前i-1行已放置了互不攻击的i-1个棋子//现从第i行起继续为后续棋子选择合适位置//当(i>n)时，求得一个合法布局，输出之if(i>n)输出棋盘的当前布局；//n为4时，即为4皇后问题elsefor(j=1;j<=n;++j){在第i行第j列放置一个棋子；if(当前布局合法)place(i+1,n);移走第i行第j列的棋子；}}//place四皇后voidpla

10、ce(inti,intn){//进入本函数时，在nx