最優(yōu)化問題算法重用研究

崔　莉

(惠州工程技術(shù)學(xué)校 工學(xué)系，廣東 惠州 516001)

?

最優(yōu)化問題算法重用研究

崔莉

(惠州工程技術(shù)學(xué)校 工學(xué)系，廣東 惠州 516001)

摘要為提高算法設(shè)計(jì)的效率以及縮小設(shè)計(jì)所需的時(shí)間，提出了算法重用的思想，即通過解決同一類型問題的算法框架來生成具體算法。并以N皇后問題的回溯算法為實(shí)例，介紹了算法設(shè)計(jì)過程。通過算法重用，文中可在解決這類問題的算法框架下，根據(jù)自身選擇的實(shí)現(xiàn)函數(shù)，在框架下填充算法的具體細(xì)節(jié)，從而避免了算法設(shè)計(jì)的重復(fù)性工作，節(jié)省了設(shè)計(jì)所需的時(shí)間，提高了設(shè)計(jì)效率。

關(guān)鍵詞最優(yōu)化問題；算法框架；算法重用；算法設(shè)計(jì)

在用程序解決現(xiàn)實(shí)中的問題時(shí)，對(duì)于每一種不同的具體問題，均必須用針對(duì)于具體問題實(shí)現(xiàn)形式的算法來開發(fā)程序。但由于每個(gè)具體問題均存在相異性，其對(duì)應(yīng)的程序算法之間也存在一些具體細(xì)節(jié)的差異，難以實(shí)現(xiàn)算法程序的重用，故對(duì)于每個(gè)具體問題，都要設(shè)計(jì)新的算法，這導(dǎo)致了工作的重復(fù)性，浪費(fèi)時(shí)間與精力，同時(shí)每種具體算法之間沒有一個(gè)相同的框架，程序可讀懂性較差，而程序的編寫僅憑編程人員自身的編程習(xí)慣，不利于后期人員的維護(hù)與修改，增大算法設(shè)計(jì)的難度。若能將同一類型不同問題的程序?qū)崿F(xiàn)算法之間的相同點(diǎn)，固定封裝在一個(gè)相同的框架上，便能在一定程度上實(shí)現(xiàn)算法的重用。

算法重用就是將解決同一類型問題的方法步驟通過編程語(yǔ)言形成一個(gè)固定的框架，當(dāng)需要解決同一類型的不同問題時(shí)，不用重新設(shè)計(jì)算法，而是直接使用這一算法框架，然后再根據(jù)具體問題填充其算法的細(xì)節(jié)，從而達(dá)到算法重用的效果[1-6]。對(duì)于算法重用而言，最關(guān)鍵的是可重用的算法框架，本文以最優(yōu)化問題為代表，提出由算法框架生成具體算法程序的方法，并以N皇后問題的回溯算法為例，給出從算法框架到具體算法設(shè)計(jì)的過程，并用C++語(yǔ)言實(shí)現(xiàn)了程序的編寫。

1最優(yōu)化問題

1.1最優(yōu)化問題定義

所謂最優(yōu)化問題，是將實(shí)際中需要解決的問題轉(zhuǎn)化為一個(gè)求解某個(gè)目標(biāo)函數(shù)的最值，目標(biāo)函數(shù)代表的可以是產(chǎn)品收益，生產(chǎn)成本，效率等人們關(guān)心的性能指標(biāo)或參數(shù)，這個(gè)目標(biāo)函數(shù)的變量滿足一定的約束條件，在這一約束條件下，文中進(jìn)行目標(biāo)函數(shù)的最值求解。

最優(yōu)化類問題的典型形式為

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

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

其中，σ=f(X)為所要求解的目標(biāo)函數(shù);X為目標(biāo)函數(shù)的n維變量，當(dāng)其使目標(biāo)函數(shù)達(dá)到最優(yōu)值時(shí)即為所想要求解的目標(biāo)解，(gi(X)≤t或|gi(X)≥t)為變量滿足的約束條件。

1.2最優(yōu)化問題的結(jié)構(gòu)描述

一個(gè)最優(yōu)化問題的結(jié)構(gòu)可用四元組P=

下面給出原子集合A上的聯(lián)接定義(ci∈A,i=1,2,…,n):(1)ci和(ci)是一種聯(lián)接；(2)序列cj,cj+1,…,ck形成聯(lián)接,其中(1≤j

2最優(yōu)化問題的算法框架

2.1算法框架的定義

正如本文前面所提到的解決同一類型不同問題的程序?qū)崿F(xiàn)算法之間，雖在具體細(xì)節(jié)上有諸多不同，但整體實(shí)現(xiàn)步驟相同，這些相同的實(shí)現(xiàn)步驟便組成一個(gè)抽象的算法框架。對(duì)于同一類型的某一具體問題，具體程序?qū)崿F(xiàn)算法設(shè)計(jì)可在算法框架的基礎(chǔ)上設(shè)計(jì)算法的具體細(xì)節(jié)，形成一個(gè)完整的具體算法，進(jìn)而將算法轉(zhuǎn)化為實(shí)現(xiàn)程序，并最終達(dá)到解決問題的目的。

