算法设计方法 教学课件 ppt 作者 吴哲辉第7章

算法设计方法吴哲辉崔焕庆马炳先吴振寰

编著机械工业出版社1第7章分支限界算法回溯算法的基本思想旅行售货员问题N后问题图的m着色问题0-1背包问题批处理作业调度问题哈密尔顿回路问题子集和问题回溯法效率分析27.1基本思想分支限界方法（BranchandBound）是一种类似于回溯法的方法，它也是在一个问题的解空间树上采用一定的策略搜索问题解的算法，但是在搜索顺序和剪枝手段上，同回溯法有明显的不同。其基本思想是：当一个活结点成为当前的可扩展结点后，生成该结点的所有子结点，而后利用剪枝函数舍弃或者杀死不会产生可行解或者不会产生最优解的结点，将未被杀死的结点加入到活结点表中。而后利用一定的策略从活结点表中取出一个活结点作为当前的可扩展结点，并重复上述过程，直到找到所需要的解或者活结点表为空为止。37.1基本思想可见，分支限界方法是在生成当前可扩展结点的所有子结点后，再生成其他活结点的子结点，并利用剪枝函数在搜索过程中避免生成不包含（最优）解结点的子树，类似于图的广度优先搜索；而回溯法则是从当前可扩展结点出发，一直搜索下去，直到找到一个解结点或者确定无解为止，类似于图的深度优先搜索。这是两种方法在搜索方式上的区别。另一方面，回溯法通常用于找到解空间中的所有可行解，而分支限界法主要用于求解一个可行解或者寻找最优解。47.1基本思想依照从活结点表中取一个活结点作为当前可扩展结点的策略不同，有三种分支限界搜索方法。1.先进先出方式（FirstInFirstOut，简称为FIFO方式）。该方式将活结点表用队列进行组织，每次总是选择最先生成的活结点作为当前的可扩展结点。2.后进先出方式（LastInFirstOut，简称为LIFO方式）。该方式将活结点表用堆栈进行组织，每次总是选取最后生成的活结点作为当前的可扩展结点。3.最小成本搜索（LeastCostSearch）。该方式需要设置一个成本估计函数，估计从活结点产生解结点的成本，每次总是选择能够“最快”产生解结点的活结点作为当前的可扩展结点。这种方式称为LC分支限界方法（有的文献中称为优先队列式分支限界方法）。57.1基本思想LC分支限界方式的基本思想。这类方法在求解问题时，需要对问题做深入细致的分析，获得有效信息以减少搜索，这类信息称为启发性信息。而利用启发性信息进行搜索的过程称为启发式搜索。在搜索解空间树的过程中，通常选择可以最快达到解结点的活结点进行优先扩展。为此，需要对各个活结点设置一定的“优先级”，使得在选择活结点作为可扩展结点时，可以选择优先级最大的活结点，从而解决FIFO和LIFO方式中可扩展结点选择的盲目性。67.1基本思想我们把与每个结点X对应的优先级定义为一个函数C(X)，将该函数称为成本函数，其定义为：如果X是解结点，则是由解空间树的根结点到X结点的成本；如果X不是解结点，且以X为根的子树不包含任何解结点，则，如果以X为根结点的子树包含解结点，则为该子树中具有最小成本的解结点的成本。要得到C(X)的精确值通常是不现实的。此时，可以用估计函数来代替，估计函数是对成本函数的估计。为了不使算法偏向于做纵深搜索，需要估计函数不仅估计从结点X到一个解结点的可能成本，而且需要估计由解空间树的根结点到X结点的成本。算法7.1LC-搜索的抽象化描述算法7.2LCBB的抽象描述77.20-1背包问题C(X)的定义：若X是可行解结点，那么若X是叶结点，但不是可行解结点，那么若X不是叶结点，那么在LCBB算法中，算法7.3就是来求解在确定了前j-1个物品的装包方案之后，将剩余的物品尽可能向背包中装，由此而得到的背包中物品的价值。

