(完整版)分支限界算法作业分配问题

第3章作业分配问题问题描述题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个货箱全部装船的方法。

要求:输出每艘船最终载重量.问题分析分支搜索法是一种在问题解空间上进行搜索尝试的算法。

是采用广度优先的策略国,依次搜索E-结点的所有分支,也就是所有的相邻结点。

和回溯法一样,在生成的结点中,抛弃那些不满足约束条件的结点,其余结点加入活结点表。

然后从表中选择一个结点作为下一个E-结点,断续搜索。

在分支定界算法中，每一个活结点只有一次机会成为扩展结点。

利用分支定界算法对问题的解空间树进行搜索，它的搜索策略是：(1)产生当前扩展结点的所有孩子结点；(2)在产生的孩子结点中，抛弃那些不可能产生可行解（或最优解）的结点；(3)将其余的孩子结点加入活结点表；(4)从活结点表中选择下一个活结点作为新的扩展结点。

如此循环，直到找到问题的可行解（最优解）或活结点表为空。

分支限界法的思想是：首先确定目标值的上下界，边搜索边减掉搜索树的某些支，提高搜索效率。

题1:先看一个实例,设有A,B,C,D,E 5人从事J1,J2,J3,J4,J5项工作，每人只能从事一项，他们的效益如图所示，求最佳安排使效益最高。

要求：输出每人所从事的工作项目以及最佳安排的最高效益。

考虑任意一个可行解,例如矩阵中的对角线是一个合法的选择,表示将任务J1分配给人员A,任务J2分配给人员B,任务J3分配给人员C,任务J4分配给D,任务J5分配给E,其总效益是10+10+7+11+4=42;或者应用贪心法求得一个近似解:人员A从事J2时效益最大,将任务J2分配给人员A,剩余工作中人员B从事J1时效益最大,任务J1分配给人员B,J3、J4、J5中人员D从事J4时效益最大,任务J4分配给人员D,J3和J5中人员C从事J3时效益最大,任务J3分配给人员C,任务J5只能分配给人员E,其总效益是11+13+11+7+4=46.显然,42和46都不能确定是最优解,有可能还有比其更大的效益,这两个解其一并不一定是一个最可行的选择,它们仅仅提供了一个参考,这样,可以以其中一个作为参考来进一步对各种作业分配方案进行搜索,比较其每种分配方式的效益.最大的总效益为最优解,其分配方案为最佳分配方案.题2:先看一个实例,当n=3,c1=c2=50,w={10,40,40}时,可将货箱1,2装到第一艘船上,货箱3装到第二艘船上.但如果w={20,40,40},则无法将货箱全部装船.由此可知问题可能有解,可能无解,也可能有多解.下面以找出问题的一个解为目标设计算法.虽然是关于两艘船的问题,其实只讨论一艘船的最大装载问题即可.因为当第一艘船的最大装载为bestw时,若w1+w2+…+wn-bestw<=c2则可以确定一种解,否则问题就无解.这样问题转化为第一艘船的最大装载问题.算法设计题1:问题的解空间为一个子集树,所有可能的解都可通过一个求解树给出.也就是算法要考虑任务是否分配给人员的情况组合,n个任务分配给n个人员的组合共n*n种情况,作业分配子集树是n=4的子集树它是用FIFO分支搜索算法解决该问题的扩展结点的过程编号的.1 个人作业分配2 3 13 4 2 24 5 3 4 5 35 4 5 5 4 4作业分配子集树在任务分配中,如实例中若n=4时,J1分配给A则向左走,否则往右走,直到走到最后,把最终的总效益求出,并把第一次求出的总效益作为最大效益与后边的总效益相比较,比其大者,交换两者,大的作为最大效益.依次方法,直到找到最优解,并输出其值以及其最大效益时的最佳分配方案.(1)用FIFO分支搜索所有的分支,并记录已搜索分支的最优解,搜索完子集树也就找出了问题的解.图中结点1为第零层,是初始E-结点;扩展后结点2,3为第一层;3,4,2是第一个任务分配出去后的下一层扩展结点,4,5,3,4,5是第二个任务分配出去后下一层的扩展结点(即分配情况).(2)用task[i]来表示任务是否分配及分配了给哪个工人,即task[i]=0时表示任务i 未分配, task[i]=j表示任务i分配给了工人j;用worker[k]=0或1来表示工人k是否分配了任务, worker[k]=0表示工人k未分配任务, worker[k]=1表示工人k已分配了任务.(3)把最低费用用mincost来表示和c[i][j]表示工人j执行任务i时的费用,并把c[i][j]和mincost分别初始化为c[1000][1000]和100000;同时把ask[i]和temp[i]、worker[i]的存储空间初始为task[1000]和temp[1000]、worker[1000],之后把其初始化为0.(4)用Plan(int k,unsigned int cost)来对分配作业的解空间树进行搜索,搜索的时候,每个活结点要记录下搜索的路径(即分配方案),存储在temp[i]中,并求出费用cost,然后cost与最小费用mincost进行比较,较小者是最小费用,其分配方案为最佳分配方案.(5)下面的算法中用Plan(int k,unsigned int cost)中的第二个for循环来实现对解空间树的搜索,第一次for(i=0)时，找出0号工人分别执行0，1，2，3，4号任务时总花费最小;第二次for(i=1)时，找出1号工人分别执行除0号工人的任务以外任务时总花费最小，并与i=0时的总花费最小比较;…;第五次for(i=4)时，找出总花费最小，并与上次的总花费最小比较;依次类推对解空间树进行搜索.第一个for循环把cost 与mincost进行比较,求出最小费用并记录出最小费用的分配方案.题2:转化为一艘船的最优化问题后,问题的解空间为一个子集树(问题的解空间树中的子集树).也就是算法要考虑所有物品取舍情况的组合.(1)要想求出最优解,必须搜索到叶结点.所以要记录树的层次,当层次为n+1时,搜索完全部叶结点,算法结束.不同于回溯算法,分支搜索过程中活结点的“层”是需要标识的,否则在入队后无法识别结点所在的层.下面算法,每处理完一层让“-1”入队,以此来标识“层”,并用记数变量i来记录当前层.(2)每个活结点要记录当前船的装载量.(3)为了突出算法思想,对数据结构队及其操作只进行抽象描述.用Queue代表队列类型，则Queue Q：定义了一个队列Q，相关操作有：add（Q，….）表示入队；Empty（Q）测试队列是否为空，为空则返回真值。

