最优化问题算法重用研究

崔　莉

(惠州工程技术学校 工学系，广东 惠州 516001)



最优化问题算法重用研究

崔莉

(惠州工程技术学校 工学系，广东 惠州 516001)

摘要为提高算法设计的效率以及缩小设计所需的时间，提出了算法重用的思想，即通过解决同一类型问题的算法框架来生成具体算法。并以N皇后问题的回溯算法为实例，介绍了算法设计过程。通过算法重用，文中可在解决这类问题的算法框架下，根据自身选择的实现函数，在框架下填充算法的具体细节，从而避免了算法设计的重复性工作，节省了设计所需的时间，提高了设计效率。

关键词最优化问题；算法框架；算法重用；算法设计

在用程序解决现实中的问题时，对于每一种不同的具体问题，均必须用针对于具体问题实现形式的算法来开发程序。但由于每个具体问题均存在相异性，其对应的程序算法之间也存在一些具体细节的差异，难以实现算法程序的重用，故对于每个具体问题，都要设计新的算法，这导致了工作的重复性，浪费时间与精力，同时每种具体算法之间没有一个相同的框架，程序可读懂性较差，而程序的编写仅凭编程人员自身的编程习惯，不利于后期人员的维护与修改，增大算法设计的难度。若能将同一类型不同问题的程序实现算法之间的相同点，固定封装在一个相同的框架上，便能在一定程度上实现算法的重用。

算法重用就是将解决同一类型问题的方法步骤通过编程语言形成一个固定的框架，当需要解决同一类型的不同问题时，不用重新设计算法，而是直接使用这一算法框架，然后再根据具体问题填充其算法的细节，从而达到算法重用的效果[1-6]。对于算法重用而言，最关键的是可重用的算法框架，本文以最优化问题为代表，提出由算法框架生成具体算法程序的方法，并以N皇后问题的回溯算法为例，给出从算法框架到具体算法设计的过程，并用C++语言实现了程序的编写。

1最优化问题

1.1最优化问题定义

所谓最优化问题，是将实际中需要解决的问题转化为一个求解某个目标函数的最值，目标函数代表的可以是产品收益，生产成本，效率等人们关心的性能指标或参数，这个目标函数的变量满足一定的约束条件，在这一约束条件下，文中进行目标函数的最值求解。

最优化类问题的典型形式为

minσ=f(X)或maxσ=f(X)

s.t.X∈S={X|gi(X)≤t或|gi(X)≥t,i=1,…,m}

其中，σ=f(X)为所要求解的目标函数;X为目标函数的n维变量，当其使目标函数达到最优值时即为所想要求解的目标解，(gi(X)≤t或|gi(X)≥t)为变量满足的约束条件。

1.2最优化问题的结构描述

一个最优化问题的结构可用四元组P=

