GOF的模板方法及其在回溯算法中应用研究

刘从军

摘 要:软件设计模式代表了从成功的系统设计中分离出来可复用的优秀设计经验,已成为现代软件系统设计的重要研究对象。在此介绍采用GOF的模板方法模式及采用回溯算法的模板方法模式的设计与实现。该实现使得回溯算法的实现达到了可扩展性、灵活性和可插入性三个目标,提高了算法的可维护性和可复用性。最后,演示如何使用该设计来解决N皇后问题、排列问题和子集和问题。

关键词:GOF设计模式;模板方法模式;设计模式;回溯算法

中图分类号:TP311文献标识码:A

文章编号:1004-373X(2009)20-123-03

Research on Template Method of GOF in Back Tracing Algorithm

LIU Congjun

(School of Computer Science and Engineering,Jiangsu University of Science and Technology,Zhenjiang,212003,China)

Abstract:Software design pattern represents excellent design experience that can be reused abstracted from successful system designs.It has become an important study subject in modem software design.Template method pattern of GOF and the realization of template method pattern in back tracing algorithm are introduced.The implementation makes the algorithm achieve the goal of extensibility,flexibility and pluggability,promote maintainability and reuseability of the algorithm.At last,it demonstrates how to apply to problem of N_Queen,permutation and sum of subset.

Keywords:GOF design model;template method pattern;design pattern;back tracing algorithm

0 引 言

设计模式的概念可以应用于生活的各个领域。例如:在都市规划和建筑学中,设计模式常用来描述城市设计和建筑设计中普遍问题的特征,以及一些为解决某些问题而准备的标准解决方案的模式。

设计模式的思想最初来源于建筑领域,建筑师Christopher Alexander首先提出了设计模式的概念。他认为,每一种模式描述一个经常出现的问题和这个问题的解决方案,这种解决方案可以反复使用,而无需每一次重新设计。尽管Alexander描述的是建筑和规划中的设计模式,但其中体现的思想也适用于建筑设计以外的一些领域,只是在这里,对象和接口代替了墙和门窗,但模式的核心都是一样的,即需要在某种环境下解决特定问题的通用方法。

设计模式的基本描述格式通常包括[1,2]:

(1) 名称:模式的名称;

(2) 问题:模式要解决的问题及模式所适用的环境;

(3) 解决方案:一个通用的解决方案,包括模式中的组件、组件间的交互以及它们的职责、关系和协作;

(4) 效果:使用这种解决方案会产生的效果;

(5) 相关模式:与这种模式相关的其他模式。

在20世纪90年代早期,设计模式对软件制造业产生了很深的影响。1994年,Gamma,Helm,Johson,Vlissides合著了一部可以被称为是设计模式领域中“圣经”的著作《设计模式:可重用的面向对象的软件元素》。这本书的成功为他们赢得了一个亲切的称号:GOF,在这本书中所描述的模式也常被称为GOF设计模式[3,4]。模板方法(Template Method)模式是GOF设计模式中最为常见的几个模式之一。

1 模板方法模式介绍

模板方法设计模式用于定义一个算法,一个算法的某些步骤和另一个算法的对应部分可能有很大的变化。负责逐步实现算法的方法称为模板方法。由于计算步骤的变化,这些变化的步骤常是以其他子类实现的,就是说模板方法会调用一个或多个抽象方法,这些抽象方法是由不同子类实现的。

现在流行的很多框架中(如Spring,Struts等)都可以看到模板方法模式的应用。模板方法模式主要应用于框架设计中,在日常的应用设计中也被经常使用。模板方法模式的静态结构如图1所示。

图1 模板方法模式的静态结构图

在模板方法模式中有两个参与者进行协作[4-6]。

抽象模板类角色有如下的责任:定义一个或多个抽象操作,由子类去实现。这些操作称为基本操作,它们是顶级逻辑的组成步骤。

定义并实现一个模板方法。这个模板方法一般是一个具体方法,它给出一个顶级逻辑的骨架,而逻辑的组成步骤在相应的抽象操作中,推迟到子类实现。具体类角色有如下责任:实现父类所定义的一个或多个抽象方法。

