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

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

1、6.7回溯法和树的遍历回溯的一般描述回溯法的基本框架应用举例Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.6.7.1回溯的一般描述回溯法(Backtracking)“通用的解题法”基本原理：以“深度优先”的方式系统地“搜索”一个问题的一组解或所有解适用场合适合于求解组合数较大的问题Evaluationonly.CreatedwithAspose.Slidesfor.NET3.

2、5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.问题的解必须能用一个n元组表示X=(x1,x2,…,xn),xiSi,(i=1,2,…n)mi=

3、Si

4、,(i=1,2,…n)求出使得规范函数P(x1,x2,…,xn)取极大值（或极小值或满足规范函数的约束条件）的所有向量应用条件Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyL

5、td.（1）xi0即Si={所有非负实数}（2）xi=0或xi=1即Si={0,1}（3）lixiui即Si={a,liaui}显式约束可以与所求解的问题的实例I有关，也可以无关。满足显示约束的所有元组确定问题的一个“可能的”解空间显式约束：限定每个x只能从一个给定的集合上取值隐式约束：规定I的解空间中那些实际上满足规范函数的元组。隐式约束描述了xi必须“彼此相关”的情况约束条件Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.C

6、opyright2004-2011AsposePtyLtd.例八皇后问题(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皇后问题Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.QQQQQQQQ1234567812345678八皇后问题X=(x1,x2,…,x8)（2）显式约束条件：（1）

7、问题解表达式：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)?Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.x1=1x2=2x2=4x2=33443x2=1x2=4x2=334x1=224422332434131141

8、3x2=1x2=4x2=224x1=31413424131x2=1x2=3x2=223x1=413123231214皇后问题的状态空间树Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.11xx212xxxx12x3123xxxx1xxx2123xxx123xx4x(1,1)(1,2)(1,3)(1,4)(2,1)(2,2)(2,3)(2,4)(2,1)(2,2)(2,3)(2,

9、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)Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.并查集的树表示intBACKTRACK(n){//这是对回溯法控制流程的抽象描述。每个解都在x[1..n]中生成，一个解一//经确定就立即印出。在x[1],…x[k]已

10、选定的情况下，T(x[1],…,x[k-1])给出//x[k]所有可能的取值。限界函数B(x[1],…x[k])判断哪些元素x[k]满足隐式约//束条件k=1;while(k>0){if还剩有未检验过的x[k],使得x[k]T(x[1],…,x[k])andB