数据结构与算法 超越算法能力的极限ppt课件.ppt

《数据结构与算法 超越算法能力的极限ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第9章超越算法能力的极限概述状态空间树搜索：FIFO,LIFO回溯（Backtracking）n皇后子集和图着色哈密顿回路分支界限（BranchandBound）15-puzzle0-1背包本章习题概述概述本章介绍：回溯法、分支界限法两种算法都是对穷举搜索的改进。与穷举不同，每次构造候选解的一个部分解。然后，据设定的评估准则评估这个部分解是否有前途：YES：构造下一步部分解。NO：抛弃该部分解，生成、评估另一个部分解。如此继续，直到找到最终全解——各步部分解组成。在最坏情况下，仍不可避免穷举查找中遇到的

2、指数级组合爆炸问题，但这种方法使我们至少可以求解某些组合难题的更大实例。回溯、分支限界的算法过程用状态空间树的搜索来描述。节点是问题的一个状态。如果预见到当前节点的子孙节点不可能成为问题全解的一个部分解，两种方法都将停止处理该节点及子孙。两种方法的区别求解不同的问题，分支界限法只能用于最优问题。回溯法不受此限，通常处理非最优问题，它的节点搜索为深度优先（DFS），分支界限的节点搜索有多种方法。状态空间树的FIFO,LIFO,LC检索状态空间树搜索：FIFO,LIFO解空间：问题有多个解，所有解的集合。问

3、题有n个变量（输入规模），解向量Xk=(x1,...,xn)表示问题的解（包括不可行解）。例如：0-1背包问题，n=3：每个x取值为0或1共2n=8个解向量，解空间：{(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)}旅行商问题，顶点数n=3的完全图：每个x取值{1,2,3}，解空间：{(1,1,1),(1,1,2),(1,1,3),(1,2,1),(1,2,2),(1,2,3),...,(3,3,3)}共nn=33=27个解

4、向量。可用约束条件xk≠xm压缩解空间：{(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)}——n!解空间树（状态空间树）将问题的解空间用树来描述——解空间树。n=3的0-1背包解空间树（包括非可行解）(0,0,0)状态空间树举例1层2层3层最优解(1,0,0)根到叶的一条路径表示一个解向量Xk每条边表示一个解分量xi每一层构造一个解分量n=4节点完全图，旅行商问题的解空间树（可行解）(0,0,0,0)解空间树搜索的一般策略穷举搜索与解空间压缩——对整个解空

5、间（包括不可行解）进行穷举搜索。——利用约束条件和目标函数，对搜索过程进行评估和指导，以大大压缩搜索空间（剪枝）。活节点、死节点、e_节点活节点：不是叶节点，满足约束条件，使目标函数有所改善，儿子节点尚有未访问的（可继续搜索下去）。否则，死节点。e_节点：扩展节点，当前正在搜索的活节点。状态空间树的一般搜索过程从根开始搜索过程。当前e_节点，左→右判定子节点是否活节点？YES:存入活节点表，且把该边相应的解分量xi加入部分解。然后，从活节点表中取出下一个活节点作为e_节点，继续该过程。如果只要求找问题的

6、一个解，搜索到一个目标解即可。如果要求找问题的全部解，则搜索过程需进行到活节点表空为止。活节点表的存储结构决定了搜索方向。状态空间树的FIFO,LIFO搜索状态空间树搜索：FIFO,LIFO活节点表的存储结构决定搜索方向（BFS、DFS）栈：用栈存储活节点，LIFO(LastinFirstOut)搜索。DFS队列：队列存储活节点，FIFO(FirstinFirstOut)搜索。BFS12345671253467LIFO搜索过程FIFO搜索过程125说明：节点号表示搜索的顺序。LIFO访问节点顺序：1→2

7、→3→2→4→2→1→5→6→5→7→5→1活节点栈空：算法停止。活节点退栈：成为死节点时。123LIFO和FIFO搜索的缺陷LIFO和FIFO搜索的缺陷状态空间树很大时，两种搜索都不能很快到达答案节点，搜索过程带有盲目性。本例最佳搜索路线：1→18→29→30→31为提高搜索效率需改进搜索策略，后述分支界限法。B节点分支被剪除FIFO搜索完30节点后搜索32而非31圈内编号为LIFO圈外编号为FIFO回溯（Backtracking）回溯（Backtracking）——号称“通用解题法”剪枝函数回溯法搜

8、索的两种剪枝策略——避免无效搜索1.约束函数：在e_节点处剪去不满足约束条件的子树2.限界函数：剪去不能得到最优解的子树——这两类函数统称为剪枝函数。举例：0-1背包问题：用剪枝函数剪去导致不可行解的子树。旅行商问题：若从根到e_节点的部分路线费用超过前面已经找到的最低费用路线，则断定以这个e_节点为根的子树不可能产生最优解，因此，将该子树剪去。n皇后问题在一个n×n格棋盘上放n个皇后，使它们彼此不能攻击。国际象棋规则：一个皇后可攻击在同一