每一个抽象模板角色都可以有任意多个具体模板角色与之对应,而每一个具体模板角色都可以给出这些抽象方法的不同实现,从而使得顶级逻辑的实现各不相同[7]。

2 回溯算法的一般性描述

回溯算法问题的解可以表示成X=(x0,x1,…,x n-1)的形式,每个分量xi的取值范围为某个有穷集Si,Si={ai.0,ai.1,…,ai.mi}。因此,问题的解空间由笛卡尔积A=S0×S1×S2×…×Sn-1构成。这时,可以把状态空间看成是一棵高度为n的树,第0层有m0个分支结点,构成m0棵子树;第1层每一棵都有m1个分支结点,构成m0×m1棵子树;…;在第n-1层共有m0×m1×…×mn-1个结点,它们都是叶子结点。

回溯算法在初始化时,令解向量X为空。然后,从根结点出发。在第0层选择S0的第一个元素作为解向量的第一个元素,即置x0=a0.0,这是根结点的第一个儿子结点。如果X=(x0)是问题的部分解,则该结点是l_结点(活结点),因为它有下层的儿子结点,所以它也是e_结点(扩展结点)。于是,搜索以该结点为根的子树。首次搜索这棵子树时,选择S1的第一个元素作为解向量X的第二个元素,即置x1=a1.0,这是此树的第一个分支结点。如果X={x0,x1}是问题的部分解,则这个结点也是l_结点,并且也是e_结点,就继续选择S2的第一个元素作为解向量的第三个元素,即置x2=a2.0,但是如果X=(x0,x1)不是问题的部分解,则该结点是一个d_结点(死结点),于是舍弃以该d_结点作为根的子树的搜索,取S1的下一个元素作为解向量X的第二个元素,即置x1=a1.1,这是第一层子树的第二个分支结点。依次类推,在一般情况下,如果已经检测到X=(x0,x1,…,xi)是问题的部分解,在把xi+1=ai+1.0扩展到X时,有下面几种情况:

(1)如果X={x0,x1,…,xi+1}是问题的最终解,就是它作为问题的一个有效解存放起来。如果问题只希望有一个解,就结束搜索;否则继续搜索其他有效解。

(2)如果X={x0,x1,…,xi+1}是问题的部分解,就令xi+2 = ai+2•0,搜索它的下层子树,继续扩展解向量X;

(3)如果X={x0,x1,…,xi+1}既不是问题的最终解,也不是问题的部分解,则有下面两种情况:

如果xi+1 = a(i+1)•k不是Si+1的最后一个元素,就令xi+1 = a(i+1)•(k+1),继续搜索它的兄弟子树;

如果xi+1= a(i+1)•k是Si+1的最后一个元素,就回溯到X={x0,x1,…,xi}的情况。如果此时的xi=ai,k不是Si的最后一个元素,就令xi=ai•(k+1),搜索上一层的兄弟子树;就继续回溯到X={x0,x1,…,xi-1}的情况[8]。

3 回溯算法的模板方法模式设计实现

根据模板方法模式,回溯算法设计如图2所示。

图2 回溯算法的类图

将回溯算法的顶层逻辑封装在BackTracingAlgorithm类中。在该类中属性m为数组,m[i]表示集合Si的势(1≤i≤n);属性X是n元解向量;它们的访问属性均为保护类型,以方便子类的访问。

方法backTracing为回溯算法的顶层逻辑,即模板方法;回溯算法逻辑应用于各类问题,其本身无需改变,所以该方法定义为final方法,以防止子类的覆盖重载。对于易于变化的,涉及具体问题的部分,定义在基本方法中,基本方法可以推迟到子类实现。模板方法可以调用具体子类的基本方法完成顶层逻辑,该功能通过面向对象程序设计语言的多态性完成。

抽象方法constrain(i:int):boolean为约束条件判断,判断当前步骤是否可行,满足约束条件返回真,否则返回假;抽象方法isSolution(i:int):boolean判断当前X是否已达到问题的解;钩子方法isFinal,判别是否可以提前结束算法,默认定义返回假。这些方法为基本方法,与具体问题领域相关,所以由BackTracingAlgorithm类的子类实现或覆盖。