作业调度问题是指在多道程序系统中，根据各道程序的特点和系统的资源状况，合理地安排各道程序的执行顺序。

而分支限界法是一种解决排列、组合、0-1背包等问题的常用技术，可以有效地解决作业调度问题。

本文将结合Java语言，介绍如何使用分支限界法来解决作业调度问题。

一、作业调度问题的基本概念1. 作业调度问题的定义作业调度是指计算机系统对各种作业的安排和分配，以便使计算机系统有效地利用资源，提高各类作业的完成时间和各项资源的利用率。

2. 作业调度问题的类型作业调度问题主要分为单机调度和并行机调度两种类型。

其中单机调度是指一个作业在一台机器上进行处理，而并行机调度是指多个作业在多台机器上进行处理。

3. 作业调度问题的目标作业调度问题的主要目标是减少作业的等待时间，提高系统吞吐量，提高资源利用率，减少作业的周转时间等。

二、分支限界法的基本原理1. 分支限界法的概念分支限界法是一种剪枝技术，通过遍历搜索所有可能的解空间，并在搜索过程中剪掉某些明显不可能得到最优解的分支，从而有效地降低了搜索空间的规模。

2. 分支限界法的特点分支限界法在搜索过程中，通过剪枝操作，能够大大降低搜索空间的规模，提高搜索效率。

在解决NP难问题时，分支限界法通常能够得到较为满意的解。

3. 分支限界法的应用分支限界法被广泛应用于排列、组合、0-1背包、作业调度等各种组合优化问题的求解过程中，具有较高的实用性和效率。

三、分支限界法解决作业调度问题的具体步骤1. 确定问题的数学模型需要将作业调度问题转化为数学模型，例如采用Gantt图或者某种数学表达形式来描述作业的调度顺序和资源分配情况。

2. 设计合适的状态空间树根据问题的特点，设计合适的状态空间树来表示各种可能的作业调度方案，并利用分支限界法进行搜索。

3. 利用分支限界法进行搜索对设计好的状态空间树进行搜索，通过适当的剪枝操作，降低搜索空间的规模，提高搜索效率，直到找到最优解或者满意解为止。

分支限界法概述：分支定界(branch and bound) s搜索法是一种在问题的解空间树上搜索问题的解的方法。

分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树，并且，在分支定界算法中，每一个活结点只有一次机会成为扩展结点。

搜索策略1 产生当前扩展结点的所有孩子结点；2 在产生的孩子结点中，抛弃那些不可能产生可行解（或最优解）的结点；3 将其余的孩子结点加入活结点表；4 从活结点表中选择下一个活结点作为新的扩展结点。

5 如此循环，直到找到问题的可行解（最优解）或活结点表为空。

从活结点表中选择下一个活结点作为新的扩展结点根据选择方式的不同分支定界算法通常可以分为两种形式：①队列式（FIFO）分支限界法队列式分支限界法将活结点表组织成一个队列，并按队列的先进先出原则选取下一个结点为当前扩展结点②优先队列式的分支限界法将活结点表组织成一个队列，并按优先队列中规定的优先级选取优先级最高的下一个节点成为当前扩展节点最大优先队列：使用最大堆，体现最大效益优先最小优先队列：使用最小堆，体现最小费用优先分支限界法和回溯法的区别①求解目标不同：回溯法的求解目标是找出解空间树中满足约束条件的所有解分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解②搜索方式不同：回溯法以深度优先的方式搜索解空间树分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树③搜索问题的解空间树方面：在分支限界法中，每一个活结点只有一次机会成为扩展结点。

活结点一旦成为扩展结点，就一次性产生其所有儿子结点。

在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。

