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

第5章-3 分支限界算法设计基本方法

发布时间:2019-05-02 14:01 来源:未知 编辑:admin

  第5章-3 分支限界算法设计基本方法_广告/传媒_人文社科_专业资料。程序设计基础课件

  第5章-3 分支限界法 1.分组名单 2.作业 1)简述回溯法的基本思想和主要步骤。 2)比较回溯法与穷举法的异同。 3)简述分支限界法的基本思想和主要步骤。 南京信息工程大学计算机与软件学院 2 学习要点: 学习要点: ? ? ? ? ? ? ? 理解分支限界法的剪枝搜索策略。 掌握分支限界法的算法框架 (1)队列式(FIFO)分支限界法 (2)优先队列式分支限界法 通过应用范例学习分支限界法的设计策略。 (1) 0-1背包问题; (2)装载问题; 南京信息工程大学计算机与软件学院 3 5.3.1 分支限界法的基本思想 分支限界法与回溯法的区别: (1)求解目标:回溯法的求解目标是找出解空 求解目标: 求解目标 间树中满足约束条件的所有解,而分支限界法 的求解目标则是找出满足约束条件的一个解, 或是在满足约束条件的解中找出在某种意义下 的最优解。 搜索方式的不同: (2)搜索方式的不同:回溯法以深度优先的方 搜索方式的不同 式搜索解空间树,而分支限界法则以广度优先 或以最小耗费优先的方式搜索解空间树。 南京信息工程大学计算机与软件学院 4 5.3.1 分支限界法的基本思想 深度优先搜索 ABDHIEJKCFLMGNO 广度优先搜索 ABCDEFGHIJKLMNO 南京信息工程大学计算机与软件学院 5 5.3.1 分支限界法的基本思想 分支限界法常以广度优先或以最小耗费 (最大效益)优先的方式搜索问题的解空间 树。 对已处理的各结点根据限界函数估算目 标函数的可能取值,从中选取使目标函数取 得极值(极大/极小)的结点优先进行广度优 先搜索 不断调整搜索方向,尽快找到解。 特点:限界函数常基于问题的目标函数,适 特点: 用于求解最优化问题。 南京信息工程大学计算机与软件学院 6 5.3.1 分支限界法的基本思想 每一个活结点只有一次机会成为扩展结点。 活结点一旦成为扩展结点,就一次性产生 其所有儿子结点。 在这些儿子结点中,导致不可行解或导致 非最优解的儿子结点被舍弃 其余儿子结点被加入活结点表中。 南京信息工程大学计算机与软件学院 7 5.3.1 分支限界法的基本思想 此后,从活结点表中取下一结点成为当前 扩展结点, 重复上述结点扩展过程,直到找到所需的 解或活结点表为空时为止。 南京信息工程大学计算机与软件学院 8 5.3.1 分支限界法的基本思想 常见的两种分支限界法 (1)队列式(FIFO)分支限界法 队列式(FIFO)分支限界法 队列式(FIFO) 按照队列先进先出(FIFO)原则选取下一 个节点为扩展节点。 (2)优先队列式分支限界法 优先队列式分支限界法 按照优先队列中规定的优先级选取优先级 最高的节点成为当前扩展节点。 9 南京信息工程大学计算机与软件学院 问题的解空间: 与回溯法相同,一般用解空间树 解空间树(Solution Space 解空间树 Trees,也称状态空间树)的方式组织。 例如,对于n=3时的0-1背包问题,可用完全二叉树 表示其解空间,如下图所示。 南京信息工程大学计算机与软件学院 10 对解空间树的动态搜索过程 1.确定一个合理的限界函数,目标函数的界 确定一个合理的限界函数, 确定一个合理的限界函数 [down, up] 2.广度优先遍历解空间树 广度优先遍历解空间树 3.依次从活结点表中选取使目标函数的值取 依次从活结点表中选取使目标函数的值取 得极值的结点成为当前扩展结点 4.重复上述过程,直到找到最优解。 重复上述过程, 重复上述过程 直到找到最优解。 南京信息工程大学计算机与软件学院 11 广度优先遍历过程 在分支结点上,依次搜索该结点的所有孩子结点, 在分支结点上,依次搜索该结点的所有孩子结点, 分别估算这些孩子结点的目标函数的可能取值; 分别估算这些孩子结点的目标函数的可能取值; 如果某孩子结点的目标函数可能取得的值超出目 标函数的界,则将其丢弃, 标函数的界,则将其丢弃,因为从这个结点生成 的解不会比目前已经得到的解更好; 的解不会比目前已经得到的解更好; 否则,将其加入待处理结点表(简称活结点表) 否则,将其加入待处理结点表(简称活结点表) 中。 南京信息工程大学计算机与软件学院 12 叶子的作用——广度优先遍历过程 广度优先遍历过程 随遍历的深入, 随遍历的深入,活结点表中所估算的目标函数的 界越来越接近问题的最优解。 界越来越接近问题的最优解。 1.得解:当搜到一个叶子结点时,如果该结点的 得解: 得解 当搜到一个叶子结点时, 目标函数值是活结点表中的极值 极值, 目标函数值是活结点表中的极值,则该叶子对应 最优解; 最优解; 2.调界:否则,根据该叶子结点调整目标函数的 调界: 调界 否则,根据该叶子结点调整目标函数的 对最小化,调上界;对最大化,调下界); 界(对最小化,调上界;对最大化,调下界); 3.调队列(活结点表):并且,依次考察活结点 调队列( ):并且 调队列 活结点表):并且, 表中的结点,将超出目标函数界的结点丢弃; 表中的结点,将超出目标函数界的结点丢弃; 然后从活结点表中选取使目标函数取得极值的结 点继续进行扩展。 点继续进行扩展。 南京信息工程大学计算机与软件学院 13 0/1背包的分支限界法过程 1. 问题描述 容量w=10 物品 1 2 3 4 重(w) 4 7 5 3 价(v) 40 42 25 12 价/重(v/w) 10 6 5 4 直观的,解(1,0,0,0),价值为40,可作为0/1背包的下界。 南京信息工程大学计算机与软件学院 14 0/1背包的分支限界法过程 2. 求解过程 上界ub可用最好情况来代替ub=w*(v1/w1)=10*10=100 目标函数的界[40, 100],一般解空间树中第i层的各结 点,代表对物1~i的选择,可这样定限界函数: ub = V+ (W-w) * (vi+1/wi+1) 已装入价值 剩余容量 剩下物品最大单位价值vi+1/wi+1 的积 南京信息工程大学计算机与软件学院 15 优先队列式分支限界法求解0/1背包问题 优先队列式分支限界法求解0/1背包问题 0/1 4个物品的重量分别为 7, 5, 3),价值分别为 个物品的重量分别为(4, 个物品的重量分别为 ,价值分别为(40, 42, 25, 12),背包容量 ,背包容量W=10。 。 价重比( 价重比(10,6,5,4) ) 1 w=0, v=0 ub=100 2 w=4, v=40 ub=76 4 × w=11 无效解 6 w=9, v=65 ub=69 8 w=12 无效解 × 9 w=9, v=65 ub=65 南京信息工程大学计算机与软件学院 16 3 w=0, v=0 ub=60 5 w=4, v=40 ub=70 7 w=4, v=40 ub=64 优先队列式分支限界法求解0/1背包问题, 优先队列式分支限界法求解 背包问题, 其搜索空 背包问题 间如上页图所示,具体的搜索过程如下: 间如上页图所示,具体的搜索过程如下: (1)在根结点 ,没有将任何物品装入背包,因此,背包 )在根结点1,没有将任何物品装入背包,因此, 的重量和获得的价值均为0,根据限界函数计算结点1的目 的重量和获得的价值均为 ,根据限界函数计算结点 的目 标函数值为10× 标函数值为 ×10=100; ; (2)在结点 ,将物品 装入背包,因此,背包的重量为 , 装入背包, )在结点2,将物品1装入背包 因此,背包的重量为4, 获得的价值为40,目标函数值为40 获得的价值为 ,目标函数值为 + (10-4)×6=76,将结 × , 点2加入待处理结点活结点表中;在结点3,没有将物品1 加入待处理结点活结点表中;在结点 , 没有将物品 加入待处理结点活结点表中 装入背包,因此,背包的重量和获得的价值仍为0, 装入背包,因此,背包的重量和获得的价值仍为 ,目标 函数值为10× = ,将结点3加入活结点表中 加入活结点表中; 函数值为 ×6=60,将结点 加入活结点表中; (3)在活结点表中选取目标函数值取得极大的结点 优先 )在活结点表中选取目标函数值取得极大的结点2优先 进行搜索; 进行搜索; 南京信息工程大学计算机与软件学院 17 ( 4)在结点4,将物品2装入背包, 因此,背包的重量为 ) 在结点 , 将物品 装入背包, 因此, 装入背包 11,不满足约束条件,将结点 丢弃;在结点 ,没有将物 丢弃; ,不满足约束条件,将结点4丢弃 在结点5,没有将物 装入背包, 品2装入背包,因此,背包的重量和获得的价值与结点 相 装入背包 因此,背包的重量和获得的价值与结点2相 目标函数值为40 同,目标函数值为 + (10-4)×5=70,将结点 加入活结点 × ,将结点5加入活结点 表中; 表中; (5)在活结点表中选取目标函数值取得极大的结点 优先 )在活结点表中选取目标函数值取得极大的结点5优先 进行搜索; 进行搜索; 装入背包, (6)在结点 ,将物品 装入背包,因此,背包的重量为 , )在结点6,将物品3装入背包 因此,背包的重量为9, 获得的价值为65,目标函数值为65 + (10-9)×4=69,将结 获得的价值为 ,目标函数值为 × , 点 6加入活结点表中; 在结点7,没有将物品3装入背包, 加入活结点表中; 在结点 , 没有将物品 装入背包, 加入活结点表中 装入背包 因此,背包的重量和获得的价值与结点5相同 相同, 因此 , 背包的重量和获得的价值与结点 相同 , 目标函数 值为40 加入活结点表中; 值为 + (10-4)×4=64,将结点 加入活结点表中; × = ,将结点6加入活结点表中 18 南京信息工程大学计算机与软件学院 (7)在活结点表中选取目标函数值取得极大的结点 优先 )在活结点表中选取目标函数值取得极大的结点6优先 进行搜索; 进行搜索; 装入背包, (8)在结点 ,将物品 装入背包,因此,背包的重量为 )在结点8,将物品4装入背包 因此, 12,不满足约束条件,将结点 丢弃;在结点 ,没有将物 丢弃; ,不满足约束条件,将结点8丢弃 在结点9, 装入背包, 品4装入背包,因此,背包的重量和获得的价值与结点 相 装入背包 因此,背包的重量和获得的价值与结点6相 目标函数值为65; 同,目标函数值为 ; 是叶子结点, (9)由于结点 是叶子结点,同时结点 的目标函数值是活 )由于结点9是叶子结点 同时结点9的目标函数值是活 结点表中的极大值 所以,结点9对应的解即是问题的最优 极大值, 结点表中的极大值,所以,结点 对应的解即是问题的最优 搜索结束。 解,搜索结束。 南京信息工程大学计算机与软件学院 19 0/1背包的分支限界法过程 3.小结 从0/1背包问题的搜索过程可看出:与回溯法相 比,分支限界法可根据限界函数不断调整搜索 方向,选择最可能得最优解的子树优先进行搜 索 找到问题的解。 南京信息工程大学计算机与软件学院 20 优先队列式分支限界法求解最大化问题的一般过程 1.根据限界函数确定目标函数的界[down, up]; .根据限界函数确定目标函数的界 ; 2.将待处理结点活结点表初始化为空; .将待处理结点活结点表初始化为空; 3.对根结点的每个孩子结点 执行下列操作 .对根结点的每个孩子结点x执行下列操作 3.1 估算结点 的目标函数值 估算结点x的目标函数值 的目标函数值value; 3.2 若(value=down),则将结点 加入活结点表中; 加入活结点表中; ,则将结点x加入活结点表中 4.循环直到某个叶子结点的目标函数值在活结点表中最大 . 4.1 i=活结点表中值最大的结点; 活结点表中值最大的结点; 活结点表中值最大的结点 4.2 对结点 的每个孩子结点 执行下列操作 对结点i的每个孩子结点 的每个孩子结点x执行下列操作 4.2.1 估算结点 的目标函数值 估算结点x的目标函数值 的目标函数值value; 4.2.2 若(value=down),则将结点 加入活结点表中; 加入活结点表中; ,则将结点x加入活结点表中 4.2.3 若(结点 是叶子结点且结点 的value值在活结点表中最大 , 结点x是叶子结点且结点 值在活结点表中最大), 结点 是叶子结点且结点x的 值在活结点表中最大 则将结点x对应的解输出 算法结束; 对应的解输出, 则将结点 对应的解输出,算法结束; 4.2.4 若(结点 是叶子结点但结点 的value值在活结点表中不是最大 , 结点x是叶子结点但结点 值在活结点表中不是最大), 结点 是叶子结点但结点x的 值在活结点表中不是最大 则令down=value,并且将活结点表中所有小于 的结点删除; 则令 ,并且将活结点表中所有小于value的结点删除; 的结点删除 南京信息工程大学计算机与软件学院 21 应用分支限界法的关键问题 (1)如何确定合适的限界函数 ) 2) (2)如何组织待处理结点表 (3)如何确定最优解中的各个分量 ) 南京信息工程大学计算机与软件学院 22 确定最优解中的各个分量 当搜索到某个叶子结点且求得了问题的最优值, 当搜索到某个叶子结点且求得了问题的最优值,但 是,却无法求得该叶子结点对应的最优解中的各个 分量。 分量。 这个问题可以用如下方法 如下方法① 解决: 这个问题可以用如下方法①或②解决: 对每个扩展结点保存该结点到根结点的路径; ① 对每个扩展结点保存该结点到根结点的路径; 在搜索过程中构建搜索经过的树结构, ② 在搜索过程中构建搜索经过的树结构 , 在求得 最优解时,从叶子结点不断回溯到根结点, 最优解时,从叶子结点不断回溯到根结点,以确定 最优解中的各个分量。 最优解中的各个分量。 南京信息工程大学计算机与软件学院 23 方法①确定0/1背包问题最优解的各分量 方法①确定0/1背包问题最优解的各分量 0/1 例如, 背包问题中, 例如,在0/1背包问题中,为了对每个扩展结点保存该结点 背包问题中 到根结点的路径,将部分解(x 到根结点的路径,将部分解 1, …, xi)和该部分解的目标函 和该部分解的目标函 数值都存储在待处理结点活结点表中, 数值都存储在待处理结点活结点表中,在搜索过程中活结 点表的状态如下图所示。 点表的状态如下图所示。 (1)76 (0)60 (0)60 (1,0)70 (a) 扩展根结点后活结点表状态 (0)60 (1,0,1)69 (1,0,0)64 (b) 扩展结点 后活结点表状态 扩展结点2后活结点表状态 (0)60 (1,0,0)64 (1,0,1,0)65 (c) 扩展结点 后活结点表状态 扩展结点5后活结点表状态 (d) 扩展结点 后活结点表状态, 扩展结点6后活结点表状态 后活结点表状态, 最优解为(1,0,1,0) 65 最优解为 南京信息工程大学计算机与软件学院 24 方法②确定0/1背包问题最优解的各分量 方法②确定0/1背包问题最优解的各分量 0/1 为在搜索中构建经过的树结构,设一个表ST,在活结点表中 为在搜索中构建经过的树结构,设一个表 , 取出最值结点进行扩充时,将最值结点存储到表ST中 取出最值结点进行扩充时,将最值结点存储到表 中. 活结点表和表ST的数据结构为 物品i-1的选择结果, 物品 活结点表和表 的数据结构为(物品 的选择结果, 物品i, 的数据结构为 物品 的选择结果 物品 物品i的选择结果 的选择结果ub), 物品 的选择结果 , 在搜索过程中活结点表和表ST的状态如下图所示。 在搜索过程中活结点表和表 的状态如下图所示。 的状态如下图所示 PT ST (a) 扩展根结点后 PT ST (0,1,060) (0,1,176) (0,3,169) (1,2,070) (0,3,064) PT ST (0,1,060) (0,1,176) (0,1,176) (0,1,060) PT ST (0,1,060) (0,1,176) (b) 扩展结点 后 扩展结点2后 (0,3,064) (1,2,070) (1,4,065) (0,3,169) (1,2,070) (c) 扩展结点 后 扩展结点5后 (d) 扩展结点 后,最优解为 扩展结点6后 最优解为(1,0,1,0)65 南京信息工程大学计算机与软件学院 25 5.3.2 分支限界法的时间性能 分支限界法和回溯法实际上都属于穷举法, 分支限界法和回溯法实际上都属于穷举法 , 遍历具有指数阶个结点的解空间树, 遍历具有指数阶个结点的解空间树,在最坏情况 时间复杂性肯定为指数阶。 下,时间复杂性肯定为指数阶。 与回溯法不同的是,分支限界法首先扩展解 与回溯法不同的是, 空间树中的上层结点,并采用限界函数 限界函数, 空间树中的上层结点,并采用限界函数,有利于 实行大范围剪枝,同时, 实行大范围剪枝,同时,根据限界函数不断调整 搜索方向, 搜索方向,选择最有可能取得最优解的子树优先 进行搜索。 进行搜索。 南京信息工程大学计算机与软件学院 26 所以, 所以,如果选择了结点的合理扩展顺序以 及设计了一个好的限界函数, 及设计了一个好的限界函数,分支界限法 可以快速得到问题的解。 可以快速得到问题的解。 分支限界法的较高效率是以付出一定代价 为基础的, 为基础的,其工作方式也造成了算法设计 的复杂性。 的复杂性。 南京信息工程大学计算机与软件学院 27 算法设计复杂的表现 1)限界函数:一个更好的限界函数通常需要花费 限界函数: 限界函数 更多的时间计算相应的目标函数值, 更多的时间计算相应的目标函数值,而且对于具 体的问题实例,通常需要进行大量实验, 体的问题实例,通常需要进行大量实验,才能确 定一个好的限界函数; 定一个好的限界函数; 2)算法设计较为复杂 为了从叶子结点求出对应最 算法设计较为复杂:为了从叶子结点求出对应最 算法设计较为复杂 优解的各分量,需保存该结点到根结点的路径, 优解的各分量,需保存该结点到根结点的路径, 或者在搜索过程中构建经过的树结构; 或者在搜索过程中构建经过的树结构; 3)需要较大的存储空间 算法要维护一个待处理结 需要较大的存储空间:算法要维护一个待处理结 需要较大的存储空间 活结点)表 点(活结点 表,并且需要在活结点表中快速查找 活结点 取得极值的结点,等等。在最坏情况下, 取得极值的结点,等等。在最坏情况下,需要的 空间复杂性是指数阶。 空间复杂性是指数阶。 南京信息工程大学计算机与软件学院 28 5.3.3 装载问题 1. 问题描述 有一批共n个集装箱要装上2 有一批共n个集装箱要装上2艘载重量分别 的轮船, 其中集装箱i 为 C1 和 C2 的轮船 , 其中集装箱 i 的重量为 n Wi, Wi,且 ∑w ≤ c + c i =1 i 1 2 装载问题要求确定是否有一个合理的装载 方案可将这个集装箱装上这2艘轮船。如 果有,找出一种装载方案。 南京信息工程大学计算机与软件学院 29 5.3.3 装载问题 容易证明:如果一个给定装载问题有解, 则采用下面的策略可得到最优装载方案。 (1)首先将第一艘轮船尽可能装满; (2)将剩余的集装箱装上第二艘轮船。 南京信息工程大学计算机与软件学院 30 5.3.3 装载问题 2. 队列式分支限界法 在算法的while循环中,首先检测当前扩展结点的左儿 子结点是否为可行结点。如果是则将其加入到活结点队列中。 然后将其右儿子结点加入到活结点队列中(右儿子结点一定 是可行结点)。2个儿子结点都产生后,当前扩展结点被舍弃。 活结点队列中的队首元素被取出作为当前扩展结点,由 于队列中每一层结点之后都有一个尾部标记-1,故在取队首 元素时,活结点队列一定不空。当取出的元素是-1时,再判 断当前队列是否为空。如果队列非空,则将尾部标记-1加入 活结点队列,算法开始处理下一层的活结点。 南京信息工程大学计算机与软件学院 31 节点的左子树表示将此集装箱装上船,右 子树表示不将此集装箱装上船。 设bestw是当前最优解;ew是当前扩展结点 所相应的重量 南京信息工程大学计算机与软件学院 32 5.3.3 装载问题 2. 队列式分支限界法 while (true) { // 检查左儿子结点 if (Ew + w[i] = c) // x[i] = 1 EnQueue(Q, Ew + w[i], bestw, i, n); // 右儿子结点总是可行的 EnQueue(Q, Ew, bestw, i, n); // x[i] = 0 Q.Delete(Ew); // 取下一扩展结点 if (Ew == -1) { // 同层结点尾部 if (Q.IsEmpty()) return bestw; Q.Add(-1); // 同层结点尾部标志 Q.Delete(Ew); // 取下一扩展结点 i++;} // 进入下一层 } } 南京信息工程大学计算机与软件学院 33 5.3.3 装载问题 3. 算法的改进 节点的左子树表示将此集装箱装上船,右子 树表示不将此集装箱装上船。设bestw是当前最优 解;ew是当前扩展结点所相应的重量;r是剩余集 装箱的重量。则当ew+r≤bestw时,可将其右子树 剪去,因为此时若要船装最多集装箱,就应该把 此箱装上船。 另外,为了确保右子树成功剪枝,应该在算 法每一次进入左子树的时候更新bestw的值。 南京信息工程大学计算机与软件学院 34 5.3.3 装载问题 3. 算法的改进 提前更新 bestw // 检查左儿子结点 Type wt = Ew + w[i]; // 左儿子结 if (Ew + r bestw && i n) 点的重量 if (wt = c) { // 可行结点 Q.Add(Ew); Q.Delete(Ew); 点 // 可能含最优解 // 取下一扩展结 // 检查右儿子结点 右儿子剪枝 if (wt bestw) bestw = wt; // 加入活结点队列 if (i n) Q.Add(wt); } 南京信息工程大学计算机与软件学院 35 5.3.3 装载问题 4. 构造最优解 为了在算法结束后能方便地构造出与 最优值相应的最优解,算法必须存储相应 子集树中从活结点到根结点的路径。为此 目的,可在每个结点处设置指向其父结点 的指针,并设置左、右儿子标志。 找到最优值后,可以根据parent回溯 到根节点,找到最优解。 南京信息工程大学计算机与软件学院 36 5.3.3 装载问题 5. 优先队列式分支限界法 解装载问题的优先队列式分支限界法用最大优先队列 存储活结点表。活结点x在优先队列中的优先级定义为从 根结点到结点x的路径所对应的载重量再加上剩余集装箱 的重量之和。 优先队列中优先级最大的活结点成为下一个扩展结点。 以结点x为根的子树中所有结点相应的路径的载重量不超 过它的优先级。子集树中叶结点所相应的载重量与其优先 级相同。 在优先队列式分支限界法中,一旦有一个叶结点成为 当前扩展结点,则可以断言该叶结点所相应的解即为最优 解。此时可终止算法。 南京信息工程大学计算机与软件学院 37 5.3.4 任务分配问题 任务分配问题要求把n项任务分配给 个人 任务分配问题要求把 项任务分配给n个人 , 项任务分配给 个人, 每个人完成每项任务的成本不同, 每个人完成每项任务的成本不同,要求分配总成本 最小的最优分配方案。 最小的最优分配方案。下图是一个任务分配的成本 矩阵。 矩阵。 任务1 任务2 任务3 任务4 任务 任务 任务 任务 C= = 9 6 5 7 2 4 8 6 7 3 1 9 8 7 8 4 人员a 人员 人员b 人员 人员c 人员 人员d 人员 图示 任务分配问题的成本矩阵 南京信息工程大学计算机与软件学院 38 求最优分配成本的上界和下界 考虑任意一个可行解, 考虑任意一个可行解,例如矩阵中的对角线是一个合法的选 表示将任务1分配给人员 分配给人员a、任务2分配给人员 任务3 分配给人员b、 择,表示将任务 分配给人员 、任务 分配给人员 、任务 分配给人员c、任务4分配给人员 分配给人员d,其成本是9+4+1+4=18; 分配给人员 、任务 分配给人员 ,其成本是 ; 或者应用贪心法求得一个近似解:将任务2分配给人员 分配给人员a、 或者应用贪心法求得一个近似解:将任务 分配给人员 、任 分配给人员b、任务1分配给人员 任务4分配给人员 分配给人员c、 分配给人员d, 务3分配给人员 、任务 分配给人员 、任务 分配给人员 , 分配给人员 其成本是2+3+5+4=14。显然,14是一个更好的上界。为了 是一个更好的上界。 其成本是 。显然, 是一个更好的上界 获得下界,考虑人员a执行所有任务的最小代价是 人员b 执行所有任务的最小代价是2, 获得下界,考虑人员 执行所有任务的最小代价是 ,人员 执行所有任务的最小代价是3,人员c执行所有任务的最小代 执行所有任务的最小代价是 ,人员 执行所有任务的最小代 价是1,人员d执行所有任务的最小代价是 因此, 执行所有任务的最小代价是4。 价是 ,人员 执行所有任务的最小代价是 。因此,将每一 行的最小元素加起来就得到解的下界, 行的最小元素加起来就得到解的下界,其成本是 2+3+1+4=10。需要强调的是,这个解并不是一个合法的选 。需要强调的是, 来自于矩阵的同一列), 择(3和1来自于矩阵的同一列),它仅仅给出了一个参考下 和 来自于矩阵的同一列),它仅仅给出了一个参考下 这样,最优值一定是[10, 14]之间的某个值。 之间的某个值。 界,这样,最优值一定是 之间的某个值 南京信息工程大学计算机与软件学院 39 设当前已对人员1~ 分配了任务 并且获得了成本v, 分配了任务, 设当前已对人员 ~i分配了任务,并且获得了成本 , 则限界函数可以定义为: 则限界函数可以定义为: lb = v + n k = i +1 =i ∑ 第 k行的最小值 南京信息工程大学计算机与软件学院 40 应用分支限界法求解任务分配问题,对解空间树的搜索如下图所示。 1 start lb=10 2 × 1→a lb=17 3 2→a lb=10 7 1→b lb=13 11 3→c lb=13 13 4→d lb=13 12 × 4→c lb=17 3→b lb=10 9 1→c lb=14 4 × 3→a lb=15 8 4→b lb=14 10 × 4→c lb=17 5 × 4→a lb=16 6 (×表示该结点被丢弃,结点上方的数表示搜索顺序) ×表示该结点被丢弃,结点上方的数表示搜索顺序 南京信息工程大学计算机与软件学院 41 具体的搜索过程如下: (1)在根结点1,没有分配任务,根据限界函数估算目标函 数值为2+3+1+4=10; (2)在结点2,将任务1分配给人员a,获得的成本为9,目标 函数值为9 + (3+1+4)=17,超出目标函数的界[10, 14],将结点2 丢弃;在结点3,将任务2分配给人员a,获得的成本为2,目标 函数值为2 + (3+1+4)=10,将结点3加入待处理结点活结点表中; 在结点4,将任务3分配给人员a,获得的成本为7,目标函数值 为7 + (3+1+4)=15,超出目标函数的界[10, 14],将结点4丢弃; 在结点5,将任务4分配给人员a,获得的成本为8,目标函数值 为8 + (3+1+4)=16,超出目标函数的界[10, 14],将结点5丢弃; 南京信息工程大学计算机与软件学院 42 (3)在活结点表中选取目标函数值极小的结点3优先进行搜索; (4)在结点6,将任务1分配给人员b,获得的成本为2+6=8, 目标函数值为8+(1+4)=13,将结点6加入活结点表中;在结点7, 将任务3分配给人员b,获得的成本为2+3=5,目标函数值为 5+(1+4)=10,将结点7加入活结点表中;在结点8。将任务4分 配给人员b,获得的成本为2+7=9,目标函数值为9+(1+4)=14, 将结点8加入活结点表中; (5)在活结点表中选取目标函数值极小的结点7优先进行搜索; (6)在结点9,将任务1分配给人员c,获得的成本为5+5=10, 目标函数值为10+4=14,将结点9加入活结点表中;在结点10, 将任务4分配给人员c,获得的成本为5+8=13,目标函数值为 13+4=17,超出目标函数的界[10, 14],将结点10丢弃; 南京信息工程大学计算机与软件学院 43 (7)在活结点表中选取目标函数值极小的结点6优先进行搜 索; (8)在结点11,将任务3分配给人员c,获得的成本为8+1=9, 目标函数值为9+4=13,将结点11加入活结点表中;在结点12, 将任务4分配给人员c,获得的成本为8+8=16,目标函数值为 16+4=20,超出目标函数的界[10, 14],将结点12丢弃; (9)在活结点表中选取目标函数值极小的结点11优先进行搜 索; (10)在结点13,将任务4分配给人员d,获得的成本为 9+4=13,目标函数值为13,由于结点13是叶子结点,同时结 点13的目标函数值是活结点表中的极小值,所以,结点13对 应的解即是问题的最优解,搜索结束。 南京信息工程大学计算机与软件学院 44 为了在搜索过程中构建搜索经过的树结构, 为了在搜索过程中构建搜索经过的树结构,设一个表 ST,在活结点表中取出最小值结点进行扩充时,将最小值 ,在活结点表中取出最小值结点进行扩充时, 结点存储到表ST中 活结点表和表ST的数据结构为 人员i的数据结构为(人员 结点存储到表 中,活结点表和表 的数据结构为 人员 1分配的任务 任务 人员 分配的任务,任务 分配的任务 任务k, 人员ilb) PT (0,2, a10) ST (a) 扩展根结点后的状态 PT (2,1, b13) (2,4, b14) (3,1, c14) ST (0,2, a10) (2,3, b10) (c) 扩展结点 后的状态 扩展结点7后的状态 PT (2,4, b14) (3,1, c14) (3,4, d13) ST PT (2,1, b13) (2,3, b10) (2,4, b14) ST (0,2, a10) (b) 扩展结点 后的状态 扩展结点3后的状态 PT (2,4, b14) (3,1, c14) (1,3, c13) ST (0,2, a10) (2,3, b10) (2,1, b13) (d) 扩展结点 后的状态 扩展结点6后的状态 (0,2, a10) (2,3, b10) (2,1, b13) (1,3, c13) (e) 扩展结点 后的状态,最优解为 扩展结点11后的状态 最优解为2→a 1→b 3→c 4→d 后的状态, 图示 任务分配问题最优解的确定 回溯过程是: (3,4, d13)→(1,3, c13)→(2,1, b13)→(0,2, a10) 。 南京信息工程大学计算机与软件学院 45 算法——任务分配问题 任务分配问题 算法 1.根据限界函数计算目标函数的下界down;采用贪心法得到上界 ; .根据限界函数计算目标函数的下界 ;采用贪心法得到上界up; 2.将待处理结点活结点表初始化为空; .将待处理结点活结点表初始化为空; 3.for (i=1; i=n; i++) . x[i]=0; 4.k=1; i=0; //为第 个人分配任务,i为第 个人分配的任务 为第k个人分配任务 为第k-1个人分配的任务 . 为第 个人分配任务, 为第 5.while (k=1) . 5.1 x[k]=1; 5.2 while (x[k]=n) 5.2.1 如果人员 分配任务 如果人员k分配任务 分配任务x[k]不发生冲突,则 不发生冲突, 不发生冲突 5.2.1.1 计算目标函数值 计算目标函数值lb; 5.2.1.2 若lb=up,则将 存储在活结点表中; ,则将i,x[k], klb存储在活结点表中; 存储在活结点表中 5.2.2 x[k]=x[k]+1; 5.3 如果 =n且叶子结点的 值在活结点表中最小, 如果k= 且叶子结点的 值在活结点表中最小, 且叶子结点的lb值在活结点表中最小 则输出该叶子结点对应的最优解; 则输出该叶子结点对应的最优解; 5.4 否则,如果 =n且活结点表中的叶子结点的 值不是最小,则 否则,如果k= 且活结点表中的叶子结点的 值不是最小, 且活结点表中的叶子结点的lb值不是最小 5.4.1 up=活结点表中的叶子结点最小的 值; 活结点表中的叶子结点最小的lb值 活结点表中的叶子结点最小的 5.4.2 将活结点表中超出目标函数界的结点删除; 将活结点表中超出目标函数界的结点删除; 5.5 i=活结点表中 最小的结点的 活结点表中lb最小的结点的 活结点表中 最小的结点的x[k]值; 值 5.6 k=活结点表中 最小的结点的 值;k++; 活结点表中lb最小的结点的 活结点表中 最小的结点的k值 南京信息工程大学计算机与软件学院 46

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