蘇 琳

(山東科技大學(xué) 土木工程與建筑學(xué)院, 山東 青島 266000 )

求解“百錢百雞”問題的最優(yōu)化算法

蘇 琳

(山東科技大學(xué) 土木工程與建筑學(xué)院, 山東 青島 266000 )

“百錢百雞”問題是一個經(jīng)典的窮舉問題，雖然該問題比較簡單，但是目前的算法并沒有實現(xiàn)求解過程的最優(yōu)化。本文充分利用數(shù)學(xué)模型中的隱含條件，減少未知量的個數(shù)，有效控制循環(huán)變量的范圍與步長來優(yōu)化循環(huán)次數(shù)，最終循環(huán)執(zhí)行4次即可求解，使得算法的時間復(fù)雜度從降為，達(dá)到算法的最優(yōu)化，為窮舉類問題的求解提供一種新的思路。

窮舉算法；百錢百雞；優(yōu)化；Matlab

1 概述

窮舉法也稱為枚舉法，這種算法是把問題涉及的可能情況一一羅列出來，并且根據(jù)題目的條件和實際背景逐個給予判斷，從中挑選出符合條件的解答。它適用的條件是：暫時找不出解決問題的更好途徑的情況下；有明顯的窮舉范圍且求解對象應(yīng)該是有限的；可以按某種窮舉規(guī)則列舉對象[1]。在很多數(shù)學(xué)問題求解中，窮舉法作為一種試探求解的方法有著廣泛的應(yīng)用[2]。

“百錢百雞”問題是一個很經(jīng)典的窮舉問題。公元前5世紀(jì)，我國古代數(shù)學(xué)家張丘建在《算經(jīng)》中提出：雞翁一值錢五，雞母一值錢三，雞雛三值錢一。百錢買百雞，問雞翁、母、雛各幾何[3]？

在現(xiàn)行的計算機高級語言編程中，經(jīng)常引用這個數(shù)學(xué)問題進(jìn)行循環(huán)結(jié)構(gòu)的講解。在算法的設(shè)計中，時間復(fù)雜度有的是，也有的是,循環(huán)執(zhí)行的次數(shù)有多達(dá)上萬次，小則數(shù)百次[4]。本文在進(jìn)一步分析隱含條件的基礎(chǔ)上，提出一種新的窮舉算法，在求解正確的前提下，使算法復(fù)雜度僅為,循環(huán)執(zhí)行4次即可求解，最大程度地優(yōu)化了問題的求解過程，并通過Matlab給出了算法實現(xiàn)[5]。

2 現(xiàn)行的求解算法

現(xiàn)行的求解算法主要有兩種，一種是利用三重循環(huán)結(jié)構(gòu)來實現(xiàn)的，另一種是利用二重循環(huán)結(jié)構(gòu)來實現(xiàn)的，無論采用那一種算法都是基于下面的數(shù)學(xué)分析。

設(shè)雞翁、雞母、雞雛的個數(shù)分別為x、y、z,由題意可得到下面的方程組：

題意要求用100錢買100只雞，若全買公雞最多買20只，顯然x的值在0-20之間；同理，y的值在0-33之間，z的值在0-100之間。因此，x、y、z可能的組合方式有21*34*101=72114 種，對每一種組合方式，再測試是否符合“百錢、百雞”這兩個條件；若符合，則該組合就是問題的一個解。

上述思想可編寫MATLAB程序如下：

clc;

clear all;

for cock=0:20

for hen=0:33

for chicken=0:100

if (5*cock+3*hen+chicken/3==100)&&(cock+hen+chick en==100)

[cock,hen,chicken]

end

end

end

end

對于上述求解我們稱為算法1，該算法在一般的教科書中都有陳述，很明顯該算法的時間復(fù)雜度為，最內(nèi)層的if語句被執(zhí)行了72114次。在答案僅有4中組合的情況下，將有72110次是無意義的重復(fù)執(zhí)行，極大浪費了系統(tǒng)資源。

為了提高效率，減少循環(huán)次數(shù)，利用百雞條件，有些研究者將上述算法進(jìn)行了簡單優(yōu)化，變?nèi)匮h(huán)為二重循環(huán)，改進(jìn)后的算法描述如下：

