劉從軍

摘 要:軟件設(shè)計模式代表了從成功的系統(tǒng)設(shè)計中分離出來可復用的優(yōu)秀設(shè)計經(jīng)驗,已成為現(xiàn)代軟件系統(tǒng)設(shè)計的重要研究對象。在此介紹采用GOF的模板方法模式及采用回溯算法的模板方法模式的設(shè)計與實現(xiàn)。該實現(xiàn)使得回溯算法的實現(xiàn)達到了可擴展性、靈活性和可插入性三個目標,提高了算法的可維護性和可復用性。最后,演示如何使用該設(shè)計來解決N皇后問題、排列問題和子集和問題。

關(guān)鍵詞:GOF設(shè)計模式;模板方法模式;設(shè)計模式;回溯算法

中圖分類號: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 引 言

設(shè)計模式的概念可以應(yīng)用于生活的各個領(lǐng)域。例如:在都市規(guī)劃和建筑學中,設(shè)計模式常用來描述城市設(shè)計和建筑設(shè)計中普遍問題的特征,以及一些為解決某些問題而準備的標準解決方案的模式。

設(shè)計模式的思想最初來源于建筑領(lǐng)域,建筑師Christopher Alexander首先提出了設(shè)計模式的概念。他認為,每一種模式描述一個經(jīng)常出現(xiàn)的問題和這個問題的解決方案,這種解決方案可以反復使用,而無需每一次重新設(shè)計。盡管Alexander描述的是建筑和規(guī)劃中的設(shè)計模式,但其中體現(xiàn)的思想也適用于建筑設(shè)計以外的一些領(lǐng)域,只是在這里,對象和接口代替了墻和門窗,但模式的核心都是一樣的,即需要在某種環(huán)境下解決特定問題的通用方法。

設(shè)計模式的基本描述格式通常包括[1,2]:

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

(2) 問題:模式要解決的問題及模式所適用的環(huán)境;

(3) 解決方案:一個通用的解決方案,包括模式中的組件、組件間的交互以及它們的職責、關(guān)系和協(xié)作;

(4) 效果:使用這種解決方案會產(chǎn)生的效果;

(5) 相關(guān)模式:與這種模式相關(guān)的其他模式。

在20世紀90年代早期,設(shè)計模式對軟件制造業(yè)產(chǎn)生了很深的影響。1994年,Gamma,Helm,Johson,Vlissides合著了一部可以被稱為是設(shè)計模式領(lǐng)域中“圣經(jīng)”的著作《設(shè)計模式:可重用的面向?qū)ο蟮能浖亍?。這本書的成功為他們贏得了一個親切的稱號:GOF,在這本書中所描述的模式也常被稱為GOF設(shè)計模式[3,4]。模板方法(Template Method)模式是GOF設(shè)計模式中最為常見的幾個模式之一。

1 模板方法模式介紹

模板方法設(shè)計模式用于定義一個算法,一個算法的某些步驟和另一個算法的對應(yīng)部分可能有很大的變化。負責逐步實現(xiàn)算法的方法稱為模板方法。由于計算步驟的變化,這些變化的步驟常是以其他子類實現(xiàn)的,就是說模板方法會調(diào)用一個或多個抽象方法,這些抽象方法是由不同子類實現(xiàn)的。

現(xiàn)在流行的很多框架中(如Spring,Struts等)都可以看到模板方法模式的應(yīng)用。模板方法模式主要應(yīng)用于框架設(shè)計中,在日常的應(yīng)用設(shè)計中也被經(jīng)常使用。模板方法模式的靜態(tài)結(jié)構(gòu)如圖1所示。

圖1 模板方法模式的靜態(tài)結(jié)構(gòu)圖

在模板方法模式中有兩個參與者進行協(xié)作[4-6]。

抽象模板類角色有如下的責任:定義一個或多個抽象操作,由子類去實現(xiàn)。這些操作稱為基本操作,它們是頂級邏輯的組成步驟。

定義并實現(xiàn)一個模板方法。這個模板方法一般是一個具體方法,它給出一個頂級邏輯的骨架,而邏輯的組成步驟在相應(yīng)的抽象操作中,推遲到子類實現(xiàn)。具體類角色有如下責任:實現(xiàn)父類所定義的一個或多個抽象方法。

每一個抽象模板角色都可以有任意多個具體模板角色與之對應(yīng),而每一個具體模板角色都可以給出這些抽象方法的不同實現(xiàn),從而使得頂級邏輯的實現(xiàn)各不相同[7]。

2 回溯算法的一般性描述