此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。

这个过程一直持续到找到所需的解或活结点表为空时为止。

什么是剪枝（以走迷宫举例）我们在“走迷宫”的时候，一般回溯法思路是这样的：1、这个方向有路可走，我没走过2、往这个方向前进3、是死胡同，往回走，回到上一个路口4、重复第一步，直到找着出口这样的思路很好理解，编程起来也比较容易。

分支限界法的研究与应用摘要：分支限界法与回溯法的不同:首先,回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。

其次，回溯法以深度优先的方式搜索解空间树，而分支限界法则一般以广度优先或以最小耗费优先的方式搜索解空间树。

再者，回溯法空间效率高；分支限界法往往更“快”。

分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。

在分支限界法中，每一个活结点只有一次机会成为扩展结点。

活结点一旦成为扩展结点，就一次性产生其所有儿子结点。

在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。

此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。

这个过程一直持续到找到所需的解或活结点表为空时为止。

常见的分支限界法有：队列式分支限界法，按照队列先进先出原则选取下一个结点为扩展结点。

栈式分支限界法，按照栈后进先出原则选取下一个结点为扩展结点。

优先队列式分支限界法，按照规定的结点费用最小原则选取下一个结点为扩展结点（最采用优先队列实现）。

分支搜索法是一种在问题解空间上进行搜索尝试的算法。

所谓分支是采用广度优先的策略国,依次搜索E-结点的所有分支,也就是所有的相邻结点。

和回溯法一样,在生成的结点中,抛弃那些不满足约束条件的结点,其余结点加入活结点表。

然后从表中选择一个结点作为下一个E-结点,断续搜索。

关键词：分支限界法回溯法广度优先分支搜索法目录第1章绪论 (3)1.1 分支限界法的背景知识 (3)1.2 分支限界法的前景意义 (3)第2章分支限界法的理论知识.................. 错误!未定义书签。

2.1 问题的解空间树 ............................................... 错误!未定义书签。

【分支限界法】批处理作业调度问题问题描述给定n个作业的集合{J1,J2,…,Jn}。

每个作业必须先由机器1处理，然后由机器2处理。

作业Ji需要机器j的处理时间为tji。

对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。

所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。

批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。

例：设n=3，考虑以下实例：这3个作业的6种可能的调度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它们所相应的完成时间和分别是19，18，20，21，19，19。

易见，最佳调度方案是1,3,2，其完成时间和为18。

限界函数批处理作业调度问题要从n个作业的所有排列中找出具有最小完成时间和的作业调度，所以如图，批处理作业调度问题的解空间是一颗排列树。

在作业调度问相应的排列空间树中，每一个节点E都对应于一个已安排的作业集。

以该节点为根的子树中所含叶节点的完成时间和可表示为：设|M|=r，且L是以节点E为根的子树中的叶节点，相应的作业调度为{pk,k=1,2,……n}，其中pk是第k个安排的作业。

如果从节点E到叶节点L的路上，每一个作业pk在机器1上完成处理后都能立即在机器2上开始处理，即从p r+1开始，机器1没有空闲时间，则对于该叶节点L有：注：(n-k+1)t1pk,因为是完成时间和，所以，后续的(n-k+1)个作业完成时间和都得算上t1pk。

如果不能做到上面这一点，则s1只会增加，从而有：。

类似地，如果从节点E开始到节点L的路上，从作业p r+1开始，机器2没有空闲时间，则：同理可知，s2是的下界。

由此得到在节点E处相应子树中叶节点完成时间和的下界是：注意到如果选择Pk，使t1pk在k>=r+1时依非减序排列，S1则取得极小值。

同理如果选择Pk使t2pk依非减序排列，则S2取得极小值。

第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个货箱全部装船的方法。

要求:输出每艘船最终载重量.3.2 问题分析分支搜索法是一种在问题解空间上进行搜索尝试的算法。

是采用广度优先的策略国,依次搜索E-结点的所有分支,也就是所有的相邻结点。

和回溯法一样,在生成的结点中,抛弃那些不满足约束条件的结点,其余结点加入活结点表。

然后从表中选择一个结点作为下一个E-结点,断续搜索。

在分支定界算法中，每一个活结点只有一次机会成为扩展结点。

利用分支定界算法对问题的解空间树进行搜索，它的搜索策略是：(1)产生当前扩展结点的所有孩子结点；(2)在产生的孩子结点中，抛弃那些不可能产生可行解（或最优解）的结点；(3)将其余的孩子结点加入活结点表；(4)从活结点表中选择下一个活结点作为新的扩展结点。

如此循环，直到找到问题的可行解（最优解）或活结点表为空。

分支限界法的思想是：首先确定目标值的上下界，边搜索边减掉搜索树的某些支，提高搜索效率。

题1:先看一个实例,设有A,B,C,D,E 5人从事J1,J2,J3,J4,J5项工作，每人只能从事一项，他们的效益如图所示，求最佳安排使效益最高。

要求：输出每人所从事的工作项目以及最佳安排的最高效益。

