资源描述：
《分枝定界算法设计模式研究与应用_陈艳琼.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、计算机与现代化2008年第12期JISUANJIYUXIANDAIHUA总第160期文章编号:1006-2475(2008)12-0015-04分枝定界算法设计模式研究与应用陈艳琼,杨庆红,于程远(江西师范大学计算机信息工程学院,江西南昌330022)摘要:分枝定界算法是传统算法设计方法中重要算法之一,很多重要问题可以用它来解决。本文在对分枝定界算法进行深入研究的基础上,将其抽象成分枝定界算法设计模式,并使用Cgg的模板机制加以实现。最后通过具体实例说明本文开发的分枝定界算法模板具有较高的可重用性、可编程性和可靠性。关键词:
2、分枝定界算法;算法设计模式;泛型编程中图分类号:TP301.6文献标识码:AStudyonBranch-and-BoundAlgorithmPatternCHENYan-qiong,YANGQing-hong,YUCheng-yuan(ComputerInformationandEngineeringCollege,JiangxiNormalUniversity,Nanchang330022,China)Abstract:Branch-and-boundalgorithmisaimportanttraditionalalgo
3、rithm,manyimportantissuescanbesolvedbyit.Thispaperstudiesonbranch-and-boundalgorithm,andimplementsbranch-and-boundalgorithmpatternbyCggtemplate.Throughexamplesexplanationbranch-and-boundalgorithmtemplatehashighreusability,programmabilityandreliability.Keywords:bran
4、ch-and-boundalgorithm;designpatterns;genericprogramming决。所以本文在对分枝定界算法进行深入研究的基0引言础上,对分枝定界算法进行抽象,描述为分枝定界算传统的算法设计方法在遇到一个具体问题时先法设计模式,并用Cgg的模板机制加以实现,形成分对该问题进行分析,从而确定可以用来解决该问题的枝定界算法模板。这样人们在使用分枝定界算法解算法,然后根据选定的算法和具体问题的特点编写出决具体问题时就可以继承分枝定界算法模板,将新的解决该问题的程序。这样的程序是根据算法的特点设计建立在
5、以往工作的基础上,大大地减轻了程序员和具体问题的特点所编写出来的,抽象层次低,程序的编程负担,提高了程序的可重用性和可靠性。开发的效率和可靠性都比较低。设计模式通常是对于某一类软件设计问题的可1分枝定界算法模式的设计与实现重用的解决方案。优秀的软件设计师都非常清楚,不1.1分枝定界算法的基本思想是所有的问题都需要从头开始解决,他们更愿意复用分枝定界算法是一种系统地搜索解空间的方法,以前曾经使用过的解决方案,每当他们找到一个好的解决方案,就会一遍又一遍地使用。他们帮助设计者它与回溯法的主要区别在于对E-结点(E-结点:称为将新
6、的设计建立在以往工作的基础上,重用以往成功扩展结点,是正在把自己的子结点加入到活动结点表的设计方案。中的活动结点)的扩充方式。每个活结点有且仅有由于分枝定界算法是传统算法设计方法中重要一次机会变成E-结点。当一个结点变为E-结点时,算法之一,很多重要问题可以用分枝定界算法来解生成从该结点移动一步即可到达的所有新结点。在收稿日期:2007-11-09作者简介:陈艳琼(1982-),女,江西高安人,江西师范大学计算机信息工程学院硕士研究生,研究方向:智能教育;杨庆红(1968-),女,副教授,研究方向:智能教育;于程远(1982
7、-),男,硕士,研究方向:并行编程环境。16计算机与现代化2008年第12期生成的结点中,抛弃那些不可能导出(最优)可行解问题无关的操作以public形式定义并且实现。的结点,其余结点加入活结点表,然后从表中选择一1.3分枝定界算法设计模式的实现个结点作为下一个E-结点。从活结点表中取出所选我们定义了分枝定界算法模板fzdjfa,状态的数择的结点并进行扩充,直到找到解或活动表为空,扩据类型作为模板参数,并根据分枝定界算法的思想把充过程才结束。分枝定界算法中与问题无关部分在fzdj()中实现,在1.2分枝定界算法模板的设计fz
8、dj()中先调用initial()对问题进行初始化即确定问在对分枝定界算法进行深入研究的基础上,本文题的第一个状态,在fzdj()函数中维护一个活动结点对分枝定界算法的结构与行为以一种与具体应用无队列,按先进先出(FIFO)方式从活动结点队列中选关的方式抽象出来构成一个分枝定界算法设计模式