clc;

clear all;

for cock=0:20

for hen=0:33

chicken=100-cock-hen;

if (5*cock+3*hen+chicken/3==100)

[cock,hen,chicken]

end

end

end

對于上述求解方法我們稱為算法2，該算法的時間復(fù)雜度為，最內(nèi)層的if語句被執(zhí)行了714次，與算法1相比執(zhí)行次數(shù)明顯減少，該算法是目前為止比較好的，也得到眾多學(xué)者的賞識；但是，循環(huán)次數(shù)還是比較多的。

3 改進(jìn)的窮舉算法

為了進(jìn)一步減少循環(huán)次數(shù)，我們從改變循環(huán)結(jié)構(gòu)的循環(huán)重數(shù)、精確計算循環(huán)增量兩個角度進(jìn)行優(yōu)化。

3.1 改變循環(huán)結(jié)構(gòu)的重數(shù)

通過分析算法1、算法2知，循環(huán)重數(shù)是由未知數(shù)的數(shù)量決定的，減少未知數(shù)可以減少循環(huán)的重數(shù)，為此我們利用消元法將方程組化簡以減少未知數(shù)，再用假設(shè)的變量來表示未知數(shù)，這樣可以改變循環(huán)結(jié)構(gòu)。

首先，將方程組(1)的式*3-(2)式，得：

即：

這樣就可以用變量x表示變量y，改變算法2的二重循環(huán)為單層循環(huán)。

3.2 循環(huán)變量的范圍與步長的精確設(shè)置

因為y≥0，且y為整數(shù)，所以25-7x/4≥0，即x≤1（當(dāng)x=13時，不能使y為整數(shù)）

另由(3)式知，x必須為數(shù)4的整數(shù)才能使y為整數(shù)，所以在x初值為0時取其步長為4。

綜合以上優(yōu)化分析，提出新的窮舉算法如下：

clc;

clear all;

for cock=0:4:12

hen=25-(cock/4)*7;

chicken=100-cock-hen;

[cock,hen,chicken]

end

4 結(jié)果分析為了比較算法的優(yōu)劣，我們將所提新算法稱為算法3，該算法在進(jìn)一步分析隱含條件的基礎(chǔ)上，繼續(xù)消元，真正改變多重循環(huán)為單重循環(huán)，減少了時間復(fù)雜度，具體對比分析如表1所示。

表1 算法結(jié)果對比

通過對比可以發(fā)現(xiàn)，無論在時間復(fù)雜度還是在循環(huán)次數(shù)上，本文所提出的算法3都達(dá)到最優(yōu)化狀態(tài)（“百錢百雞”問題有4中解），這為我們求解類似的窮舉問題提供了一個很好的思路：應(yīng)充分挖掘和利用已知條件，尋找隱含條件因素來限制窮舉的次數(shù)以提高求解效率。

[1]李巍,徐愛功,趙亮,王昶,高良博.基于Matlab的測量坐標(biāo)系統(tǒng)轉(zhuǎn)換[J].煤炭學(xué)報,2014,39(01):88-92.

[2]吳文肖.窮舉法在確定帶電粒子在磁場中軌跡的應(yīng)用[J].物理教學(xué)探討,2017,35(500):36-38.

[3]黃隆華,陳志輝.算法設(shè)計與分析課程的“百錢買百雞問題”趣用[J].計算機教育,2016(03):143-145.

[4]R.VenkataRao,G.G.Waghmare.A New Optimization Algorithm for Solving Complex Constrained Design Optimization Problems[J].Engineering Optimization,2017,49(01):60-83.

[5]呼娜.淺談如何激發(fā)學(xué)習(xí)高等數(shù)學(xué)的興趣[J].山東工業(yè)技術(shù),2016(03):220.

10.16640/j.cnki.37-1222/t.2018.01.197

國家自然科學(xué)基金面上項目（61771231）

蘇琳(1998-),女,山東棲霞人,本科,助教,研究方向：主要從事優(yōu)化設(shè)計、材料力學(xué)等方面的研究。