通過總結(jié)各類求解最優(yōu)化問題的方法與研究，文中基于算法框架的定義設(shè)計(jì)出一個(gè)求解最優(yōu)化問題的抽象算法框架，其是最優(yōu)化問題程序?qū)崿F(xiàn)算法設(shè)計(jì)的基礎(chǔ)。

2.2基本操作步驟

在得出最優(yōu)化問題的算法框架時(shí)，首先定義3種基本操作。設(shè)X是一個(gè)集合，以X的所有子集為元素的集合稱為X的子元素集，記作SE。V代表所需解決問題的變量集。

步驟1分解步驟(Decompose Operation)DO(V)，DO(V)表示將問題細(xì)化為N個(gè)子問題P1,P2,…,Pn?P(V)，然后求各個(gè)子問題的最優(yōu)解。同時(shí)其還可繼續(xù)分解成更小的子問題，分解后的子問題為規(guī)模遞增或規(guī)模同等的；

步驟2求優(yōu)步驟(Seeking Optimal-solution Operation)SOO(PN)，即求解第N個(gè)子問題PN的最優(yōu)化解；

步驟3歸并步驟(Combine Operation)CO(PN)，CO(PN)將各個(gè)子問題的最優(yōu)解所對(duì)應(yīng)的目標(biāo)函數(shù)值歸并為一個(gè)集合CO(P)；

步驟4比較步驟(Compare Operation)CoO(CO(P))，比較集合CO(P)得到目標(biāo)函數(shù)值的全局最優(yōu)解。

2.3最優(yōu)化問題算法框架

最優(yōu)化問題算法框架是將求解最優(yōu)化問題的抽象實(shí)現(xiàn)步驟封裝為一個(gè)固定的算法框架，其將求解最優(yōu)化問題類型程序?qū)崿F(xiàn)算法的相同性歸結(jié)在一個(gè)框架中，因此在解決最優(yōu)化問題時(shí)，只需根據(jù)具體問題以及選取的實(shí)現(xiàn)方法對(duì)框架進(jìn)行算法細(xì)節(jié)的設(shè)計(jì)。對(duì)于最優(yōu)化問題，現(xiàn)已存在的求解最優(yōu)化問題的算法有動(dòng)態(tài)規(guī)劃法、貪心法、回溯法和分枝定界法等，其均可在最優(yōu)化算法框架的基礎(chǔ)上細(xì)化為具體的算法，這也證明了算法框架的實(shí)用性[7]。

在上述4類步驟的基礎(chǔ)上，最優(yōu)化問題算法框架如下：

/*最優(yōu)化問題算法框架*/

Begin

Initialize

DO(V);

For i=1 to ndo

begin

SOO(PN);

end;

CO(PN);

S= CoO(CO(P));

return(S);

END

3最優(yōu)化問題算法實(shí)現(xiàn)實(shí)例

3.1回溯算法

在將最優(yōu)化算法框架轉(zhuǎn)化為具體程序時(shí)，可采用不同的解決方法，即給出操作的不同實(shí)現(xiàn)函數(shù)，根據(jù)不同的解決方法，可得到動(dòng)態(tài)規(guī)劃算法、回溯算法、貪心算法、分支定界算法等。本文以回溯算法為例。

回溯算法也可稱之為試探法，其是一種系統(tǒng)地搜索問題的解的方法，其基本思想是：從所要解決問題的某一種可能點(diǎn)作為出發(fā)點(diǎn)，搜索從這一點(diǎn)出發(fā)所能達(dá)到的所有可能點(diǎn)，當(dāng)從出發(fā)點(diǎn)到某一種可能點(diǎn)時(shí)若不能到達(dá)目標(biāo)，再返回上一個(gè)出發(fā)點(diǎn)，從另一個(gè)可能點(diǎn)出發(fā)繼續(xù)搜索，直至到達(dá)正確的目標(biāo)。一般回溯法是一種枚舉狀態(tài)空間中所有可能狀態(tài)的系統(tǒng)方法[8-10]。

