GOF的模板方法及其在回溯算法中应用研究
2010-05-13刘从军
刘从军
摘 要:软件设计模式代表了从成功的系统设计中分离出来可复用的优秀设计经验,已成为现代软件系统设计的重要研究对象。在此介绍采用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) 解决方案:一个通用的解决方案,包括模式中的组件、组件间的交互以及它们的职责、关系和协作;……p>