回溯算法問題的解可以表示成X=(x0,x1,…,x n-1)的形式,每個分量xi的取值范圍為某個有窮集Si,Si={ai.0,ai.1,…,ai.mi}。因此,問題的解空間由笛卡爾積A=S0×S1×S2×…×Sn-1構(gòu)成。這時,可以把狀態(tài)空間看成是一棵高度為n的樹,第0層有m0個分支結(jié)點,構(gòu)成m0棵子樹;第1層每一棵都有m1個分支結(jié)點,構(gòu)成m0×m1棵子樹;…;在第n-1層共有m0×m1×…×mn-1個結(jié)點,它們都是葉子結(jié)點。

回溯算法在初始化時,令解向量X為空。然后,從根結(jié)點出發(fā)。在第0層選擇S0的第一個元素作為解向量的第一個元素,即置x0=a0.0,這是根結(jié)點的第一個兒子結(jié)點。如果X=(x0)是問題的部分解,則該結(jié)點是l_結(jié)點(活結(jié)點),因為它有下層的兒子結(jié)點,所以它也是e_結(jié)點(擴展結(jié)點)。于是,搜索以該結(jié)點為根的子樹。首次搜索這棵子樹時,選擇S1的第一個元素作為解向量X的第二個元素,即置x1=a1.0,這是此樹的第一個分支結(jié)點。如果X={x0,x1}是問題的部分解,則這個結(jié)點也是l_結(jié)點,并且也是e_結(jié)點,就繼續(xù)選擇S2的第一個元素作為解向量的第三個元素,即置x2=a2.0,但是如果X=(x0,x1)不是問題的部分解,則該結(jié)點是一個d_結(jié)點(死結(jié)點),于是舍棄以該d_結(jié)點作為根的子樹的搜索,取S1的下一個元素作為解向量X的第二個元素,即置x1=a1.1,這是第一層子樹的第二個分支結(jié)點。依次類推,在一般情況下,如果已經(jīng)檢測到X=(x0,x1,…,xi)是問題的部分解,在把xi+1=ai+1.0擴展到X時,有下面幾種情況:

(1)如果X={x0,x1,…,xi+1}是問題的最終解,就是它作為問題的一個有效解存放起來。如果問題只希望有一個解,就結(jié)束搜索;否則繼續(xù)搜索其他有效解。

(2)如果X={x0,x1,…,xi+1}是問題的部分解,就令xi+2 = ai+2?0,搜索它的下層子樹,繼續(xù)擴展解向量X;

(3)如果X={x0,x1,…,xi+1}既不是問題的最終解,也不是問題的部分解,則有下面兩種情況:

如果xi+1 = a(i+1)?k不是Si+1的最后一個元素,就令xi+1 = a(i+1)?(k+1),繼續(xù)搜索它的兄弟子樹;

如果xi+1= a(i+1)?k是Si+1的最后一個元素,就回溯到X={x0,x1,…,xi}的情況。如果此時的xi=ai,k不是Si的最后一個元素,就令xi=ai?(k+1),搜索上一層的兄弟子樹;就繼續(xù)回溯到X={x0,x1,…,xi-1}的情況[8]。

3 回溯算法的模板方法模式設(shè)計實現(xiàn)

根據(jù)模板方法模式,回溯算法設(shè)計如圖2所示。

圖2 回溯算法的類圖

將回溯算法的頂層邏輯封裝在BackTracingAlgorithm類中。在該類中屬性m為數(shù)組,m[i]表示集合Si的勢(1≤i≤n);屬性X是n元解向量;它們的訪問屬性均為保護類型,以方便子類的訪問。

方法backTracing為回溯算法的頂層邏輯,即模板方法;回溯算法邏輯應(yīng)用于各類問題,其本身無需改變,所以該方法定義為final方法,以防止子類的覆蓋重載。對于易于變化的,涉及具體問題的部分,定義在基本方法中,基本方法可以推遲到子類實現(xiàn)。模板方法可以調(diào)用具體子類的基本方法完成頂層邏輯,該功能通過面向?qū)ο蟪绦蛟O(shè)計語言的多態(tài)性完成。

抽象方法constrain(i:int):boolean為約束條件判斷,判斷當前步驟是否可行,滿足約束條件返回真,否則返回假;抽象方法isSolution(i:int):boolean判斷當前X是否已達到問題的解;鉤子方法isFinal,判別是否可以提前結(jié)束算法,默認定義返回假。這些方法為基本方法,與具體問題領(lǐng)域相關(guān),所以由BackTracingAlgorithm類的子類實現(xiàn)或覆蓋。

