算法设计与分析ch7.ppt

7.1 Motivation of Tree Searching 7.2 Basic Tree Searching Strategies 7.3 Optimal Tree Searching Strategies 7.4 Personnel Assignment Problem 7.5 Traveling Salesperson Optimization Problem 7.6 The A* Algorithm  7.1 Motivation of Tree Searching 很多问题可以表示成为树. 于是, 这些问题可以使用树 有哪些信誉好的足球投注网站算法来求解 问题的定义 输入: n个布尔变量x1, x2, …., xn 关于x1, x2, …., xn的k个析取布尔式 输出: 是否存在一个x1, x2, …., xn的一种赋值 使得所有k个布尔析取式皆为真 把问题表示为树 通过不断地为赋值集合分类来建立树 (以三个变量(x1, x2, x3)为例) 问题的定义 输入: 具有8个编号小方块的魔方 Hamiltonian环问题 问题定义 输入: 具有n个节点的连通图G=(V, E) 输出: G中是否具有Hamiltonian环 算法 1. 构造由根组成的队列Q； 2. If Q的第一个元素x是目标节点 Then 停止; 3. 从Q中删除x，把x的所有子节点加入Q的末尾; 4. If Q空 Then 失败 Else goto 2. Depth-First Search 例1. 求解子集合和问题 输入: S={7, 5, 1, 2, 10} 输出: 是否存在S’?S, 使得Sum(S’)=9 Hill Climbing算法 1. 构造由根组成的单元素栈S; 2. If Top(S)是目标节点 Then 停止; 3. Pop(S); 4. S的子节点按照其启发测度由大到 小的顺序压入S; 5. If S空 Then 失败 Else goto 2. 基本思想 上述方法很难用于求解优化问题 分支界限策略可以有效地求解组合优化问题 发现优化解的一个界限 缩小解空间, 提高求解的效率 举例说明分支界限策略的原理 多阶段图有哪些信誉好的足球投注网站问题 输入: 多阶段图 输入 人的集合P={P1, P2, …, Pn}, P1P2 …Pn 工作的集合J={J1, J2, …, Jn}, J是偏序集合 矩阵[Cij], Cij是工作Jj分配到Pi的代价 输出 矩阵[Xij], Xij=1表示Pi被分配Jj , ?i,j CijXij最小 每个人被分配一种工作, 不同人分配不同工作 如果f(Pi)?f(Pj), 则Pi ? Pj 转换为树有哪些信誉好的足球投注网站问题 拓朴排序 输入: 偏序集合(S, ?) 输出: S的拓朴序列是s1, s2, …, sn, 满足: 如果si?sj, 则si排在sj的前面. 例 问题的解空间 命题1. P1? Jk1、P2 ? Jk2、…、Pn ? Jkn是一个可能 解, 当且仅当Jk1、Jk2、…、Jkn必是一个拓朴 排序的序列. 例. P={P1, P2, P3, P4}, J={J1, J2, J3, J4}, J的偏序如下 问题的树表示(即用树表示所有拓朴排序序列) 拓朴序列树的生成算法 输入: 偏序集合S, 树根root. 输出: 由S的所有拓朴排序序列构成的树. 1. 生成树根root; 2. 选择偏序集中没有前序元素的所有元素, 作为 root的子节点; 3. For root的每个字节点v Do 4. S=S-{v}; 5. 把v作为根, 递归地处理S. 例1. 最短路径问题: 输入: A*算法关键—代价函数 对于任意节点n g(n)＝从树根到n的代价 h*(n)＝从n到目标节点的优化路径的代价 f*(n)＝g(n) + h*(n)是节点n的代价 What is the value of h*(n)? 不知道！ 于是, f*(n)也不知道 估计h*(n) 使用任何方法去估计h*(n), 用h(n)表示h*(n)的估计 h(n)?h*(n)总为真 f(n)=g(n)+h(n)?g(n)+h*(n)=f*(n)定义为n的代价 输出: 发现一个从S到T的最短路径 S V3 V2 V1 V4 V5 T 2 3 4 3 2