下面给出原子集合A上的联接定义(ci∈A,i=1,2,…,n):(1)ci和(ci)是一种联接；(2)序列cj,cj+1,…,ck形成联接,其中(1≤j

2最优化问题的算法框架

2.1算法框架的定义

正如本文前面所提到的解决同一类型不同问题的程序实现算法之间，虽在具体细节上有诸多不同，但整体实现步骤相同，这些相同的实现步骤便组成一个抽象的算法框架。对于同一类型的某一具体问题，具体程序实现算法设计可在算法框架的基础上设计算法的具体细节，形成一个完整的具体算法，进而将算法转化为实现程序，并最终达到解决问题的目的。

通过总结各类求解最优化问题的方法与研究，文中基于算法框架的定义设计出一个求解最优化问题的抽象算法框架，其是最优化问题程序实现算法设计的基础。

2.2基本操作步骤

在得出最优化问题的算法框架时，首先定义3种基本操作。设X是一个集合，以X的所有子集为元素的集合称为X的子元素集，记作SE。V代表所需解决问题的变量集。

步骤1分解步骤(Decompose Operation)DO(V)，DO(V)表示将问题细化为N个子问题P1,P2,…,Pn⊆P(V)，然后求各个子问题的最优解。同时其还可继续分解成更小的子问题，分解后的子问题为规模递增或规模同等的；

步骤2求优步骤(Seeking Optimal-solution Operation)SOO(PN)，即求解第N个子问题PN的最优化解；

步骤3归并步骤(Combine Operation)CO(PN)，CO(PN)将各个子问题的最优解所对应的目标函数值归并为一个集合CO(P)；

步骤4比较步骤(Compare Operation)CoO(CO(P))，比较集合CO(P)得到目标函数值的全局最优解。

2.3最优化问题算法框架

最优化问题算法框架是将求解最优化问题的抽象实现步骤封装为一个固定的算法框架，其将求解最优化问题类型程序实现算法的相同性归结在一个框架中，因此在解决最优化问题时，只需根据具体问题以及选取的实现方法对框架进行算法细节的设计。对于最优化问题，现已存在的求解最优化问题的算法有动态规划法、贪心法、回溯法和分枝定界法等，其均可在最优化算法框架的基础上细化为具体的算法，这也证明了算法框架的实用性[7]。

在上述4类步骤的基础上，最优化问题算法框架如下：

/*最优化问题算法框架*/

Begin

Initialize

DO(V);

For i=1 to ndo

begin

SOO(PN);

end;

CO(PN);

S= CoO(CO(P));

return(S);

END

3最优化问题算法实现实例

3.1回溯算法

在将最优化算法框架转化为具体程序时，可采用不同的解决方法，即给出操作的不同实现函数，根据不同的解决方法，可得到动态规划算法、回溯算法、贪心算法、分支定界算法等。本文以回溯算法为例。

回溯算法也可称之为试探法，其是一种系统地搜索问题的解的方法，其基本思想是：从所要解决问题的某一种可能点作为出发点，搜索从这一点出发所能达到的所有可能点，当从出发点到某一种可能点时若不能到达目标，再返回上一个出发点，从另一个可能点出发继续搜索，直至到达正确的目标。一般回溯法是一种枚举状态空间中所有可能状态的系统方法[8-10]。

假设问题的解的形式为(x1，x2，…，xn)，x1∈S1，x2∈S2，…，xn∈Sn，若已有满足约束条件的部分解，不妨设为(x1，x2，…，xi)(i

procedure try(i);/*搜索第i个分量xi*/

begin

if i=n+1 then print /*得到一种解*/

forxi∈Si且使得(x1，x2，…，xi-1，xi)满足约束条件do

begin

记录满足条件的xi;

添加相应的标志；

try(i+1) /*删除标志；恢复之前的状态，根据具体情况选择*/

end

end

3.2N皇后的回溯算法

在N×N的国际象棋盘上，放置N个皇后，使任何一个皇后均不能吃掉另一个，其需满足的条件为同一行，同一列，同一对角线上只能有一个皇后，求放置方法。如N=4时，有如图1所示的两种放置方法。

图1　4皇后放置图

问题解的形式：{x:array[i…n]of integer;{x[i]:第i个皇后放在第j行，第x[i]列，保证所有皇后不同行}，问题的解变成求(x[1],x[2],…,x[n])；x[n]∈{1，2，3，4}4皇后的解为(2,4,1,3)，(3,1,4,2)。

放置第k(1≤k≤n)个皇后的递归算法：

procedure try(k);//搜索第k个皇后所在的列x[k]，前k-1个已放好，即已求得x[1]…x[k-1].

var i:integer;

begin

if k=n+1 then print(输出放置方案：数组x)；

fori=1 to n do /搜索第k个皇后所在的列j.

if 第k个皇后能够放置在第i列 then

begin

放置第k个皇后在第j列(x[k]=i)；

try(k+1);

end;

end

3.3回溯算法实现程序

下面给出使用C++语言来实现回溯算法的程序：

int main()

{

try(1);

System(“pause”);}

}

int try(int i)

{

int j;

for(j=1;j<=N;j + +)//每个皇后都有N位置(列)可试放

if((!b[j])&&(!c[i+j])&&(!d[i-j+N-1]))//寻找放置皇后的位置

//由于C++不能操作负数组，因此考虑加N-1

{//放置皇后，建立相应标志值

a[i]=j;//摆放皇后

b[j]=1;//宣布占领第j列

c[i+j]=1;//占领两个对角线

d[i-j+N-1]=1;

if(i= = N) print();//N个皇后都放置好，输出

else try(i+1);//继续递归放置下一个皇后

b[j]=0;//递归返回即为回溯一步，当前皇后退出

c[i+j]=0;

d[i-j+N-1]=0;

}

}

由于算法框架给算法重用提供了一种可能性，同时由于具有统一的框架，使得算法设计变得更加高效。

4结束语

本文以算法重用为思想，以N皇后问题的回溯算法为实例，阐述了从算法框架到具体算法的算法设计方法。通过算法重用，在解决同类型下不同问题时无需重新设计完整的算法，而是在解决这类问题的算法框架下，根据自身选择的实现函数，在框架下填充算法的具体细节，从而避免了算法设计的重复性工作，节省了算法设计所需的时间与精力。同时，由于具有统一框架，程序的后期维护也得到了良好的保障。

参考文献

[1]Helman P. An algebra for search problem and their solutions[C].Berlin: Search in Artificial Intelligence,Springer Verlag,1988.

[2]Lu Jian.Framework of algorithm correctness in NDNDAS[J].Science in China(Series A),1991:34(7):875-884.

[3]Tello E R.Object-oriented programming for artificial intelligence[M].Berlin:Springer Verlag,1989.

[4]栾尚敏,马绍汉.一类问题的描述方法及其算法[J].计算机学报,1995,18(10):775-762.

[5]栾尚敏,马绍汉.搜索问题的代数描述及其算法[J].计算机研究与发展,1997,34(11):801-806.

[6]栾尚敏,李未,马绍汉.算法框架:算法重定位的一种可操作的方法[J].软件学报,1999,10(7):679-684.

[7]李云清.基于算法框架的可重用部件设计与实现[J]计算机工程与应用,2001,37(23):136-138.

[8]原永福.算法设计与分析[M].北京:机械工业出版社,1998.

[9]卢开澄.计算机算法导引:设计与分析[M].2版.北京:清华大学出版社,2006.

[10] Erich Gamma,Richard Helm.设计模式:可复用面向对象软件的基础[M].李英军,马晓星,蔡敏,等,译.北京:机械工业出版社,2000.

[11] 李传湘,陈世鸿,刘海青.程序设计方法学[M].武汉:武汉大学出版社,2000.

Research on Algorithm Mode of Optimization Problems

CUI Li

(Department of Engineering, Huizhou Engineering Technical School, Huizhou 516001, China)

AbstractThe algorithm reuse idea is proposed to improve the efficiency and reduce design time of algorithm design. The example of algorithm for the N queen problem is taken to describe the algorithm design process, which is developed from algorithm framework to specific algorithm. By algorithm reuse, one can fill the specific details of the algorithm under the algorithm framework, implement functions according to our choice in order to avoid the repetitive tasks of algorithm design, and save the time and effort required for algorithm design, thus improving the efficiency of algorithm design.

Keywordsoptimization problems; algorithm framework; algorithm reuse; algorithm design

收稿日期:2015- 12- 4

作者简介:崔莉(1977-)，女，硕士，讲师。研究方向：计算机信息技术。

doi:10.16180/j.cnki.issn1007-7820.2016.07.008

中图分类号TP306.1

文献标识码A

文章编号1007-7820(2016)07-026-04