該設(shè)計滿足了“開-閉原則”(OCP)。BackTracingAlgorithm為抽象類,在抽象類中預見了所有可能的擴展,在任何情況下都不需要改變,從而滿足了對修改的關(guān)閉。它對擴展是開放的,如果需要用回溯算法解決新的問題,只需設(shè)計一個新類繼承BackTracingAlgorithm類,實現(xiàn)抽象方法constrain和isSolution,即可利用BackTracingAlgorithm類中的回溯算法模板解決。滿足了在對原有類不需修改的基礎(chǔ)上,擴展了系統(tǒng)。

4 應(yīng)用實例

下面以N皇后問題、排列問題和子集和問題說明模板方法模式設(shè)計的回溯算法應(yīng)用。BackTracingAlgorithm類封裝的回溯算法不需修改,即可應(yīng)用于解決具體問題。分別設(shè)計N-Queen類、N-Permunation類和SumSubset類用回溯法解決N皇后問題,排列問題和子集和問題。這些類繼承自BackTracingAlgorithm類,如圖2所示。

例1(N皇后問題) 在N×N的棋盤上放置N個皇后,要求每行、每列和每個對角線至多放置一個皇后[9]。

設(shè)計N-Qeen類繼承自BackTracingAlgorithm類,實現(xiàn)抽象方法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(排列問題) 設(shè)A是一個集合,求A的全排列。

N-Permutation類實現(xiàn)了抽象方法constrain和isSolution。其中,constrain判斷當前第i個數(shù)是否與前i-1個數(shù)有相同值, 有則返回假, 表示不能滿足排列的要求,否則返回真;isSolution判斷i是否等于N。若i=N,則表示生成了一個合法排列,返回真,否則返回假(程序略)。

例3(子集和問題) 設(shè)A是N個正整數(shù)組成的集合及正整數(shù)sum,求A的子集,使它的元素和為sum。

SumSubset類實現(xiàn)了抽象方法constrain和isSolution。其中,constrain判斷前i個數(shù)的選擇是否可行,即在后續(xù)的選擇中,所選整數(shù)和是否能達到sum,能則返回真,否則返回假;isSolution判斷對集合A中的前i個整數(shù)的選擇,其和是否為sum,若已是sum,則返回真,表示找到了一個解,否則返回假。屬性data:int[N]表示N個數(shù)的集合,M表示sum(程序略)。

5 結(jié) 語

設(shè)計模式把面向?qū)ο蟮姆庋b、繼承和多態(tài)性等特征發(fā)揮到了極至,對許多重復出現(xiàn)的問題,提出了既優(yōu)雅又實際的解決方案[10]?；厮菟惴ㄔ谟嬎銠C科學與技術(shù)中有著廣泛的應(yīng)用。在此應(yīng)用模板方法設(shè)計模式設(shè)計回溯算法,使得回溯算法與具體應(yīng)用問題相分離,成為一個可復用的算法。該設(shè)計避免了系統(tǒng)過于僵硬,過于脆弱,復用率低,黏度過高等軟件設(shè)計的主要問題,達到了可擴展性、靈活性、可插入性的目標。設(shè)計的回溯算法具有較好的可維護性、可復用性及可靠性。

參考文獻

[1]James W Cooper.設(shè)計模式[M].北京:清華大學出版社,2004.

[2]計春雷.軟件設(shè)計模式及其應(yīng)用研究[J].上海電機學院學報,2006(5):46-49.

[3]胡文華,李建民,胡振鵬.模式與設(shè)計模式[J].計算機與現(xiàn)代化,2002(12):12-15.

[4]計春雷.基于MVC模型的信息管理系統(tǒng)設(shè)計[J].上海電機學院學報,2008(5) :589-592.

[5]劉繁艷.基于Java的模板設(shè)計模式研究[J] .電腦知識與技術(shù),2008(19):60-62.

[6]任勇軍,王志堅.模板方法模式及其在Java 2D中的應(yīng)用[J].計算機與現(xiàn)代化,2003(9):13-15.

[7]閻閎.Java與模式[M].北京:電子工業(yè)出版社,2002.

[8]鄭宗漢,鄭曉明.算法設(shè)計與分析[M].北京:清華大學出版社,2005.

[9]王巖冰,鄭明春,劉弘.回溯算法的形式模型[J].計算機研究與發(fā)展,2001,38(9):1 066-1 079.

[10]龔立,許炎義.面向模式分析與設(shè)計方法應(yīng)用研究[J].微計算機信息,2006,22(15):264-266.