资源描述：
《第六讲-回溯法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、算法设计与分析第六讲回溯法算法设计与分析第六讲回溯法主要内容回溯法基本要素回溯算法的设计思想回溯算法的设计过程回溯算法的设计实例重点回溯算法的设计思想和设计过程难点针对具体问题的回溯算法算法设计与分析第六讲回溯法6.1回溯法（backtracking）基础一、适用范围需要搜索一个或一组解满足约束条件的最优解问题的解用向量表示X=(x1,x2,…,xn)算法设计与分析第六讲回溯法求一个或一组满足约束条件的解向量X=(x1,x2,…,xn)隐式约束条件B(x1,x2,…,xn)显式约束条件xi∈Si,
2、Si
3、=mi，1≤i≤n算法设计与分析第六讲
4、回溯法二、基本动机1)逐级扩展解向量2)动态测试部分解用Bi(x1，x2，…，xi-1，xi=a)动态测试，判定路径x1x2…xi-1xi=a是否可行。x1，x2，…，xi-1xi算法设计与分析第六讲回溯法三、问题举例例6.18皇后问题。123456781Q2Q3Q4Q5Q6Q7Q8Q解的表示：X=(x1,x2,…,x8)显式约束:xi∈Si，1≤i≤8，Si={1,2,3,4,5,6,7,8}隐式约束：任何两个皇后不能相互攻击解空间大小：穷举法88，回溯法8!算法设计与分析第六讲回溯法例6.2子集和数问题。已知n个正数，即W=(w1,w2,
5、…,wn)，求wi的和数为M的所有子集。例如，W=(w1,w2,w3,w4)=(11,13,24,7),M=31满足条件的子集：(11,13,7),(24,7)向量表示：(1,2,4),(3,4)解向量的k元组变长表示：(x1,x2,…,xk)，要求xi≤xi+1解向量的n元组定长表示：(x1,x2,…,xn)，xi∈{0,1}算法设计与分析第六讲回溯法6.2回溯算法设计算法设计与分析第六讲回溯法解向量：由根节点到叶节点的路径所定义45673910111281415161713220212223192526272824303132332918
6、36373839354142434440464748494534525354555157585960566263646561501x1x2x3x41234234134124123342423341413241412231312434232434131424121323121例6.34皇后问题的解空间树结构。一、解空间的树结构表示算法设计与分析第六讲回溯法树中的节点：求解过程的一个状态树中的边：标示xi的一个可能的值解向量：由根节点到任意叶节点的路径定义解空间：由根节点到所有叶节点的路径定义特点算法设计与分析第六讲回溯法例6.4n=4的子集和数
7、问题的解空间树结构。1)解向量长度可变的树结构解向量，解空间的定义？12786131214163910154115x1x2x3x4123423434434444算法设计与分析第六讲回溯法2)解向量长度固定的树结构26303127282918220242521222319121617131415436101178951x1x2x3x4101111111111111100000000000000解向量，解空间的定义？算法设计与分析第六讲回溯法二、解空间树的状态描述问题状态状态空间解状态答案状态状态空间树算法设计与分析第六讲回溯法三、回溯法的抽象描
8、述1)根据问题特点设计状态空间树基本任务2)逐个地生成问题状态3)确定问题状态是否是解状态4)确定解状态是否是答案状态算法设计与分析第六讲回溯法1)活节点1)回溯法:使用规范函数杀死活节点的深度优先生成法状态空间树的三类节点状态空间树的生成方法2)E节点3)死节点2)分支限界法:E节点一直保持到死的生成方法(宽度优先,D检索)算法设计与分析第六讲回溯法皇后问题的回溯法求解过程13x2=28x2=313x2=49x3=211x3=414x3=216x3=315x4=318x1=219x2=124x2=329x2=430x3=131x4=3kil
9、ledkilledkilled,backkilled,backkilled,backkilledkilledoutput,back30x3=3killed,back2x1=1算法设计与分析第六讲回溯法算法的抽象描述(x1,x2,…,xi-1)：由根节点到某个节点的一条子路径Si:xi的值的集合Bi(x1,x2,…,xi)：动态规范函数,如果路径(x1,x2,…,xi)不可能延伸至一个答案节点,取假值,否则,取真值解向量中xi的值：Si中使Bi(x1,x2,…,xi)为真的部分算法设计与分析第六讲回溯法非递归算法BackTracking1(in
10、tn){inti=1;while(i>0){for(xi∈Si)if(Bi(x1,x2,…,xi)==TRUE){if((x1,x2,…,xi)已抵达答案节点)pr