考虑任意一个可行解,例如矩阵中的对角线是一个合法的选择,表示将任务J1分配给人员A,任务J2分配给人员B,任务J3分配给人员C,任务J4分配给D,任务J5分配给E,其总效益是10+10+7+11+4=42;或者应用贪心法求得一个近似解:人员A 从事J2时效益最大,将任务J2分配给人员A,剩余工作中人员B从事J1时效益最大,任务J1分配给人员B,J3、J4、J5中人员D从事J4时效益最大,任务J4分配给人员D,J3和J5中人员C从事J3时效益最大,任务J3分配给人员C,任务J5只能分配给人员E,其总效益是11+13+11+7+4=46.显然,42和46都不能确定是最优解,有可能还有比其更大的效益,这两个解其一并不一定是一个最可行的选择,它们仅仅提供了一个参考,这样,可以以其中一个作为参考来进一步对各种作业分配方案进行搜索,比较其每种分配方式的效益.最大的总效益为最优解,其分配方案为最佳分配方案.题2:先看一个实例,当n=3,c1=c2=50,w={10,40,40}时,可将货箱1,2装到第一艘船上,货箱3装到第二艘船上.但如果w={20,40,40},则无法将货箱全部装船.由此可知问题可能有解,可能无解,也可能有多解.下面以找出问题的一个解为目标设计算法.虽然是关于两艘船的问题,其实只讨论一艘船的最大装载问题即可.因为当第一艘船的最大装载为bestw时,若w1+w2+…+wn-bestw<=c2则可以确定一种解,否则问题就无解.这样问题转化为第一艘船的最大装载问题.3.3 算法设计题1:问题的解空间为一个子集树,所有可能的解都可通过一个求解树给出.也就是算法要考虑任务是否分配给人员的情况组合,n个任务分配给n个人员的组合共n*n种情况,作业分配子集树是n=4的子集树它是用FIFO分支搜索算法解决该问题的扩展结点的过程编号的.1 个人作业分配2 3 13 4 2 24 5 3 4 5 3作业分配子集树在任务分配中,如实例中若n=4时,J1分配给A则向左走,否则往右走,直到走到最后,把最终的总效益求出,并把第一次求出的总效益作为最大效益与后边的总效益相比较,比其大者,交换两者,大的作为最大效益.依次方法,直到找到最优解,并输出其值以及其最大效益时的最佳分配方案.(1)用FIFO分支搜索所有的分支,并记录已搜索分支的最优解,搜索完子集树也就找出了问题的解.图中结点1为第零层,是初始E-结点;扩展后结点2,3为第一层;3,4,2是第一个任务分配出去后的下一层扩展结点,4,5,3,4,5是第二个任务分配出去后下一层的扩展结点(即分配情况).(2)用task[i]来表示任务是否分配及分配了给哪个工人,即task[i]=0时表示任务i未分配, task[i]=j表示任务i分配给了工人j;用worker[k]=0或1来表示工人k是否分配了任务, worker[k]=0表示工人k未分配任务, worker[k]=1表示工人k已分配了任务.(3)把最低费用用mincost来表示和c[i][j]表示工人j执行任务i时的费用,并把c[i][j]和mincost分别初始化为c[1000][1000]和100000;同时把ask[i]和temp[i]、worker[i]的存储空间初始为task[1000]和temp[1000]、worker[1000],之后把其初始化为0.(4)用Plan(int k,unsigned int cost)来对分配作业的解空间树进行搜索,搜索的时候,每个活结点要记录下搜索的路径(即分配方案),存储在temp[i]中,并求出费用cost,然后cost与最小费用mincost进行比较,较小者是最小费用,其分配方案为最佳分配方案.(5)下面的算法中用Plan(int k,unsigned int cost)中的第二个for循环来实现对解空间树的搜索,第一次for(i=0)时，找出0号工人分别执行0，1，2，3，4号任务时总花费最小;第二次for(i=1)时，找出1号工人分别执行除0号工人的任务以外任务时总花费最小，并与i=0时的总花费最小比较;…;第五次for(i=4)时，找出总花费最小，并与上次的总花费最小比较;依次类推对解空间树进行搜索.第一个for循环把cost与mincost进行比较,求出最小费用并记录出最小费用的分配方案.题2:转化为一艘船的最优化问题后,问题的解空间为一个子集树(问题的解空间树中的子集树).也就是算法要考虑所有物品取舍情况的组合.(1)要想求出最优解,必须搜索到叶结点.所以要记录树的层次,当层次为n+1时,搜索完全部叶结点,算法结束.不同于回溯算法,分支搜索过程中活结点的“层”是需要标识的,否则在入队后无法识别结点所在的层.下面算法,每处理完一层让“-1”入队,以此来标识“层”,并用记数变量i来记录当前层.(2)每个活结点要记录当前船的装载量.(3)为了突出算法思想,对数据结构队及其操作只进行抽象描述.用Queue代表队列类型，则Queue Q：定义了一个队列Q，相关操作有：add（Q，….）表示入队；Empty（Q）测试队列是否为空，为空则返回真值。