87.20-1背包问题例7.1假设n=4，P=(10,10,12,18)，W=(2,4,6,9)，。利用LCBB方法求解此0-1背包问题。此问题用LCBB方法给出的解空间树如图所示。97.20-1背包问题当利用LCBB算法（算法7.2）来求解0-1背包问题时，需要解决以下问题。(1)解空间树中每个结点的存储结构。(2)如何生成一个结点的子结点。(3)如何识别一个可行解结点。(4)活结点表的表示及其操作。算法7.4~7.7LCBB算法107.20-1背包问题例7.2考虑个物品，背包容量100，W=(30,20,20,50,40)，P=(65,40,30,60,40)。117.3旅行售货商问题利用分支限界策略来求解TSP方法，可以从两个角度进行考虑：(1)在周游路线中，由于每个结点（城市）必须经过且仅能经过一次，因此，可以从出发点开始，逐个考察经过结点的次序，并借助LCBB思想去寻求最优解。此时，将周游路线看作顶点的集合。(2)从图中边的角度来考虑，一条边只有两种可能：要么包含在周游路线中，要么不被包含在周游路线中。因此，可以逐个考察每个路线是否被包含在最优解中。此时，将周游路线看作边的集合。127.3旅行售货商问题1.成本函数。显然，这个函数可以定义为路线的成本，即对于结点X：

2.估计函数。估计函数有多种定义方法：(1)定义为由根到X结点的部分周游路线的成本；(2)取图中具有最小成本的边，将该成本乘以城市数量n；(3)若X为根结点，对于每一个城市i（），求出城市i到最近的两个城市的成本之和，而后计算这个n个数字的和s，取；若X不是根结点，则X结点处已经确定了周游路线中包含的部分路径，此时，将这些路径包含进去，重新计算即可；(4)利用成本矩阵的矩阵约数。137.3旅行售货商问题147.4任务分配问题任务分配问题是指：有n个任务要分配给n个人完成，每项任务只能由一个人来执行，每个人也只能执行一项任务，其中第i项任务分配给第j个人的成本为，给出一种任务分配方案，使任务完成的总成本最小。157.4任务分配问题在利用分支限界方法进行求解该问题时，需要确定成本函数、估计函数和上界函数。(1)成本函数：记录为结点X的部分分配方案的成本。(2)估计函数：对于根结点，可以选择每行的最小值之和作为估计函数值；对于除根结点之外的内结点X，由于X处已经确定了部分任务的分配方案，因此估计函数值是已确定的部分分配方案的成本与未分配任务的估计函数值之和，只不过在计算估计函数值时，注意不要给当前已分配任务的人员重复分配任务；对于叶结点，即为对应的分配方案的成本。(3)上界函数：可以简单的设置为∞。167.4任务分配问题该问题的解空间树有两种画法。一是以任务为主，即将成本矩阵C按照行，逐个任务的分配，每次考虑第i项任务分配给哪个人去完成；二是以人为主，即将成本矩阵C按照列，逐个人安排，每次考虑第j个人应当完成哪一项任务。这两种方法是完全类似的，此处以第一种方法来进行求解。177.4任务分配问题187.5批处理作业调度问题不妨设X是解空间树中的一个结点，对应于一个已经调度的k个作业为那么，以X根的子树中的每一个叶结点Leaf对应的作业调度方案的完成时间之和为对于在J-JX中的作业，可以提供两种调度方案：方案S1：在该方案进行调度，使得机器M1没有空闲。方案S2：在该方案进行调度，使得机器M2没有空闲。据此，可求得估计函数值。197.5批处理作业调度问题207.6重排九宫问题假设在一个格的小盘中放有8个分别带有1~8编号的将牌，另有一个空格，允许的操作是每次只能把一个将牌移动到空格上。对于任意给定的一种初始状态（图