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

裴南平

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

關鍵詞：算法；回溯法；泊松分酒；循環圈

中圖分類號：TP311 文獻標識碼：A 文章編號：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 背景

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

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

2 解題算法分析

計算機解決該類問題當然不需要用泊松研究的數學方法，只要利用自身強大快速的計算能力將所有的情況遍歷，從而找出問題的所有解。

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

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

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

1） a倒入b；

2） a倒入c；

3） b倒入a；

4） b倒入c；

5） c倒入a；

6） c倒入b。

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

不過擴展到哪一步為止？然后回溯，正式文本論述的關鍵所在。普通的回溯法都是擴展到某一固定層數就開始回溯。分油問題因為每個解步數不相同，所以無法擴展到某一固定步數就開始回溯。當然可以規定到了足夠多的n步開始回溯，但是n就不好定了，太小了可能漏掉解，太大了如n=50，就要窮舉6的50次方，費事太長，普通的電腦短時間無法找到所有解。

當進行到某一步時三個油壺的油量與前面經歷的某一步相同，可以稱之為進入“循環圈”。一步一步擴展下去，如果沒有找到解停下并回溯，肯定會進入“循環圈”。一旦進入“循環圈”，就不需要往下擴展，就可以回溯了。這樣做，不但合理地設定了擴展的終止條件，而且大大提高了求解的效率，因為跳過了很多無聊的步驟，如一個油壺倒入另一油壺，立馬又倒回來。

3 C語言完整程序

4 結束語

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

參考文獻：

[1] 李青， 張軍， 張學軍. 解決排班問題的多目標優化模型及算法研究[J]. 北京航空航天大學學報， 2003（10）.

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

[3] 徐永琳， 巫青山， 林川. 遞歸回溯法求解整數線性規劃及MATLAB實現[J]. 蘭州文理學院學報：自然科學版， 2014（7）.endprint