分支限界算法作业分配问题

分支限界法的研究与应用摘要：分支限界法与回溯法的不同:首先,回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。其次，回溯法以深度优先的方式搜索解空间树，而分支限界法则一般以广度优先或以最小耗费优先的方式搜索解空间树。再者，回溯法空间效率高；分支限界法往往更“快”。分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。常见的分支限界法有：队列式分支限界法，按照队列先进先出原则选取下一个结点为扩展结点。栈式分支限界法，按照栈后进先出原则选取下一个结点为扩展结点。优先队列式分支限界法，按照规定的结点费用最小原则选取下一个结点为扩展结点（最采用优先队列实现）。分支搜索法是一种在问题解空间上进行搜索尝试的算法。所谓分支是采用广度优先的策略国,依次搜索E-结点的所有分支,也就是所有的相邻结点。和回溯法一样,在生成的结点中,抛弃那些不满足约束条件的结点,其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点,断续搜索。关键词：分支限界法回溯法广度优先分支搜索法-1-目录第1章绪论...................................................................................31.1分支限界法的背景知识...........................................................................31.2分支限界法的前景意义...........................................................................3第2章分支限界法的理论知识..................错误!未定义书签。2.1问题的解空间树...............................................错误!未定义书签。2.2分支限界法的一般性描述.............................................................6第3章作业分配问题...................................................................73.1问题描述......................................................................................73.2问题分析......................................................................................73.3算法设计......................................................................................83.4算法实现....................................................................................103.5测试结果与分析.........................................................................12第4章结论.................................................................................13参考文献................................................................................................................14-2-第1章绪论1.1分支限界法的背景知识分支搜索法是一种在问题解空间上进行搜索尝试的算法。所谓分支是采用广度优先的策略国,依次搜索E-结点的所有分支,也就是所有的相邻结点。和回溯法一样,在生成的结点中,抛弃那些不满足约束条件的结点,其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点,断续搜索。（1)FIFO搜索先进先出搜索算法要依赖“队”做基本的数据结构。一开始,根结点是唯一的活结点,根结点入队。从活结点队中取出根结点后,作为当前扩展结点。对当前扩展结点,先从左到右地产生它的所有儿子,用约束条件检查,把所有满足约束函数的儿子加入活结点队列中。再从活结点表中取出队首结点为当前扩展结点,……,直到找到一个解或活结点队列为空为止。（2)LIFO搜索后进先出搜索算法要依赖“栈”做基本的数据结构。一开始,根结点入栈.从栈中弹出一个结点为当前扩展结点。对当前扩展结点,先从左到右地产生它的所有儿子,用约束条件检查,把所有满足约束函数的儿子入栈,再众栈中弹出一个结点为当前扩展结点,……，直到找到一个解或栈为空为止。（3）优先队列式搜索为了加速搜索的进程，应采用有效地方式选择E-结点进行扩展。优先队列式搜索，对每一活结点计算一个优先级，并根据这些优先级，从当前活结点表中优先选择一个优先级最高的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。1.2分支限界法的前景意义在现实生活中，有这样一类问题：问题有n个输入，而问题的解就由n个输入的某种排列或某个子集构成，只是这个排列或子集必须满足某些事先给定的条件。把那些必须满足的条件称为约束条件；而把满足约定条件的排列或子集称为该问题的可行解。满足约束条件的子集可能不止一个，也就量说可行解一般来说是不唯一的。为了衡量可行解的优劣，事先也可能给出了一定的标准，这些标准一般以函数-3-形式给出，这些函数称为目标函数。那些使目标函数取极值的可行解，称为最优解。如工作安排问题，任意顺序都是问题的可行解，人们真正需要的是最省时间的最优解。用回溯算法解决问题时，是按深度优先的策略在问题的状态空间中，尝试搜索可能的路径，不便于在搜索过程中对不同的解进行比较，只能在搜索到所有解的情况下，才能通过比较确定哪个是最优解。这类问题更适合用广度优先策略搜索，因为在扩展结点时，可以在E-结点的各个子结点之间进行必要的比较，有选择地进行下一步扩展。分支限界法就是一种比较好的解决最优化问题的算法。分支限界法是由“分支”策略和“限界”策略两部分组成。“分支”策略体现在对问题空间是按广度优先的策略进行搜索；“限界”策略是为了加速搜索速度而采用启发信息剪枝的策略。第2章分支限界法的理论知识2.1问题的解空间树1x1=1x1=023x2=1x2=0x2=1x2=04567x3=1x3=0x3=1x3=0x3=1x3=0x3=1x3=089101112131415子集树在FIFO分支搜索方法中,在搜索当前E-结点全部儿子后,其儿子成为活结点,E--4-结点变为死结点;活结点存储在队列中,队首的活结点出队后变为E-结点,其再生成其他活结点的儿子……直到找到问题的解或活结点队列为空搜索完毕.这里采用地构造解空间二叉树的方法,问题的解就是二叉树中的某一个分支.这个解是要搜索到二叉树的叶结点才能确定的,且只须记录最优解的叶结点,就能找到问题的解.比较方便的存储方式是二叉树要有指向父结点的指针,以便从叶结点回溯解的方案.又为了方便知道当前结点的情况,还要记录当前结点是父结点的哪一个儿子.FIFO分支搜索算法框架如下:假定问题解空间树为T,T至少包含一个解结点(答案结点).u为当前的最优解,初值为一个较大的数;E表示当前扩展的活结点,x为E的儿子,s(x)为结点x下界函数,当其值比u大时,不可能为最优解,不断续搜索此分支,该结点不入队;当其值比u小时,可能达到最优解,断续搜索此分支,该结点入队;cost(X)当前叶结点所在分支的解.search(T){leaf=0;初始化队;ADDQ(T);parent(E)=0;while(队不空){DELETEQ(E)for(E的每个儿子X)if(s(X)u){ADDQ(X);parent(X)=E;if(X是解结点){U=min(cost(X),u);leaf=x;}}}printf(leastcost=%f,u);-5-while(leaf!=0){printf(%f,leaf);leaf=parent(leaf);}}找最小成本的LC分支-限界算法框架与FIFO分支-限界算法框架结构大致相同,只是扩展结点的顺序不同,因而存储活结点的数据结构不同.FIFO分支-限界算法用队存储活结点,LC分支-限界算法用堆存储活结点,以保证比较优良的结点行被扩展.且对于LC分支-限界算法,当扩展到叶结点就已经找到最优解,可以停止搜索.2.2分支限界法的一般性描述分支限界有3种不同的搜索方式:FIFO、LIFO和优先队列。对于先进先出搜索(FIFO),其算法要依赖“队”做基本的数据结构。一开始,根结点是唯一的活结点,根结点入队。从活结点队中取出根结点后,作为当前扩展结点。对当前扩展结点,先从左到右地产生它的所有儿子,用约束条件检查,把所有满足约束函数的儿子加入活结点队列中。再从活结点表中取出队首结点为当前扩展结点,……,直到找到一个解或活结点队列为空为止。对于后进先出搜索(LIFO),其算法要依赖“栈”做基本的数据结构。一开始,根结点入栈.从栈中弹出一个结点为当前扩展结点。对当前扩展结点,先从左到右地产生它的所有儿子,用约束条件检查,把所有满足约束函数的儿子入栈,再众栈中弹出一个结点为当前扩展结点,……，直到找到一个解或栈为空为止。对于优先队列式扩展方式，不加入限界策略其实是无意义的，因为要说明解的最优性，必需搜索完问题全部解空间，才能下结论。优先队列式搜索通过结点的优先级，可以使搜索尽快朝着解空间树上有最优解的分支推进，这样当前最优解一定较接近真正的最优解。其后将当前最优解作为一个“标准”，对上界（或下界）不可能达到（或大于）这个“标准”的分支，则不去进行搜索，这样剪枝的效率更高，能较好地缩小搜索范围，从而提高搜索效率。这种搜索策略称为优先队列式分支限界法，即“LC-检索”。优先队列式分支限界法进行算法设计的要点如下：（1）结点扩展方式：无论哪种分支限界法，都需要有一张活结点表。优先队列的分支限界法将活结点组织成一个优先队列，并按优先队列中规定的结点优先级-6-选取优先级最高的下一个结点成为当前扩展结点。（2）结点优先级确定：优先队列中结点优先级常规定为一个与该结点相关的数值w，w一般表示以该结点为根的子树中的分支（其中最优的分支）接近最优解的程度。（3）优先队列组织：结点优先级确定后，按结点优先级进行排序，就生成了优先队列。排序算法的时间复杂度较高，考试到搜索算法每次只扩展一个结点，使用数据结构中介绍的堆排序比较合适，这样每次扩展结点时，比较交换的次数最少。第3章作业分配问题3.1问题描述题1:作业分配问题：设有A,B,C,D,E,…等n个人从事J1,J2,J3,J4,J5,…等n项工作，每人只能从事一项任务，每个任务由不同的工人从事有着不同的费用，求最佳安排使费用最低。要求：输出每人所从事的工作任务以及最佳安排的最低费用。题2:有两艘船和需要装运的n个货箱，第一艘船的载重量是c1，第二艘船的载重量是c2，Wi是货箱i的重量，且W1+W2+W3+W4+......+Wn=c1+c2。希望确定是否有一种可将所有n个货箱全部装