该设计满足了“开-闭原则”(OCP)。BackTracingAlgorithm为抽象类,在抽象类中预见了所有可能的扩展,在任何情况下都不需要改变,从而满足了对修改的关闭。它对扩展是开放的,如果需要用回溯算法解决新的问题,只需设计一个新类继承BackTracingAlgorithm类,实现抽象方法constrain和isSolution,即可利用BackTracingAlgorithm类中的回溯算法模板解决。满足了在对原有类不需修改的基础上,扩展了系统。

4 应用实例

下面以N皇后问题、排列问题和子集和问题说明模板方法模式设计的回溯算法应用。BackTracingAlgorithm类封装的回溯算法不需修改,即可应用于解决具体问题。分别设计N-Queen类、N-Permunation类和SumSubset类用回溯法解决N皇后问题,排列问题和子集和问题。这些类继承自BackTracingAlgorithm类,如图2所示。

例1(N皇后问题) 在N×N的棋盘上放置N个皇后,要求每行、每列和每个对角线至多放置一个皇后[9]。

设计N-Qeen类继承自BackTracingAlgorithm类,实现抽象方法constrain和isSolution。此时,constrain(i:int):boolean判断当前行i与1~(i-1)行的皇后是否有冲突;isSolution(i:int):boolean判断i值是否为N,若i=N,则表示成功放至了第N个皇后,获得了一个合法解,返回真,否则返回假。程序如下:

public boolean constrain(int i){

for(int j=0;j

if((x[j]==x[i])||(Math.abs(x[j]-x[i]) == Math.abs(i-j)))

return false; }

return true;}

public boolean isSolution(int i){

if(i==n-1)return true;

else return false;}

例2(排列问题) 设A是一个集合,求A的全排列。

N-Permutation类实现了抽象方法constrain和isSolution。其中,constrain判断当前第i个数是否与前i-1个数有相同值, 有则返回假, 表示不能满足排列的要求,否则返回真;isSolution判断i是否等于N。若i=N,则表示生成了一个合法排列,返回真,否则返回假(程序略)。

例3(子集和问题) 设A是N个正整数组成的集合及正整数sum,求A的子集,使它的元素和为sum。

SumSubset类实现了抽象方法constrain和isSolution。其中,constrain判断前i个数的选择是否可行,即在后续的选择中,所选整数和是否能达到sum,能则返回真,否则返回假;isSolution判断对集合A中的前i个整数的选择,其和是否为sum,若已是sum,则返回真,表示找到了一个解,否则返回假。属性data:int[N]表示N个数的集合,M表示sum(程序略)。

5 结 语

设计模式把面向对象的封装、继承和多态性等特征发挥到了极至,对许多重复出现的问题,提出了既优雅又实际的解决方案[10]。回溯算法在计算机科学与技术中有着广泛的应用。在此应用模板方法设计模式设计回溯算法,使得回溯算法与具体应用问题相分离,成为一个可复用的算法。该设计避免了系统过于僵硬,过于脆弱,复用率低,黏度过高等软件设计的主要问题,达到了可扩展性、灵活性、可插入性的目标。设计的回溯算法具有较好的可维护性、可复用性及可靠性。

参考文献

[1]James W Cooper.设计模式[M].北京:清华大学出版社,2004.

[2]计春雷.软件设计模式及其应用研究[J].上海电机学院学报,2006(5):46-49.

[3]胡文华,李建民,胡振鹏.模式与设计模式[J].计算机与现代化,2002(12):12-15.

[4]计春雷.基于MVC模型的信息管理系统设计[J].上海电机学院学报,2008(5) :589-592.

[5]刘繁艳.基于Java的模板设计模式研究[J] .电脑知识与技术,2008(19):60-62.

[6]任勇军,王志坚.模板方法模式及其在Java 2D中的应用[J].计算机与现代化,2003(9):13-15.

[7]阎闳.Java与模式[M].北京:电子工业出版社,2002.

[8]郑宗汉,郑晓明.算法设计与分析[M].北京:清华大学出版社,2005.

[9]王岩冰,郑明春,刘弘.回溯算法的形式模型[J].计算机研究与发展,2001,38(9):1 066-1 079.

[10]龚立,许炎义.面向模式分析与设计方法应用研究[J].微计算机信息,2006,22(15):264-266.