用回溯法求“韓信分油”問題所有解

裴南平

摘要：回溯法是一種常用的計(jì)算機(jī)程序設(shè)計(jì)方法。使用回溯法解決“韓信分油問題”也稱“泊松分酒問題”，在算法中保存每一步執(zhí)行的中間結(jié)果，程序擴(kuò)展前，判斷程序是否進(jìn)入“循環(huán)圈”，程序一旦進(jìn)入“循環(huán)圈”，就不需要往下擴(kuò)展，開始回溯了。如果能合理設(shè)計(jì)擴(kuò)展的條件，防止程序陷入“循環(huán)圈”可以提高程序的效率。

關(guān)鍵詞：算法；回溯法；泊松分酒；循環(huán)圈

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）34-0248-03

Abstract： Backtracking is a commonly used method of computer programming. The use of backtracking method to solve the "Han oil" also known as the " Poisson wine problem"， save every step of execution of the intermediate results in the algorithm， the expansion of the program before the procedure to determine whether to enter the "circle"， once the program into the circle， do not need to expand down and start backtracking. if can design reasonable expansion conditions to prevent the program into a "circle" can improve the efficiency of the program.

Key words： algorithm； backtracking method； Poisson wine； cycle ring

1 背景

韓信是家喻戶曉的漢朝名將，聰明過人。傳說有一天他騎馬路過街市，見有二人爭(zhēng)吵，下馬細(xì)問，原來是一個(gè)賣油的只帶了十斤、七斤、五斤三個(gè)油壺，十斤油壺裝滿了油，七斤、五斤油壺空的，沒有帶秤具，對(duì)方只想買一半，正為無法分出五斤油成交爭(zhēng)執(zhí)。韓信略加思考，立馬給出了解決辦法。

這其實(shí)是一個(gè)利用二個(gè)空的小容器將一個(gè)滿的大容器均分的問題。法國(guó)數(shù)學(xué)家、物理學(xué)家和力學(xué)家泊松曾提出并研究該類問題，所以也稱“泊松分酒問題”。

2 解題算法分析

計(jì)算機(jī)解決該類問題當(dāng)然不需要用泊松研究的數(shù)學(xué)方法，只要利用自身強(qiáng)大快速的計(jì)算能力將所有的情況遍歷，從而找出問題的所有解。

“韓信分油問題”的解是一步一步的步驟，例如韓信當(dāng)時(shí)給出的分油辦法如圖1所示。

韓信的方法總共八步，當(dāng)然解題方法不止一種，而且步驟可能是八步，也可能是九步、十步、...，由于每個(gè)解的步驟不相同，使用普通的窮舉法無法實(shí)現(xiàn)，只能使用回溯法來窮舉實(shí)現(xiàn)。

我們用a代表十斤油壺，b代表七斤油壺，c代表三斤油壺。進(jìn)行下一步操作共有如下六種可能：

1） a倒入b；

2） a倒入c；

3） b倒入a；

4） b倒入c；

5） c倒入a；

6） c倒入b。

求解的每一步都市這六種可能的窮舉，就這樣一部一部擴(kuò)展，直到某個(gè)油壺正好是要分的一半五斤油，就找到了一個(gè)解。

不過擴(kuò)展到哪一步為止？然后回溯，正式文本論述的關(guān)鍵所在。普通的回溯法都是擴(kuò)展到某一固定層數(shù)就開始回溯。分油問題因?yàn)槊總€(gè)解步數(shù)不相同，所以無法擴(kuò)展到某一固定步數(shù)就開始回溯。當(dāng)然可以規(guī)定到了足夠多的n步開始回溯，但是n就不好定了，太小了可能漏掉解，太大了如n=50，就要窮舉6的50次方，費(fèi)事太長(zhǎng)，普通的電腦短時(shí)間無法找到所有解。

當(dāng)進(jìn)行到某一步時(shí)三個(gè)油壺的油量與前面經(jīng)歷的某一步相同，可以稱之為進(jìn)入“循環(huán)圈”。一步一步擴(kuò)展下去，如果沒有找到解停下并回溯，肯定會(huì)進(jìn)入“循環(huán)圈”。一旦進(jìn)入“循環(huán)圈”，就不需要往下擴(kuò)展，就可以回溯了。這樣做，不但合理地設(shè)定了擴(kuò)展的終止條件，而且大大提高了求解的效率，因?yàn)樘^了很多無聊的步驟，如一個(gè)油壺倒入另一油壺，立馬又倒回來。

3 C語(yǔ)言完整程序

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

通過運(yùn)行上面程序，可以求出“韓信分油問題”共有十七個(gè)不同的解，最長(zhǎng)步驟的解要十七步，最短步驟的解只需要八步，也就是韓信給出的辦法。

參考文獻(xiàn)：

[1] 李青， 張軍， 張學(xué)軍. 解決排班問題的多目標(biāo)優(yōu)化模型及算法研究[J]. 北京航空航天大學(xué)學(xué)報(bào)， 2003（10）.

[2] 謝玉庚. 用回溯法編程求解愛因斯坦謎題[J]. 電腦與電信， 2016（10）.

[3] 徐永琳， 巫青山， 林川. 遞歸回溯法求解整數(shù)線性規(guī)劃及MATLAB實(shí)現(xiàn)[J]. 蘭州文理學(xué)院學(xué)報(bào)：自然科學(xué)版， 2014（7）.endprint