布线问题：如图1所示，印刷电路板将布线区域划分成n*m个方格。

精确的电路布线问题要求确定连接方格a的中点到b的中点的最短布线方案。

在布线时，电路只能沿直线或直角布线，如图1所示。

为了避免线路相交，已经布线的方格做了封锁标记（如图1中阴影部分），其他线路不允许穿过被封锁的方格。

3 问题的算法选择题目的要求是找到最短的布线方案，从图1的情况看，可以用贪婪算法解决问题，也就是从a开始朝着b的方向垂直布线即可。

实际上，再看一下图2，就知道贪婪算法策略是行不通的。

因为已布线的放个没有规律的所以直观上说只能用搜索方法去找问题的解。

根据布线方法的要求，除边界或已布线处，每个E-结点分支扩充的方向有4个：上、下、左、右，也就是说，一个E-结点扩充后最多产生4个活结点。

以图2的情况为例，图的搜索过程如图3所示。

搜索以a为第一个E-结点，以后不断扩充新的活结点，直到b结束（当然反之也可以）。

反过来从b到a，按序号8-7-6-5-4-3-2-1就可以找到最短的布线方案。

从图3中也可以发现最短的布线方案是不唯一的。

且由此可以看出，此问题适合用分支限界搜索。

#include <stdio.h>#include <stdlib.h>typedef struct Position{int row;int col;}Position;typedef struct team{int x;int y;struct team *next;}team,*TEAM;Position start,end,path[100];TEAM team_l=NULL;int a[100][100];int m,n,path_len;void output(){int i,j;printf("\n|-------------------布线区域图-------------------|\n");for(i=0;i<m+2;i++){for(j=0;j<n+2;j++){printf("%5d",a[i][j]);}printf("\n");}printf("|------------------------------------------------|\n");return;}void input_data(){char yes;int x,y;printf("创建布线区域...\n\n");printf("请输入区域大小(行列的个数): ");scanf("%d,%d",&m,&n);printf("请输入开始点坐标(x,y): ");scanf("%d,%d",&start.row,&start.col);printf("请输入结束点坐标(x,y): ");scanf("%d,%d",&end.row,&end.col);printf("区域内是否有被占用点? (y/n) ");fflush(stdin);scanf("%c",&yes);fflush(stdin);while(yes=='y'){printf("请输入占用点的坐标(x,y): ");scanf("%d,%d",&x,&y);fflush(stdin);if(x<0 || x>m+1 || y<0 || y>n+1 || (x==start.row && y==start.col) || (x==end.row && y==end.col)){printf("输入错误,请重新输入\n");continue;}else{a[x][y]=-1;}printf("是否还有被占用点? (y/n) ");scanf("%c",&yes);fflush(stdin);}for(x=0;x<m+2;x++){a[0][x]=-1;a[m+1][x]=-1;}for(x=0;x<n+2;x++){a[x][0]=-1;a[x][n+1]=-1;}return;}void inq(Position p){TEAM t,q;q=team_l;t=(TEAM)malloc(sizeof(TEAM));t->x=p.row;t->y=p.col;t->next=NULL;if(team_l==NULL){team_l=t;return ;}while(q->next!=NULL){q=q->next;}q->next=t;return;}Position outq(){Position out;out.row=team_l->x;out.col=team_l->y;team_l=team_l->next;return out;}void find_path(){Position offset[4];Position here={start.row,start.col};Position nbr={0,0};int num_of_nbrs=4;int i,j;offset[0].row=0;offset[0].col=1; //右offset[1].row=1;offset[1].col=0; //下offset[2].row=0;offset[2].col=-1;//左offset[3].row=-1;offset[3].col=0;//上printf("\n开始搜索路径...\n");if((start.row == end.row)&&(start.col == end.col)){ path_len = 0;return;}while(1){for(i=0;i<num_of_nbrs;i++){nbr.row=here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(a[nbr.row][nbr.col]==0){a[nbr.row][nbr.col]=a[here.row][here.col] + 1;if((nbr.row == end.row) && (nbr.col == end.col)) break;inq(nbr); //nbr入队}}//是否到达目标位置finishif((nbr.row == end.row) && (nbr.col == end.col)) break;//或节点队列是否为空if(team_l==NULL){printf("\n没有结果\n");return ;}here=outq();}path_len=a[end.row][end.col];here=end;for(j=path_len-1;j>=0;j--){path[j] = here;for(i = 0;i < num_of_nbrs;i++){nbr.row = here.row + offset[i].row;nbr.col = here.col + offset[i].col;if(a[nbr.row][nbr.col] == j) //+ 2)break;}here=nbr;}return;}void out_path(){int i;printf("\n路径为:\n");printf("(%d,%d) ",start.row,start.col);for(i=0;i<path_len;i++){printf("(%d,%d) ",path[i].row,path[i].col);}printf("\n");return;}void main(){input_data();output();find_path();out_path();output(); }。

分支限界法典型例题分支限界法(Branch and Bound)是一种常见的算法分析技术,用于解决搜索问题和动态规划问题。

