基于枚舉算法的優(yōu)化方法研究

梁 潘

（阿壩師范高等?？茖W(xué)校電子信息工程系，四川郫縣 611741）

引 言

著名計(jì)算機(jī)科學(xué)家沃思（Nikiklaus Wirth）曾提出一個(gè)公式“數(shù)據(jù)結(jié)構(gòu)+算法=程序”，實(shí)際上算法是程序的靈魂.[1]在程序設(shè)計(jì)中經(jīng)常使用的算法有：枚舉算法、遞歸算法、二分算法、貪心算法、二叉樹算法等.枚舉法，常常稱之為窮舉法，是指從可能的集合中一一窮舉各個(gè)元素，用題目給定的約束條件判定哪些是無(wú)用的，哪些是有用的，能使命題成立者，即為問(wèn)題的解，其優(yōu)點(diǎn)是算法簡(jiǎn)單，結(jié)果準(zhǔn)確、全面，在解決眾多實(shí)際問(wèn)題中被廣泛使用，[2]但枚舉法效率不高，為了更好地發(fā)揮它的優(yōu)點(diǎn)，編寫出高效的程序，必須對(duì)其進(jìn)行優(yōu)化，下面以“百錢百雞”問(wèn)題為例，分析使用枚舉算法的程序的優(yōu)化思路與方法.

1 枚舉法

公元前5世紀(jì)，我國(guó)古代數(shù)學(xué)家張丘建在《算經(jīng)》一書中提出了百雞問(wèn)題：雞翁一值錢五，雞母一值錢三，雞雛三值錢一.百錢買百雞，問(wèn)雞翁、母、雛各幾何?

1.1 傳統(tǒng)枚舉算法（算法一）

從數(shù)學(xué)分析來(lái)看，設(shè)變量cock、hen、chick分別代表雞翁、雞母、雞雛，可以構(gòu)建兩個(gè)三元一次方程組：

1）cock + hen + chick = 100，2）cock*5 + hen*3 + chick/3 = 100，求cock、hen、chick的解，根據(jù)枚舉法的特點(diǎn)結(jié)合題意，此題很顯然使用枚舉法，對(duì)雞翁、雞母、雞雛的可能只數(shù)逐一進(jìn)行測(cè)試，直到全部可能只數(shù)都試完為止.

通過(guò)分析，三個(gè)變量的取值范圍是：0≤cock≤20，0≤hen≤33，0≤chick≤100，這樣，cock、hen、chick的可能組合方式就有21*34*101 = 72 114種，對(duì)每一種組合再測(cè)試是否符合“百錢、百雞”這兩個(gè)條件，若符合，則該組合就是問(wèn)題的一個(gè)解，[3]圖1為算法一N-S流程圖.

基于C語(yǔ)言的核心代碼如下：

圖1 ：算法一N--SS流程圖

1.2 利用加強(qiáng)約束條件改進(jìn)的枚舉算法（算法二）

從上面的算法及C程序來(lái)看，雖然能夠計(jì)算出每一個(gè)解，但是效率比較低，此時(shí)可以利用加強(qiáng)約束條件的方法改進(jìn)枚舉算法.由題可知，三種雞的和恒為100，只要枚舉兩種雞（cock，hen），第三種雞（chick）就可以根據(jù)約束條件求得，由cock + hen + chick = 100方程可得chick = 100 - cock -hen，這樣就可減少一層枚舉循環(huán)縮小了搜索范圍，cock、hen、chick的可能組合方式就只有21*34 = 714種，其組合方式不及傳統(tǒng)枚舉法的 1%，大大提高了程序的工作效率，[4]圖2為算法二N-S流程圖.

改進(jìn)后的核心代碼如下：

圖2 ：算法二N-S流程圖

1.3 利用數(shù)學(xué)分析改進(jìn)的枚舉算法（算法三）

在利用枚舉算法解決實(shí)際問(wèn)題的過(guò)程中，經(jīng)常利用數(shù)學(xué)分析方法化簡(jiǎn)方程式，進(jìn)一步減少枚舉的次數(shù)提高工作效率.根據(jù)題意得到方程（1）cock + hen + chick = 100;（2）cock*5 + hen*3 + chick/3 = 100，觀察其特點(diǎn)，消去一個(gè)未知數(shù)chick，得到一個(gè)二元一次方程：cock*7 + hen*4 = 100，通過(guò)分析，可進(jìn)一步縮小兩個(gè)變量的取值范圍是：0≤cock≤14，0≤hen≤25；同時(shí)由該方程得到 hen = (100-cock*7)/4，因此，只要枚舉cock就可根據(jù)約束條件求得hen和chick，進(jìn)而將兩層循環(huán)改進(jìn)為單層循環(huán)，這樣再次縮小了枚舉范圍，cock、hen、chick的可能組合方式就只有15種，極大的提高了程序的執(zhí)行效率，算法三N-S流程圖如圖3.

改進(jìn)后的核心代碼如下：

圖3 ：算法三N--SS流程圖

2 結(jié)果比較

通過(guò)表1可以看出，三種程序使用不同的算法，但得到了相同的運(yùn)行結(jié)果，經(jīng)過(guò)改進(jìn)后的算法枚舉次數(shù)明顯減少，時(shí)間復(fù)雜度也由O(n3)降低到O(n)，對(duì)循環(huán)工作量產(chǎn)生了極大的影響，程序的執(zhí)行效率迥然不同，后面兩個(gè)特別是第三個(gè)程序執(zhí)行效率明顯提高.

表1 各種算法比較結(jié)構(gòu)圖

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

程序=算法設(shè)計(jì)+數(shù)據(jù)結(jié)構(gòu)+程序設(shè)計(jì)方法+語(yǔ)言工具，[1]從中我們可以看出，算法設(shè)計(jì)是整個(gè)程序設(shè)計(jì)的核心和靈魂，是解決實(shí)際問(wèn)題的重要方法和步驟.在使用枚舉算法解決實(shí)際問(wèn)題時(shí)要想提高程序的執(zhí)行效率，增強(qiáng)程序的可理解性和可讀性，必須精心設(shè)計(jì)、優(yōu)化算法，從研究效果看加強(qiáng)約束條件縮小枚舉范圍，結(jié)合數(shù)學(xué)分析減少循環(huán)嵌套正是行之有效的優(yōu)化枚舉算法的方法.

[1]譚浩強(qiáng).C語(yǔ)言程序設(shè)計(jì)（第二版）[M].北京：清華大學(xué)出版社，2002.

[2]林小茶.C語(yǔ)言程序設(shè)計(jì)[M].北京：中國(guó)鐵道出版社，2004.

[3]劉金祥.從“百錢百雞”問(wèn)題看如何進(jìn)行 C語(yǔ)言程序設(shè)計(jì)[J].電腦學(xué)習(xí)，2007（5）：59-60.

[4]應(yīng)進(jìn)平.淺談 C語(yǔ)言程序設(shè)計(jì)中算法設(shè)計(jì)的作用[J].科技情報(bào)開發(fā)與經(jīng)濟(jì)，2006（24）：261.