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

蘇 琳

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

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

蘇 琳

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

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

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

1 概述

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

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

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

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

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

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

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

上述思想可編寫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

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

為了提高效率，減少循環(huán)次數(shù)，利用百雞條件，有些研究者將上述算法進(jìn)行了簡(jiǎ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

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

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

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

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

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

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

即：

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

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

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

另由(3)式知，x必須為數(shù)4的整數(shù)才能使y為整數(shù)，所以在x初值為0時(shí)取其步長(zhǎng)為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)，減少了時(shí)間復(fù)雜度，具體對(duì)比分析如表1所示。

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

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

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

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

[3]黃隆華,陳志輝.算法設(shè)計(jì)與分析課程的“百錢買百雞問題”趣用[J].計(jì)算機(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

國(guó)家自然科學(xué)基金面上項(xiàng)目（61771231）

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