以下是一些分支限界法的典型例题:1. 最长公共子序列(LCS):求给定两个字符串的最长公共子序列。

可以使用分支限界法,首先找出两个字符串中的不同字符出现的次数,然后用哈希表存储这些计数器。

最后,遍历哈希表中的每个计数器,找到最大的计数器的值,即为最长公共子序列的长度。

2. 背包问题(Knapsack problem):给定一个背包,容量为64,有多个选项,每个选项的重量和容量不限。

求给定背包中可以放入的最大重量的背包物品。

可以使用分支限界法,首先列出所有可能背包容量的组合,然后用枚举法找出每个背包容量下可以放入的最大重量的物品,最后计算出可以放入的最大重量的物品数量。

3. 最短路径问题(Shortest Path problem):给定一个二维图,目标为找到从源点出发,到达所有目标点的路径。

可以使用分支限界法,首先找出图中的所有节点和它们之间的联系,然后用递归算法计算每个节点到源点的路径。

最后,通过剪枝,可以找到最短路径。

4. 最大子数组和问题(Maximum Subarray and Problem):给定一个数组,求出其中任意一个元素的最大值。

可以使用分支限界法,首先找出数组中的最小值和最大值,然后用递归算法计算每个元素的最大值。

最后,通过剪枝,可以找到最大子数组和问题。

5. 模拟退火问题(Simulated Annealing Problem):给定一个概率分布,求出在一定条件下,随机变量的取值分布。

可以使用分支限界法,首先找出概率分布中所有可能的取值,然后用模拟退火算法计算在这些取值中随机变量的取值分布。

最后,通过剪枝,可以找到最优解。

分支限界法求解批作业处理调度问题的实验总结(一)前言本文将介绍分支限界法在求解批作业处理调度问题中的实验结果，并总结这种方法在实践中的应用效果。

批作业处理调度问题是一个经典的优化问题，通过引入分支限界法求解，可以有效提高求解效率。

正文问题描述批作业处理调度问题是将一批作业分配给多台处理机，使得总完成时间最短。

每个作业有一个处理时间，各个处理机的处理速度可能不同，且每个处理机同时只能处理一项作业。

问题的目标就是找到一个合适的作业分配方案，使得总完成时间最小。

分支限界法原理分支限界法是一种优化算法，通过不断剪枝和界限约束，逐步地搜索最优解。

在批作业处理调度问题中，分支限界法的基本思想是将问题划分为子问题，并通过计算每个子问题的上界，动态地选择优先搜索的分支。

本次实验选取了一批作业和多台处理机，随机生成了作业的处理时间和处理机的处理速度。

利用分支限界法和贪心算法分别求解了批作业处理调度问题，并比较了两者的求解效果。

实验结果实验结果显示，分支限界法在求解批作业处理调度问题时表现出了较高的效率和准确性。

与贪心算法相比，分支限界法能够找到更优的作业分配方案，并且所需的计算时间相对较短。

实际应用分支限界法在实际生产中广泛应用于调度问题的求解。

无论是生产线的作业调度、机器设备的任务分配，还是人员的排班安排，都可以通过分支限界法来优化求解。

其高效的搜索方式和较好的求解结果使其成为一种实用的求解方案。

结尾通过本次实验，我们验证了分支限界法在求解批作业处理调度问题中的有效性。

分支限界法不仅能够在较短的时间内找到较优的解决方案，而且还可以应用于各种实际的调度问题。

希望通过本文的介绍，能够增加对分支限界法的了解和认识，并促进其在实际应用中的推广和应用。

为了求解批作业处理调度问题，我们使用了分支限界法和贪心算法两种方法进行对比。

首先，我们随机生成了一批作业和多台处理机。

每个作业的处理时间和每台处理机的处理速度也随机生成。

这样可以模拟实际情况中作业的不同耗时和处理机的不同处理能力。

0033算法笔记分支限界法分支限界法与单源最短路径问题 0033算法笔记-分支限界法分支限界法与单源最短路径问题1、分支限界法(1)叙述：使用广度优先产生状态空间一棵的结点，并采用剪枝函数的方法称作分枝限界法。

所谓“分支”是采用广度优先的策略，依次生成扩展结点的所有分支（即为：儿子结点）。

所谓“限界”是在结点扩展过程中，计算结点的上界（或下界），边搜索边减去搜寻一棵的某些分支，从而提升搜寻效率。

(2)原理：按照广度优先的原则，一个活结点一旦成为扩展结点（e-结点）r后，算法将依次生成它的全部孩子结点，将那些导致不可行解或导致非最优解的儿子舍弃，其余儿子加入活结点表中。

然后，从活结点表中取出一个结点作为当前扩展结点。

重复上述结点扩展过程，直至找到问题的解或判定无解为止。

(3)分支限界法与回溯法1)解目标：追溯法的解目标就是找到求解空间树中满足用户约束条件的所有求解，而分支限界法的解目标则就是找到满足用户约束条件的一个求解，或是在八十足约束条件的解中找出在某种意义下的最优解。

2)搜寻方式的相同：追溯法以深度优先的方式搜寻求解空间一棵，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

