多米诺性质?求不等式的整数解 影响算法效率的因素 5x+4x,-x≤101≤×≤3,=1 1.最坏情况下的时间W(m)=(风(m)(m) n)每个结点时间,m)结点个数 促左边小事芋过是足米在簽 2.影响回朔算法效率的因素 搜索树的结构 分支情况:分支均匀否 的深度 分布深度 约束条件的判断:计算筒单 分支限界技术 实现方法 与回溯法的比较 求解目标、搜索方式、扩展结点的扩展方式、存储 ■队列式(FIFO)分支限界法 空间的要求不同 活动结点组织成队列,按FIFo原则选取下 对解空间树的搜索存储结点的数结点存储特性常用应用 一个结点为当前扩展结点 ■优先队列式分支限界法 被条件的所有解 活动结点组织成优先队列,按队列中规定 的结点优先级选取优先级最高的下一个结 分支限界广度优先成 队列、优先队部个点只有找出足的 点成为当前扩展结点,通常用堆来实现 最小消耗〔最大效列 盐)优先搜 点的机会 装载问题 用回溯法求解 约束函数:设cW为已装重量,如cw N个待装载的货物[w1w2,wn],船的载重量为 C,求装载哪些货物使得装的货物最重且不超过c w()>c1则杀死该子结点 限界函数:设 besty为当前最优装船重量, Max>wx 设为r剩余货箱的总重量, 如cwW+r<= best则停止产生该结点及其 子结点。 andx∈{O,}回溯算法 43 多米诺性质？求不等式的整数解 , 1≤xi≤3, i=1,2,3 P(x1, …, xk) : 意味将x1,x2,…,xk代入原不等式的相应部分 使得左边小于等于10，是否满足多米诺性质？ 5 4 10 1 2 3 x + x − x ≤ 回溯算法 44 影响算法效率的因素 1. 最坏情况下的时间W(n)=(p(n) f(n)) 其中p(n)每个结点时间，f(n)结点个数 2. 影响回朔算法效率的因素 „ 搜索树的结构 分支情况：分支均匀否 树的深度 对称程度：对称适合裁减 „ 解的分布 在不同子树中分布多少是否均匀 分布深度 „ 约束条件的判断：计算简单 回溯算法 45 分支限界技术 „ 与回溯法的比较 求解目标、搜索方式、扩展结点的扩展方式、存储 空间的要求不同 找出满足约束 条件的一个解 或特定意义下 的最优解 每个结点只有 一次成为活结 点的机会 队列、优先队 列 广度优先或 最小消耗（最大效 益）优先搜索 分支限界 找出满足约束 条件的所有解 活结点的所有 可行子结点被 遍历后才被从 栈中弹出 回溯 深度优先 堆栈 存储结点的数 结点存储特性 常用应用 据结构 对解空间树的搜索 方式 方法 回溯算法 46 实现方法 „ 队列式（FIFO）分支限界法 活动结点组织成队列，按FIFO原则选取下 一个结点为当前扩展结点 „ 优先队列式分支限界法 活动结点组织成优先队列，按队列中规定 的结点优先级选取优先级最高的下一个结 点成为当前扩展结点，通常用堆来实现 回溯算法 47 装载问题 „ N个待装载的货物[w1,w2,…,wn]，船的载重量为 C，求装载哪些货物使得装的货物最重且不超过C。 1 n i i i Max w x = ∑ 1 { } 1 0,1 , 1 n i i i i w x c and x i n = ∑ ≤ ∈ ≤≤ 回溯算法 48 用回溯法求解 „ 约束函数：设cw为已装重量，如cw＋ w(i)>c1则杀死该子 结点。 „ 限界函数：设bestw为当前最优装船重量， 设为 r剩余货箱的总重量， 如cw+r<=bestw,则停止产生该结点及其 子结点