分枝定界算法应用小结

《分枝定界算法应用小结》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分枝定界算法应用小结摘要本文首先总结了分枝定界算法的总体内容。然后，我们列举了6个分枝定界算法应用的实例，它们分别：（1）基于分枝限界法的公交换乘算法设计；（2）分枝定界算法用于有机混合物的分析；（3）求解最大割问题的分枝定界算法；（4）弱有效集上凹函数极大问题的分枝定界算法；（5）分枝定界算法在食品分析中的应用—水果中有机酸的同时定性定量分析；（6）基于分枝定界法的环肋圆柱壳优化研究。我们得知，分枝定界算法是一种常用算法，属于枚举算法，能够系统地搜索解空间，分枝定界算法的应用非常广泛。一、分枝定界算法总述分枝定界算法也可以叫做分支限定法。分枝定界

2、法是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。总的来说，“分支限定法求解问题的过程与图的广度优先方法类似。它是把问题的各个结点的解看作是解空间树上的各个分支结点，求解过程是在解空间树中进行官广度优先搜索的过程。”[1]分枝定界算法的具体内容如下：“步骤一：如果问题的目标为最小化，则设定目前最优解的值Z=∞。步骤二：根据分枝法则（Branchingrule），从尚未被洞悉（Fathomed）节点（局部解）中选择一个节点，并在此节点的下一阶层中分为几个新的节点。步骤三：计算每一个新分枝出来的节点的下限值（Lower

3、bound，LB）。步骤四：对每一节点进行洞悉条件测试，若节点满足以下任意一个条件，则此节点可洞悉而不再被考虑：此节点的下限值大于等于Z值。已找到在此节点中，具最小下限值的可行解；若此条件成立，则需比较此可行解与Z值，若前者较小，则需更新Z值，以此为可行解的值。此节点不可能包含可行解。步骤五：判断是否仍有尚未被洞悉的节点，如果有，则进行步骤二，如果已无尚未被洞悉的节点，则演算停止，并得到最优解。”[2]二、分枝定界算法的有关应用分枝定界算法是一种常用算法，属于枚举算法，能够系统地搜索解空间，分枝定界算法的应用非常广泛。以下列举几个具体应用实例。1、

4、基于分枝限界法的公交换乘算法设计[3]（1）问题陈述伴随着经济的高速发展，公共交通问题成为解决城市拥挤，环境污染等问题的重要手段。由于受计算机硬件及软件资源的制约，我们在对城市，特别是大型城市庞大的公交网络进行公交换乘问题求解时，不可能对每一种可能解进行计算。那该如何更好地解决该问题呢？（2）该问题算法设计思想在本文所解决的公交换乘问题中，我们的设计是根据具体城市的具体情况，我们对城市地图进行逐层分块，直至求出所求解。从起点站开始，我们总是试图转乘最少次数的车到终点站，因此，当我们坐上一辆公交车后，我们要尽可能走更远的距离。只有当这趟车不满足我们乘

5、车方向的要求时，我们才会考虑转车。所以我们在每一个起始点站总是试图找到能够到达离目的地最近的一趟车。在每一个车站总会有好几趟车经过，我们怎样才能知道坐哪趟车才会是最佳方案呢？从这站开始，每走一站，我们便作一次条件判断，保留满足某一条件的车次，对不满足这一条件的车次修枝（删除）。按此方案，不断往前走，只要有车次能够继续往目的地方向前进，我们就决不换车。只有当目前所有的车都不满这一条件时，我们再按上面的方案，把此站作为起始站换乘车辆继续前进，直至终点站。根据以上思想设计的算法是一种行之有效的公交换乘解决方案。2、分枝定界算法用于有机混合物的分析[4]在

6、分析工作中常常会遇到一种分析体系，即定性组成不完全确知的混合体系称为“灰色”分析体系。最常见的情形为已知混合物体系中可能存在的组分（物种）范围，但种类和数目未知。对于这类灰色分析体系，一般需先用某方法进行定性分析，再进行定量测定。采用分枝定界算法，实现未知混合试样体系的同时定性定量分析。此方法克服了逐步回归法只能找出局部最优解的不足，仅用较少的计算就可以找出全局最优解。在最优回归子集的选择中，选用4个判据，解决了最优回归子集难判断的问题，使最优回归子集的选择更加准确，真实，可靠。采用分枝定界算法，实现最优回归子集的选择。3、求解最大割问题的分枝定界

7、算法[5]最大割问题是图论中的一个典型的NP困难问题，它在工程问题中有着广泛的应用。该应用基于最大割问题的半定规划松弛模型，给出了最大割问题的一种二次规划松弛模型，并且理论证明了文中提出的二次规划松弛模型要优于半定规划松弛模型.在该模型的基础上，利用分枝定界算法求解最大割问题。对小规模和中等规模的最大割问题分别作数值实验。实验表明分枝定界算法能够给出最大割问题一个好的近似解。4、弱有效集上凹函数极大问题的分枝定界算法[6]弱有效集上的优化问题主要思想是寻找一个使决策者最满意的弱有效解，为了达到这个目的，决策者选择一些实值目标函数，搜索一个弱有效解以

8、便优化其目标函数。该应用考虑了一凹函数在弱有效集上的极大问题。此优化问题主要有两方面的困难。第一，弱有效解集一般说来不再是