(4)常见的分支限界法1)fifo分支限界法(队列式分支限界法)基本思想：按照队列先进先出(fifo)原则选取下一个活结点为扩展结点。

搜寻策略：一已经开始，根结点就是唯一的活结点，根结点入队。

从活结点队中抽出根结点后，做为当前拓展结点。

对当前拓展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足用户约束函数的儿子重新加入活结点队列中。

再从活结点表抽出队首结点（队中最先进去的结点）为当前拓展结点，……，直至找出一个求解或活结点队列入空年才。

2)lc(leastcost)分支限界法(优先队列式分支限界法)基本思想：为了加速搜索的进程，应采用有效地方式选择活结点进行扩展。

按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。

实验五分支限界算法的应用一、实验目的1．掌握分支限界算法的基本思想、技巧和效率分析方法。

2．熟练掌握用分支限界算法的基本步骤和算法框架，FIFO搜索，LIFO搜索，优先队列式搜索的思想。

3．学会利用分支限界算法解决实际问题。

二、算法问题描述批处理作业调度问题：n个作业{1, 2, …, n}要在两台机器上处理，每个作业必须先由机器1处理，然后再由机器2处理，机器1处理作业i所需时间为ai，机器2处理作业i所需时间为bi（1≤i≤n），批处理作业调度问题（batch-job scheduling problem）要求确定这n个作业的最优处理顺序，使得从第1个作业在机器1上处理开始，到最后一个作业在机器2上处理结束所需时间最少。

注意：由于要从n个作业的所有排列中找出具有最早完成时间的作业调度，所以，批处理作业调度问题的解空间是一棵排列树，并且要搜索整个解空间树才能确定最优解，因此，其时间性能是O(n!)。

在搜索过程中利用已得到的最短完成时间进行剪枝，才能够提高搜索速度。

三、算法设计批处理作业调度问题要从n个作业的所有排列中找出具有最小完成时间和的作业调度，所以如图，批处理作业调度问题的解空间是一颗排列树。

在作业调度问相应的排列空间树中，每一个节点E都对应于一个已安排的作业集。

以该节点为根的子树中所含叶节点的完成时间和可表示为：设|M|=r，且L是以节点E为根的子树中的叶节点，相应的作业调度为{pk,k=1,2,……n}，其中pk是第k个安排的作业。

如果从节点E到叶节点L的路上，每一个作业pk在机器1上完成处理后都能立即在机器2上开始处理，即从pr+1开始，机器1没有空闲时间，则对于该叶节点L有：注：(n-k+1)t1pk,因为是完成时间和，所以，后续的(n-k+1)个作业完成时间和都得算上t1pk。

如果不能做到上面这一点，则s1只会增加，从而有：。

类似地，如果从节点E开始到节点L的路上，从作业pr+1开始，机器2没有空闲时间，则：同理可知，s2是的下界。

批处理作业调度_分⽀限界法⼀、问题描述给定 n 个作业的集合 j = {j1, j2, …, jn}。

每⼀个作业 j[i] 都有两项任务分别在两台机器上完成。

每⼀个作业必须先由机器1 处理，然后由机器2处理。

作业 j[i] 需要机器 j 的处理时间为 t[j][i] ，其中i = 1, 2, …, n, j = 1, 2。

对于⼀个确定的作业调度，设F[j][i]是作业 i 在机器 j 上的完成处理的时间。

所有作业在机器2上完成处理的时间之和 f = sigma F[2][i] 称为该作业调度的完成时间之和。

批处理作业调度问题要求对于给定的 n 个作业，制定最佳作业调度⽅案，使其完成时间和达到最⼩。

⼆、解题思路及所选算法策略的可⾏性分析⽤优先队列式分⽀限界法解决此问题。

由于要从n个作业的所有排列中找出有最⼩完成时间和的作业调度，所以批处理作业调度问题的解空间树是⼀颗排列树。

对于批处理作业调度问题，可以证明存在最佳作业调度使得在机器1和机器2上作业以相同次序完成(因为每个作业必须先在机器1上完成作业才能在机器2上进⾏作业)。

如果对于未安排的作业，对于其中⼀个作业，每当该作业在机器1上完成处理后都能⽴即在机器2上开始处理，则机器1没有空闲时间，达到满⼯作状态，将此情况的未安排作业在机器2上的⼯作时间总和记为S1，同理将机器2满⼯作状态的情况下的⼯作时间总和记为S2，则必有：所有作业机器2上完⼯时间和 >= 已安排作业机器2上完⼯时间和 + max{S1,S2}其中当未安排作业按照在机器1、2上⼯作时间⾮递减顺序进⾏调度时，S1和S2同时取得极⼩值且和调度⽆关，由此可作为分⽀限界法中的限界函数。