假設(shè)問題的解的形式為(x1，x2，…，xn)，x1∈S1，x2∈S2，…，xn∈Sn，若已有滿足約束條件的部分解，不妨設(shè)為(x1，x2，…，xi)(i

procedure try(i);/*搜索第i個(gè)分量xi*/

begin

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

forxi∈Si且使得(x1，x2，…，xi-1，xi)滿足約束條件do

begin

記錄滿足條件的xi;

添加相應(yīng)的標(biāo)志；

try(i+1) /*刪除標(biāo)志；恢復(fù)之前的狀態(tài)，根據(jù)具體情況選擇*/

end

end

3.2N皇后的回溯算法

在N×N的國(guó)際象棋盤上，放置N個(gè)皇后，使任何一個(gè)皇后均不能吃掉另一個(gè)，其需滿足的條件為同一行，同一列，同一對(duì)角線上只能有一個(gè)皇后，求放置方法。如N=4時(shí)，有如圖1所示的兩種放置方法。

圖1　4皇后放置圖

問題解的形式：{x:array[i…n]of integer;{x[i]:第i個(gè)皇后放在第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)個(gè)皇后的遞歸算法：

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

var i:integer;

begin

if k=n+1 then print(輸出放置方案：數(shù)組x)；

fori=1 to n do /搜索第k個(gè)皇后所在的列j.

if 第k個(gè)皇后能夠放置在第i列 then

begin

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

try(k+1);

end;

end

3.3回溯算法實(shí)現(xiàn)程序

下面給出使用C++語(yǔ)言來實(shí)現(xiàn)回溯算法的程序：

int main()

{

try(1);

System(“pause”);}

}

int try(int i)

{

int j;

for(j=1;j<=N;j + +)//每個(gè)皇后都有N位置(列)可試放

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

//由于C++不能操作負(fù)數(shù)組，因此考慮加N-1

{//放置皇后，建立相應(yīng)標(biāo)志值

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

b[j]=1;//宣布占領(lǐng)第j列

c[i+j]=1;//占領(lǐng)兩個(gè)對(duì)角線

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

if(i= = N) print();//N個(gè)皇后都放置好，輸出

else try(i+1);//繼續(xù)遞歸放置下一個(gè)皇后

b[j]=0;//遞歸返回即為回溯一步，當(dāng)前皇后退出

c[i+j]=0;

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

}

}

由于算法框架給算法重用提供了一種可能性，同時(shí)由于具有統(tǒng)一的框架，使得算法設(shè)計(jì)變得更加高效。

4結(jié)束語(yǔ)

本文以算法重用為思想，以N皇后問題的回溯算法為實(shí)例，闡述了從算法框架到具體算法的算法設(shè)計(jì)方法。通過算法重用，在解決同類型下不同問題時(shí)無需重新設(shè)計(jì)完整的算法，而是在解決這類問題的算法框架下，根據(jù)自身選擇的實(shí)現(xiàn)函數(shù)，在框架下填充算法的具體細(xì)節(jié)，從而避免了算法設(shè)計(jì)的重復(fù)性工作，節(jié)省了算法設(shè)計(jì)所需的時(shí)間與精力。同時(shí)，由于具有統(tǒng)一框架，程序的后期維護(hù)也得到了良好的保障。

參考文獻(xià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].計(jì)算機(jī)學(xué)報(bào),1995,18(10):775-762.

[5]欒尚敏,馬紹漢.搜索問題的代數(shù)描述及其算法[J].計(jì)算機(jī)研究與發(fā)展,1997,34(11):801-806.

[6]欒尚敏,李未,馬紹漢.算法框架:算法重定位的一種可操作的方法[J].軟件學(xué)報(bào),1999,10(7):679-684.

[7]李云清.基于算法框架的可重用部件設(shè)計(jì)與實(shí)現(xiàn)[J]計(jì)算機(jī)工程與應(yīng)用,2001,37(23):136-138.

[8]原永福.算法設(shè)計(jì)與分析[M].北京:機(jī)械工業(yè)出版社,1998.

[9]盧開澄.計(jì)算機(jī)算法導(dǎo)引:設(shè)計(jì)與分析[M].2版.北京:清華大學(xué)出版社,2006.

[10] Erich Gamma,Richard Helm.設(shè)計(jì)模式:可復(fù)用面向?qū)ο筌浖幕A(chǔ)[M].李英軍,馬曉星,蔡敏,等,譯.北京:機(jī)械工業(yè)出版社,2000.

[11] 李傳湘,陳世鴻,劉海青.程序設(shè)計(jì)方法學(xué)[M].武漢:武漢大學(xué)出版社,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

作者簡(jiǎn)介:崔莉(1977-)，女，碩士，講師。研究方向：計(jì)算機(jī)信息技術(shù)。

doi:10.16180/j.cnki.issn1007-7820.2016.07.008

中圖分類號(hào)TP306.1

文獻(xiàn)標(biāo)識(shí)碼A

文章編號(hào)1007-7820(2016)07-026-04