您好、欢迎来到现金彩票网!
当前位置:ds视讯 > 分支限界搜索 >

第十三章 分支限界法

发布时间:2019-09-01 08:07 来源:未知 编辑:admin

  第十三章 分支限界法_数学_自然科学_专业资料。第五部分 克服困难性 第十三章 回溯法和分支限界法 (二) 第十三章 回溯法和分支限界法(二) 13.4 分支限界法 13.5 分支限界法的应用 13.5.1 单源最短路径问题 13.5.2 0/

  第五部分 克服困难性 第十三章 回溯法和分支限界法 (二) 第十三章 回溯法和分支限界法(二) 13.4 分支限界法 13.5 分支限界法的应用 13.5.1 单源最短路径问题 13.5.2 0/1背包问题 13.5.3 旅行商问题 13.5.4 指派问题 13.5.5 批处理作业问题 本章采用知识发明的第一条线,即方 法——应用为主线. 分支限界法与回溯法的不同 a. 搜索策略的不同:回溯法以深度优先的方 式搜索解空间树; ● 回溯法采用深度优先的方式,朝纵深方向搜 索,直至达到问题的一个可行解,或经判断沿此 路径不会达到问题的可行解或最优解时,停止向 前搜索,并沿原路返回到该路径上最后一个还可 扩展的结点。从该结点出发朝新的方向纵深搜索。 ● 分支限界法则以广度优先或以最小耗费优先 的方式搜索解空间树,将活结点存放在一个特殊 的表中。其策略是:在扩展结点处,先生成其所 有的儿子结点,将那些导致不可行解或导致非最 优解的儿子舍弃,其余儿子加入活结点表中。此 后,从活结点表中按照一定的规则取出一个结点 作为当前扩展结点。并重复上述结点扩展过程。 b. 分支限界法不仅通过约束条件, 而且可通 过目标函数的限界来减少无效搜索。 2. 分支限界法的基本思想 分支限界法常以广度优先或以最小耗费(最 大效益)优先的方式搜索问题的解空间树。 ● 在分支限界法中,每一个活结点只有一次机 会成为扩展结点。活结点一旦成为扩展结点,就 一次性产生其所有儿子结点。在这些儿子结点中, 导致不可行解或导致非最优解的儿子结点被舍弃, 其余儿子结点被加入活结点表中。 此后,从活结点表中取下一结点成为当前扩 展结点,并重复上述结点扩展过程。这个过程一 直持续到找到所需的解或活结点表为空时为止。 3. 常见的两种分支限界法 ● 队列式(FIFO)分支限界法 按照队列先进先出(FIFO)原则选取下一个 节点为扩展节点。 ● 优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最 高的节点成为当前扩展节点。 队列式分支限界法的搜索解空间树的方式 类似于解空间树的宽度优先搜索,不同的是队列 式分支限界法不搜索已不可行结点(已经被判定 不能导致可行解或不能导致最优解的结点)为根 的子树。按照规则,这样的结点不被列入活结点 表。 ● 优先队列式分支限界法的搜索方式是根据 活结点的优先级确定下一个扩展结点。结点的优 先级常用一个与该结点有关的限界函数值p来表 示。 ● 最大优先队列规定p值较大的结点的优先级 较高。在算法实现时通常用一个最大堆来实现最 大优先队列,体现最大效益优先的原则。 ● 最小优先队列规定p值较小的结点的优先级 较高。在算法实现时,常用一个最小堆来实现, 体现最小优先的原则。 采用优先队列式分支限界算法解决具体问题 时,应根据问题的特点选用最大优先或最小优先 队列,确定各个结点的p值。 ● 4. 限界函数的构造 限界函数要能够提供一个评定候选扩展结点的 方法,以便确定哪个结点最有可能在通往目标 的最佳路径上。 ? 一个限界函数f(d)通常可以由两个部分构成: ⑴从开始结点到结点d的已有耗损值g(d);⑵再 从结点d到达目标的期望耗损值h(d)。即: ? f(d) = g(d) + h(d) ? 通常g(d)的构造较易,h(d)的构造较难。 5. 优先队列分支限界算法的设计思想(模式) ? ? 首先,确定一个合理的限界函数,并根据限界函数 确定问题的目标函数的界[down, up]; 然后,按照广度优先策略遍历问题的解空间树: – 当搜索到达一个扩展结点时,一次性扩展它的所有孩 子,估算每一个孩子结点的目标函数的上(下)界值(又 称为耗费函数值); – 将那些满足约束条件且耗费函数值不超过目标函数的 界的孩子,插入活结点表H中,再从H表中取耗费函 数值极大(小)的下一结点同样扩展; – 直到找到所需的解或H表为空为止。 – 对于H中的叶子结点 ? 其耗费函数值是极值(极大或极小),则该叶子结点对应的解就 是问题的最优解; ? 否则,调整问题的目标函数的界为该叶子结点的耗费函数值, 然后丢弃H表中超出目标函数界的结点,再次选取结点继续扩 展。 13.5 分支限界法的应用 13.5.1 单源最短路径问题 1. 问题描述 下面以一个例子来说明单源最短路径问题:在 下图所给的有向图G中,每一边都有一个非负 边权。要求图G的从源顶点s到目标顶点t之间 的最短路径。 2 3 4 7 3 2 9 2 2 3 4 5 4 2 2 o2 2 1 2 2. 算法思想 单源最短路径问题的限界函数的构造: ? f(d)=g(d)+h(d) ? g(d)定义为从源s到结点d所走的路径长度: ? g(d) = g(p) + C[p][d] 这里p为d的前驱结点,C[p][d]为p到d的距离。 ? ? ? h(d)定义为0。于是f(d) = g(d)。 源s的评价函数f(s) = 0。 限界函数的下界为0;上界初始时为∞,以后不断 用取得的更短路径的长度来替代。 单源最短路径问题为极小优化问题,因此可用一个 极小堆来存储活结点表。 Input:有向图G; Output:从源点s到终点t的最短路径长度。 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 3. 算法 1. 设定目标函数的限界down=0,up=∞ 2. 计算初始结点1的f(1)=0,将初始结点插入最小堆H; 3. while (H ≠Φ) 4. { 5. 从H中做DELETEMIN的操作,用p带回相应结点; 6. 产生p的所有满足约束条件的后继结点d并计算f(d); 7. while 对每个结点d 8. { if f(d)up then 9. { if d是叶子结点 then 10. { up=f(p); 11. 删除活结点表(最小堆H)中函数值大于up值的结点; 12. if (H=Φ) then 13. 从叶子结点沿parent指针输出解,退出; 14. } 15. else 将d结点插入最小堆H中; 16. } 17. } 18. } 13.5.2 0-1背包问题 ? 分析:问题的解可表示为n元向量{x1, x2, ... xn }, xi?{0,1},则可用排序树表示解空间, 在树中做广 度优先搜索。 n – 约束条件: ? wi xi ? W i ?1 – 目标函数: V ? max ? vi xi i ?1 1 1 2 1 4 1 8 0 9 1 10 0 5 0 11 1 12 6 1 0 3 0 7 n 0 13 1 14 0 15 限界函数的确定: 下界:应用贪心法求得近似解为(1, 0, 0, 0),获得的 价值为v1,这可以作为0/1背包问题的下界。 上界:考虑最好情况,背包中装入的全部是第1个 物品且可以将背包装满,则可以得到一个非常简单的上 界的计算方法:ub=W×(v1/w1)。于是,得到了目标函数 的界[v1 , ub]。 限界函数为: ub ? v ? (W ? w) ? (vi ?1 wi ?1 ) 这里g(d)=v (已经装入背包的物品价值) h(d)=(W-w)×(vi+1/wi+1) (剩余容量全部装入可 选物品中单位价值最大的物品达到的最大价值) 背包问题为极大优化问题,因此可用一个极大堆来 存储活结点表。 实例:假设有4个物品,其重量分别为(4, 7, 5, 3),价值分别为(40, 42, 25, 12),背包容量 W=10。将给定物品按单位重量价值从大到小排 序,结果如下: 物品 1 2 3 4 重量(w) 4 7 5 3 价值(v) 40 42 25 12 价值/重量(v/w) 10 6 5 4 ? 分支限界法求解0/1背包问题: ub ? v ? (W ? w) ? (vi ?1 wi ?1 ) 1 w=0, v=0 ub=100 目标函数范围:[40, 100] W=10 wi=(4, 7, 5, 3) vi= (40, 42, 25, 12) vi/wi=(10, 6, 5, 4) H={2, 3} 4 × w=11 无效解 x2=1 2 w=4, v=40 ub=76 x1=1 x1=0 3 w=0, v=0 ub=60 x2=0 5 w=4, v=40 ub=70 H={5, 3} 6 w=9, v=65 ub=69 8 w=12 无效解 x4=1 x3=1 7 w=4, v=40 ub=64 9 w=9, v=65 ub=65 x4=0 x3=0 H={6, 7, 3} × H={9, 7, 3} V=65 X=(1, 0, 1, 0) 算法 Input:n个物品的价值和重量,背包容量w; Output:装入背包的物品及最大价值。 1. 设定目标函数的限界down=40,up=100 2. 计算初始结点1的f(1)=100,将初始结点插入最大堆H; 3. while (H ≠Φ) 4. { 5. 从H中做DELETEMAX的操作,用p带回相应结点; 6. If p是叶子结点 then 7. 输出当前最优值,并从叶子结点沿parent指针输出解,退出; 8. Else 9. { 产生p的所有满足约束条件的后继结点d,并计算f(d); 10. if f(d)down then 11. { 将d结点插入最大堆H中; 12. if d是叶子结点 then 13. { down=f(d); 14. 删除活结点表(最大堆H)中函数值小于down值的结点; 15. } 16. } 17. } 18. } 13.5.2 旅行商问题 ? ? 30 ?30 ? ?6 5 ? ? 4 10 6 4? 5 10? ? 20? 20 ? ? ? 算法思路: 设周游路线,...xn) xi?{2,...,n}. 则解空间树为排列树,在树中做广度优先搜 索。 约束条件: xi ? xj ,i ? j; 目标函数:解向量对应的边权之和∑Cij ? ? ? ? ? 限界函数: f(d)=g(d)+h(d) g(d)定义为从结点1到结点d所走的路径长度; h(d)定义为0。于是f(d) = g(d)。 限界函数的下界为0;上界初始时为∞。 旅行商问题为极小优化问题,因此可用一个极小堆 来存储活结点表。 1. 旅行商问题的队列分支限界法 2. 旅行商问题的优先队列分支限界法 30 11 6 26 14 4 24 25 25 59 分支限界法求TSP的搜索 0 1 ∞ 25 40 31 27 5 ∞ 17 30 25 19 15 ∞ 6 1 9 50 24 ∞ 6 22 8 7 10 ∞ 25 2 42 3 55 4 50 40 3 31 4 27 5 34 3 37 4 找到了第一条周游路 49 40 87 61 4 2 3 线 55 47 5 3 2 5 35 2 这不是最短周游路线,需要修改上界后继续搜索。 算法 Input:图G=(V,E),顶点编号为1到n; Output:从1顶点出发的最短巡回旅行路线。 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1. 设定目标函数的限界down=0,up=∞ 2. 计算初始结点1的f(1)=0,将初始结点插入最小堆H; 3. while (H ≠Φ) 4. { 5. 从H中做DELETEMIN的操作,用p带回相应结点; 6. 产生p的所有满足约束条件的后继结点d并计算f(d); 7. while 对每个结点d 8. { if f(d)up then 9. { if d是叶子结点 then 10. { up=f(p); 11. 删除活结点表(最小堆H)中函数值大于up值的结点; 12. if (H=Φ) then 13. 从叶子结点沿parent指针输出解,退出; 14. } 15. else 将d结点插入最小堆H中; 16. } 17. } 18. } 归约矩阵以及约数 ? 前面的搜索的效率不高,几乎要搜索全部的状态空间。 其原因是评价函数以及上下界的估计太低。为了设计 求解TSP问题的更好的评价函数,先定义其代价矩阵 的归约矩阵和约数。 给定代价矩阵C,从C的任何行i(或列j)的各元素中减 去此行(或此列)的最小元素的值r(i)(或r’(j)),称为对i 行(或j列)的归约。将C的各行和各列都归约后的矩阵 称为C的归约矩阵。和数 r = ∑i≤n r(i) + ∑i≤n r’(j) 称为C的约数。 ? 归约矩阵和约数举例 ? 计算下面例子中的归约矩阵及其约数如下: ∞ 25 40 31 27 5 ∞ 17 30 25 19 15 ∞ 6 1 9 50 24 ∞ 6 22 8 7 10 ∞ 先做行归约: 再做列归约: ? 约数 r = 47。 r(1)=25 ∞ 0 15 63 2 0 ∞ 12 25 22 20 r(2)=5 r(3)=1 18 14 ∞ 52 0 3 44 21 ∞ r(4)=6 ∞ 0 r(5)=7 15 1 0 3 0 ∞ r’(1)=r’(2)=r’(3)=r’(5)=0 r’(4)=3 约数是周游路线长度的下界 ? 定理:设C是图G的代价矩阵,P是周游路线, 则P的代价,即∑i, j∈P cij = r + ∑i, j∈P c’ij , 式中C’ = [c’ij]是C的归约矩阵,r为约数。 ? 证明:由归约矩阵的构造可知: c’ij = cij – r(i) – r’(j) 即cij = c’ij + r(i) + r’(j)。 ? 任何周游路线包含n条边并且对应在C中的 每行每列有且仅有一条边。于是 ∑i, j∈P cij = ∑ r(i) + r’(j))。 ri, + j ∑ c’ ∈ P(c’ ijP+ i, j∈ ij 。 定义期望函数h(d) 设 C’p为某路线上结点 p的归约矩阵。从 p选择 对开始结点 1,令g(1) = 0,h(1) = r,f(1) = r。 边p, d所得到结点d的归约矩阵C’d和约数rd ? 为: 若从结点1选择了一条边,不妨设边1, 2,则 令g(2) = f(1)+从1到2的距离l ,显然l应该是c’12, ? (1)将C’p中的c’dp, c’pk和c’kd臵为∞,1≤k≤n; 而不应该再是c12了。 ? (2)依照求归约矩阵C’的方法对C’p进行行归约 ? 和列归约,便得到了 那么h(2) = ? C’d和rd 。 ? 自然可以想到h(2)可以是从2开始的路线。是否也可用类似求 r一样去求新的约数 呢? ? 令 f(1) = g(1) + h(1),其中 g(1) = 0,h(1) = r r2 。 可以,但在此之前应将边 1, 2和所有边1, ? 对任意路线上的结点 d,设 p是其前驱结点,则 k和边k, 2 都删去,即臵 c’12 、c’1k和c’k2为∞。 f(d) = g(d) + h(d) , 其中,g(d) = f(p) + C’p[p][d], h(d) = rd。 ? ? 用新的评价函数求TSP ? 下面用新的评价函数求前面的例子,我们已经求 得了它的归约矩阵C’和约数r = 47。 47 1 62 2 3 63× 51 4 50 5 62 3 84× 4 72× 5 4 × 76 2 69× 3 64× 4 67× 2 68× 3 81 4 121 × × ∞ ∞ ∞ ∞3 ∞ ∞ 15 ∞ 2 ∞ ∞ 0 ∞ ∞∞ ∞ ∞ 0 10 8 0 ∞ 12 22 ∞ 0∞ ∞ ∞ ∞ ∞20 0 ∞ ∞∞ 0 12 10 22 8 ∞ ∞ 18 14 ∞ 2 0 ∞ 15 ∞ ∞ 15 ∞ ∞ 18 14 ∞ ∞ 2 2 ∞ 0 0 16 13 ∞ 3 18 ∞ 0 0 43 ∞ ∞ ∞ 0 3 44 44 ∞ 18 18 ∞ ∞0 0 ∞ 15 3∞ 12 15 1 0 0 ∞ ∞ ∞ ∞0 ∞∞ ∞ 0 ∞ ∞ 0 ∞ 12 ∞ 0 0 ∞ 62 5 于是找到了一条最短的周 其余未扩展的结点 对结点 5(f(5) = 62) g(2) = 50 + 0 = 50 游路线: 结点 下面对 对结点 4 是目标结点, 2 f(3) 4 5 的另外两个 , = 62 的结 下面要扩展的结点 g(3) = 62 + 0 = 62 ; 此时 类似地计算出 下面扩展 C’ 是在 f(4) C’ = f(3) f(4) 51 的基 的结 = 68 81 的评价函数值均超 下面优先扩展的是结 g(2) = 47 g(3) 0 == 62 2 + 15 547 类似地可求出 再进行扩展。 1→2→3→5→4→1 找到了第一条路线。 = 62 64 。 儿子进行同样的计 是 对 f(2)= C’ 的结点 2。 点 4 。并用同样方法计 62 得 础上进行。右边就是 过上界,因而不再 2进行归约, 点 5 。 4 f(4) f(5) 51 50 。 h(2) = 17 h(3) =1 h(2) 12需要扩展了。 +算,得: 3 = 15 g(4) =0 62 + 0 = 62, 两个后继结点。 h(4) 12 ,于是 h(5) 0 ,于是 右边是其对应的归 这条路线的长度为 C’ 算它们的评价函数值。 。 h(3) = ;于是 5 f(2) f(4) 84 , f(5) = 72。 。 h(4) = 02 , 62 约矩阵 C’ 。 62 ,以其为上界。 f(4) = 64 +f(4) 12 76 f(3) = 62 f(3) =67 63 f(5) 62 0 == 62 f(2)= 47 +15 == 62 算法 Input :图G=(V,E),顶点编号为1到n; Output:从1顶点出发的最短巡回旅行路线。 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1. 设定目标函数的限界down=r,up=? 2. 计算初始结点1的f(1)=0,将初始结点插入最小堆H; 3. while (H ≠Φ) 4. { 5. 从H中做DELETEMIN的操作,用p带回相应结点; 6. 产生p的所有满足约束条件的后继结点d并计算f(d); 7. while 对每个结点d 8. { if f(d)up then 9. { if d是叶子结点 then 10. { up=f(p); 11. 删除活结点表(最小堆H)中函数值大于up值的结点; 12. if (H=Φ) then 13. 从叶子结点沿parent指针输出解,退出; 14. } 15. else 将d结点插入最小堆H中; 16. } 17. } 18. } 分支边与二叉树 ? ? ? ? ? 在构造求TSP的搜索树时,还有另外一种算法 稍有点不同,就是将搜索树构造成二叉树。 给定一条最短周游路线P,对于任一条边i, j 只有两种情况,即i, j?P或者i, j?P。 这就可以表示成右边的二叉树: k ____ ____ 其中 i, j表示i, j?P。 i, j i, j 这样的边称为分支边。 m n 用二叉树求TSP 2, 1 50 2 ____ 3 62 ____ 4, 5 4, 5 4, 1 4, 1 ____ 4 62 8 9 74 5 68 53 2, 3 ____ 2, 3 1, 4 1, 4 ___ 11 70 62 10 3, 5 3, 5 64 6 7 65 13 66 62 12 ___ 5, 4 5, 4 15 66 结点16给出了一条 62 14 ____ 1, 2 1, 2 最短周游路线→5→4→1 13.5.4 指派问题 设有4个雇员和4件工作,用下面的矩阵表示 耗费函数,矩阵中,行i对应于第i个雇员,第j列 对应于第j件工作。找出一种工作指派使得总耗 费最小。 ?3 ?6 ? ?3 ? ?8 5 7 7 5 2 5 4 4 4? ? 3? 5? ? 6? 装载问题 有一批共n个集装箱要装上2艘载重量分别为 C1和C2的轮船,其中集装箱i的重量为Wi,且 ?w i ?1 n i ? c1 ? c2 装载问题要求确定是否有一个合理的装载方案 可将这个集装箱装上这2艘轮船。如果有,找出 一种装载方案。 容易证明:如果一个给定装载问题有解,则采用 下面的策略可得到最优装载方案。 (1)首先将第一艘轮船尽可能装满; (2)将剩余的集装箱装上第二艘轮船。 举例 c1=c2=50, n=3, w={10, 40, 40}。 w={20, 40, 40}。 1. 队列式分支限界法 2. 优先级分支限界法 无论哪种分支限界法,策略都是尽可能装满 第一艘轮船,剩下的集装箱能够装入第二艘轮船 即可。 状态空间树是完全二叉树,每个节点代表当 前集装箱装入第一艘轮船,或者不装入第一艘轮 船;优先级选择当前已装入的箱子的重量加上剩 下箱子的重量之和。 举例 : c1=c2=45, n=4, w={10, 20, 25, 30}。 批处理作业问题 设J1, J2, J3, J4是四项待处理的作业,它们的工 序一样,即先在m1上处理,然后在m2上处理, 最后在m3上处理,加工时间矩阵为: J1 J2 J3 J4 T? ? 5 7 9? ?10 5 2 ? ? ? ? (ti , j ) 4?3 ?9 9 5 ? ? ? ? 7 8 10? m1 m2 m3 找一种最佳的处理顺序,使完成作业的总时间 达到最短。 优先级的确定与LC检索 对于优先队列式分支限界法,结点优先级的 确定直接影响着算法性能。我们当然希望这样的 活结点X成为当前扩展结点: 1) 以X为根的子树中含有问题的答案结点; 2) 在所有满足条件1)的活结点中,X距离答案 结点“最近”。 但是,要给可能导致答案结点的活结点附 以优先级,必须要附加若干计算工作,即要付 出代价。 对于任一结点,要付出的代价可以使用两种标 准来度量: 1. 在生成一个答案结点之前,子树X需要生成 的结点数; 2. 在子树X中离X最近的那个答案结点到X的 路径长度。 ? 如果使用度量1,在对于每一种分枝限界算法, 总是生成最小数目的结点; ? 如果采用度量2,则要成为扩展结点的结点只 是由根到最近的那个答案结点路径上的那些结 点。 用c(· )表示一个理想的优先级函数,定义如下: a) 如果X是答案结点,则c(X)是解空间树中, 由根结点到 X 的成本 ( 即所用的代价,如级数、 计算复杂度等); b) 如果X不是答案结点,而且以X为根的子树 中不含答案结点,则c(X)定义为?; c) 如果X不是答案结点,但是以X为根的子树 中含答案结点,则c(X)是具有最小成本的答案 结点的成本。 ? 如果能够获得这样的优先级函数,则优先 队列式分支限界法将以最少的搜索时间找到问 题的解。 (找这样的优先级函数是非常困难的) ? 实际问题中都是采用一个估计函数e,它由 两部分决定:解空间树的根结点到X的成本f(X) 和X到答案结点的估计成本g(X)。 即 e(X)= f(X)+g(X)。 ?称为成本估计函数。 ? 根据成本估计函数选择下一个扩展结点的策 略总是选取e(· )值最小的活结点作为下一个扩展 结点。这种搜索策略称为最小成本检索(Least Cost search),简称LC-检索。 如前所讲过的装载问题的成本估计函数的确定。 ? 如果取g=0, f(X)等于X在解空间树中的级; ? 如果f=0,且g满足: Y是X的儿子 ? g(Y)? g(X) (13. 1) 以后提到的成本函数e中, 函数g都满足(13.1)式。 例 15迷问题 在一个分成4×4的棋盘上排列15块号牌, 如图 (a)。其中会出现一个空格。棋盘上号牌的一次合 法移动是指将位于空格上、下、左、右的一块号 牌移入空格。要求通过一系列合法移动,将号牌 的初始排列转换成自然排列,如图(b)。 1 5 13 2 6 3 4 7 8 14 15 1 5 2 6 3 4 7 8 9 10 11 12 9 10 11 12 13 14 15 (a) (b) 不是任意的初始状态都可能达到目标状态! ? 先给棋盘的方格编上1-16的号码。位臵 i 是 在图(b)所示的目标排列中放 i 号牌的方格位臵, 位臵16是空格的位臵。假设 POSITION( i )是编 号为 i 的那块牌在初始状态下的编号,1=i16; POSITION( 16 )表示空格的位臵。 ? 对于任意一种状态,设 LESS(i) 是使牌 j 小 于牌 i 且 POSITION( j ) POSITION( i )的数目 (j 为任意满足条件的数,1= j i)。 ? 例如,对于图 7.2(a) 所示的状态,有 LESS(1) = 0,LESS(16) = 2 。 在初始条件下,如果空格在图(c)的阴影位 臵中的某一格处,则令 X = 1;否则令 X = 0。 于是有如下定理。 ? # # # # # # # # (c) Less(i) ? X 是偶数,才可以从 定理:当且仅当 1?? i ?16 初始状态转变到图(b)所示的目标状态。 在处理实际问题中,一般是根据具体问 题的特性,确定成本估计函数e(X)= f(X)+g(X)中 的函数f(X)和g(X)。 ? 在本例中,我们令f(x)是由根到结点X的 路径的长度,g(X)是以X为根的子树中,由X到 目标状态(自然排列)的一条最短路径长度的估计 值。为此,g(X)至少应是把状态X转换成目标状 态所需的最小移动数。对它的一种可能的选择 是 ? g(X)= 排列X的不在自然位臵的牌的数目 关于15迷问题还有很多有效的算法,其中 采用了一些启发式的搜索策略进行剪枝,比如 A*,B*算法等。 ? 博弈搜索 富有智能行为的竞争活动,如下棋、打牌、战 争……. ? 双人完备信息博弈 两位选手对垒,轮流走步,一方知道另一方已 经走过的棋步,并能够估计对方未来的走步。 对弈的结果是一方赢,另一方输;或者双方和 局。实例有象棋、围棋等。 ? 机遇性博弈 存在不可预测性的博弈,例如掷币等。 ? 双人完备信息博弈 ? 在双人完备信息博弈过程中,假设博弈的一方 为MAX,另一方为MIN。可用博弈树表示双 方博弈过程。在博弈树中,那些下一步该 MAX走步的节点称为MAX节点,而下一步该 MIN走步的节点称为MIN节点。 博弈树例:分钱币游戏 ? 假设有7枚硬币,选手只能将已分好的一堆钱 币分成两堆个数不等的硬币。两位选手轮流进 行,直到每一堆都只有一个或两个硬币,不能 再分为止。哪位选手遇到不能再分的情况,则 认输。 博弈状态:(K1,K2,….,Kn, 当前各个钱堆中的钱币数 MIN or MAX) 当前走步方 MAX必胜的策略?(7, MIN) (6,1, MAX) (5,1,1, MIN) (5,2, MAX) (4,2,1, MIN) (4,3, MAX) (3,3,1, MIN) (3,2,2, MIN) (4,1,1,1, MAX) (3,1,1,1,1, MIN) (2,1,1,1,1,1, MAX) (3,2,1,1, MAX) (2,2,1,1,1, MIN) (2,2,2,1, MAX) 分钱币博弈树 极大极小搜索 ? 用当前正在考察的节点生成一棵部分博弈树, 利用估价函数f(n)对叶节点进行静态评估,对 MAX有利的节点其估价函数取正值,如为 MAX获胜节点,则取正无穷大;对MIN有利 的节点,其估价函数取负值,如为MAX认输 节点,则取负无穷大;那些使双方势均力敌的 节点,其估价函数取0值。 (假设MAX为程序方,MIN为对手方) 极大极小过程 从叶节点向上倒推计算非叶节点的值,直到当 前考察节点的过程。 对于MAX节点, MAX方总是选择对自己最好 的走步,即估值最大的走步,因此MAX节点 的倒推值应该取其后继节点估值的极大值。 对于MIN节点,MAX方需做最坏的打算,考 虑MIN方会选择对自己最好,从而对MAX方 最坏的走步,即估值最小的走步,因此MIN节 点的倒推值应取其后继节点估值的极小值。 ? 最终,站在MAX的立场上,显然应选择具有 最大倒推值的走步。 ? 极大极小搜索例:一字棋游戏 ? 设有一个三行三列的棋盘,两个棋手轮流走 步,每个棋手走步时往空格上摆一个自己的 棋子,谁先使自己的棋手成三子一线为赢。 设MAX方的棋子用×标记,MIN方的棋子用 ○标记,并规定MAX方先走步。 静态估价函数e(P) 1. 若 P是 MAX的必胜局, 则 e(P) = +∞ 2. 若 P是 MIN的必胜局, 则 e(P) = -∞ ; 3. 若P对MAX、MIN都是胜负未定局,则 e(P) = e(+P)-e(-P) 其中,e(+P)表示棋局 P上有可能使× 成三子 一线的数目;e(-P)表示棋局 P上有可能使 ○ 成三子一线的数目。 e(P) = 6 – 4=2 ? 在搜索过程中,具有对称性的棋局认为是同一 棋局,以大大减少搜索空间。 对称棋局的例子 总结: 1. 队列 分支限界法和优先级队列分支限界法 2.利用分支限界法旅行商问题, 指派问题等的 过程 3. 优先级分支限界法中,对不同问题优先级 的确定 谢 谢 各 位 为了使分支限界法能应用,限界函数必须满 足下面的属性:对于所有的部分解(x1,x2,…,xk-1) 和扩展的解(x1,x2,…,xk),必须有 ● cost(x1,x2,…,xk-1)≤cost (x1,x2,…,xk) 给出了这个性质,部分解(x1,x2,…,xk)的耗费 一旦大于先前计算出来的解耗费,就可以丢弃。 于是,如果算法找到了一个耗费为c的解,并且 有一个部分解,它的耗费至少是c,那么就不会 有该部分解的扩展生成。 ●

http://gamesbaby.net/fenzhixianjiesousuo/760.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有