伪代码描述及复杂度分析bbFlow(){对各作业在机器1和2上作旭时间排序do{if(到达叶结点){if(当前作业安排机器2上完成时间和 < bestc){更新bestc；更新最优解；}}else{For(int i=enode.已安排作业数; i<总作业数; i++){求得当前下届bb；If(bb < bestc){结点插⼊最⼩堆；}}}取下⼀个拓展结点；}while（enode!=null&&enode.s<=n）}三、代码实现package分⽀限界法;public class Nodes implements Comparable {int s;//已安排作业数int sf2;//当前机器2上的完成时间和int bb;//当前完成时间和下界int[] f;//f[1]机器1上最后完成时间，f[2]机器2上最后完成时间int[] x;//当前作业调度public Nodes(int n){//最⼩堆结点初始化x=new int[n];for(int i=0;i<n;i++)x[i]=i;s=0;f=new int[3];f[1]=0;f[2]=0;sf2=0;bb=0;}public Nodes(Nodes e,int[] ef,int ebb,int n){//最⼩堆新结点x=new int[n];for(int i=0;i<n;i++)x[i]=e.x[i];f=ef;sf2=e.sf2+f[2];bb=ebb;s=e.s+1;}@Overridepublic int compareTo(Object o) {int xbb=((Nodes) o).bb;if(bb<xbb) return -1;if(bb==xbb) return 0;return 1;}}public class BBFlow {public int n;//作业数public int bestc;//最⼩完成时间和public int [][]m;//n个作业所需的处理时间数组public int [][]b;//n个作业所需的处理时间排序数组public int[][] a;//数组m和b的对应关系数组public int[] bestx;//最优解public boolean[][] y;//⼯作数组public BBFlow(int n,int[][] m){this.n=n;bestc=10000;this.m=m;b=new int[n][2];a=new int[n][2];bestx=new int[n];y=new boolean[n][2];}public void swap(int[][] b,int i,int j,int k,int t){int temp=b[i][j];b[i][j]=b[k][t];b[k][t]=temp;}public void swap(int[] x,int i,int j){int temp=x[i];x[i]=x[j];x[j]=temp;}* 对n个作业在机器1和2上所需时间排序*/public void sort(){int[] c=new int[n];for(int j=0;j<2;j++){for(int i=0;i<n;i++){b[i][j]=m[i][j];c[i]=i;}for(int i=0;i<n-1;i++){for(int k=n-1;k>i;k--){if(b[k][j]<b[k-1][j]){swap(b,k,j,k-1,j);swap(c,k,k-1);}}}for(int i=0;i<n;i++)a[c[i]][j]=i;}}/*** 计算完成时间和下界* @param enode* @param f* @return*/public int bound(Nodes enode,int[] f){for(int k=0;k<n;k++){for(int j=0;j<2;j++){y[k][j]=false;}}for(int k=0;k<enode.s;k++){for(int j=0;j<2;j++){y[a[enode.x[k]][j]][j]=true;}}f[1]=enode.f[1]+m[enode.x[enode.s]][0];f[2]=((f[1]>enode.f[2])?f[1]:enode.f[2])+m[enode.x[enode.s]][1];int sf2=enode.sf2+f[2];int s1=0;int s2=0;int k1=n-enode.s;int k2=n-enode.s;int f3=f[2];//计算s1的值for(int j=0;j<n;j++){if(!y[j][0]){k1--;if(k1==n-enode.s-1)f3=(f[2]>f[1]+b[j][0])?f[2]:f[1]+b[j][0];s1+=f[1]+k1*b[j][0];}}//计算s2的值for(int j=0;j<n;j++){if(!y[j][1]){k2--;s1+=b[j][1];s2+=f3+k2*b[j][1];}//返回完成时间和下界return sf2+((s1>s2)?s1:s2);}/*** 优先队列式分⽀限界法解批处理作业调度问题* @param nn* @return*/public int bbFlow(int nn){n=nn;sort();//对n个作业在机器1和2上所需时间排序LinkedList<Nodes> heap=new LinkedList<Nodes>();Nodes enode =new Nodes(n);//搜索排列空间树do{if(enode.s==n){//叶节点if(enode.sf2<bestc){bestc=enode.sf2;for(int i=0;i<n;i++){bestx[i]=enode.x[i];}}}else{//产⽣当前扩展结点的⼉⼦结点for(int i=enode.s;i<n;i++){swap(enode.x,enode.s,i);int[] f=new int[3];int bb=bound(enode,f);if(bb<bestc){//⼦树可能含有最优解//结点插⼊最⼩堆Nodes node=new Nodes(enode,f,bb,n);heap.add(node);Collections.sort(heap);}swap(enode.x,enode.s,i);}//完成结点扩展}//取下⼀个扩展结点enode=heap.poll();}while(enode!=null&&enode.s<=n);return bestc;}public static void main(String[] args) {int n=3;int[][] m={{2,1},{3,1},{2,3}};//m的下标从0开始BBFlow f=new BBFlow(n,m);f.bbFlow(n);System.out.println("最优批处理作业调度顺序为：");for(int i=0;i<n;i++)System.out.print((f.bestx[i]+1)+" ");System.out.println();System.out.println("最优调度所需的最短时间为："+f.bestc); }}/**************************运⾏结果*最优批处理作业调度顺序为：*1 3 2*最优调度所需的最短时间为：18 *************************/。