基于圖的泊松分酒問題一般解的研究

張晨　王明根　李宇豪　王潔　霍迎秋

摘要：為了解決泊松分酒的一般性問題，本文結(jié)合圖論以及廣度優(yōu)先搜索算法，考慮求解的時空復(fù)雜度，借助map存放復(fù)雜類型數(shù)據(jù)的特點并根據(jù)實際設(shè)置剪枝函數(shù)，進(jìn)而設(shè)計出該類問題的一般性求解算法。

關(guān)鍵詞：泊松分酒問題；廣度優(yōu)先搜索；狀態(tài)轉(zhuǎn)移；圖論

中圖分類號：TP301.6 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2018）04-0038-02

1 引言

泊松分酒問題是由泊松所提出來的求解三個無刻度酒瓶由12、8、5品脫多次轉(zhuǎn)移為6、6、0品脫的過程的智力問題，一直在中小學(xué)奧賽乃至大學(xué)的數(shù)學(xué)類競賽中頻繁出現(xiàn)，引發(fā)了廣泛關(guān)注。 對這類問題的一般性問題，即當(dāng)無刻度的酒瓶個數(shù)為n時的狀態(tài)轉(zhuǎn)移問題，成為研究的熱點。

2 一般性泊松分酒問題及分析

一般性的分酒問題是指n個沒有刻度的酒瓶，n個瓶子的容量表示為，n個瓶子的初始狀態(tài)表示為，討論是否存在使n個酒瓶的最終狀態(tài)為的方法。

一般性分酒問題的求解方法空間復(fù)雜度為，每一種瓶子的狀態(tài)有種可能，故狀態(tài)數(shù)為，隨著n的增加，基于鄰接矩陣的方法，將會產(chǎn)生很多無用的狀態(tài)節(jié)點，造成空間的浪費。對于一般問題的時間復(fù)雜度則是，狀態(tài)遷移過程直接影響了時間復(fù)雜度，狀態(tài)的每一次轉(zhuǎn)移都有種可能性。并可能出現(xiàn)重復(fù)遍歷或者循環(huán)遍歷的情況，增加了時間復(fù)雜度。

3 BFS算法及其在分酒問題的應(yīng)用

3.1 廣度優(yōu)先搜索（BFS）

BFS是一種基于圖的基礎(chǔ)搜索方法，是以一種分層遞進(jìn)的搜索方式進(jìn)行搜索的過程，如圖1所示。對應(yīng)廣度優(yōu)先搜索算法過程如下：

（1）從頂點①出發(fā)，并訪問此頂點；（2）從①出發(fā)，訪問①的各個未曾訪問的鄰接點②，④，⑤；然后，依次從②，④，⑤出發(fā)訪問各自未被訪問的鄰接點；（3）重復(fù)（2）直到全部節(jié)點被訪問或找到結(jié)果。

3.2 分酒問題分析

對于一般分酒問題，狀態(tài)遍歷過程會造成巨大的時間開銷。并且當(dāng)搜索的過程不斷地深入，必存在很多節(jié)點重復(fù)遍歷的情況，將會導(dǎo)致很多無用遍歷或者死循環(huán)遍歷等，故需要對每一個遍過的狀態(tài)進(jìn)行標(biāo)記。據(jù)分析可知其狀態(tài)構(gòu)成的矩陣為低密度矩陣，存在著大量不可到達(dá)的無用狀態(tài)節(jié)點。因此當(dāng)n很大時，將導(dǎo)致巨大且無用的空間開銷，故并不需要專門開辟大量空間去存儲，而可通過隊列實時動態(tài)變化。并采用map容器進(jìn)行存儲，其可通過的方式進(jìn)行存儲數(shù)據(jù)，用key表示一個具體的狀態(tài)字符串，value表示上一具體狀態(tài)遷移變化成key狀態(tài)過程的字符串。從而可以方便的回溯尋找最小路徑。

綜上，將狀態(tài)節(jié)點的遍歷過程視為廣搜遍歷一棵滿（n*（n-1））叉樹的過程（當(dāng)前狀態(tài)到下一狀態(tài)有n*（n-1）種可能）。當(dāng)搜索到結(jié)果時，可將map容器存儲的內(nèi)容輸出或無結(jié)果。

3.3 分酒問題算法設(shè)計

根據(jù)初始、最終狀態(tài)及酒瓶容量，利用getResult（）函數(shù)求初始到最終狀態(tài)所經(jīng)歷的路徑。其中g(shù)etResult（）函數(shù)調(diào)用了Dochange（）得到轉(zhuǎn)移后的結(jié)果以及printTrace（）函數(shù)輸出路徑。

現(xiàn)給出基本實現(xiàn)流程如圖2所示。

其中變量含義如下：

i，j：第一、二次循環(huán)的循環(huán)變量；A，B：分別代表了倒出瓶和倒入瓶；A.v，B.v：分別代表了A，B瓶的狀態(tài)；A.B，B.B：分別代表了A，B瓶的容量。

本算法剪枝函數(shù)共設(shè)置三個，一是剪掉已經(jīng)遍歷過的狀態(tài)，是剪掉不能到達(dá)的狀態(tài)，三是具體問題具體分析從而限制。通過對倒酒過程所到達(dá)的節(jié)點狀態(tài)的分析，存在一些不可能到達(dá)的狀態(tài)，如（0，0，…，0）等，鑒于很多它們的存在，為防止程序在搜索過程中，進(jìn)入死循環(huán)又不知的情況，必須為具體的問題的步數(shù)設(shè)定一個限度。若超過了這個限度，即認(rèn)為問題無解。

4 實例

4.1 實例分析

運(yùn)用上述所設(shè)計的算法，下面以一個實例來演示問題的解決和進(jìn)行算法說明的過程。其中n取3，3個瓶子容量為（8 5 3），3個瓶子的初始狀態(tài)為（8 0 0），3個瓶子的最終狀態(tài)為（4，4，0）。

依照上述算法，因有3個酒瓶，故當(dāng)從搜索隊列中取出一個狀態(tài)后，現(xiàn)狀態(tài)到下一狀態(tài)的選擇有6條路徑（2*3），包括0、1、2瓶分別倒入其它非自己的瓶。故搜索樹是一個滿6叉樹，如圖3所示。

4.2 搜索過程

“A，B，C”代表酒瓶的狀態(tài)，若其后跟×表示該狀態(tài)不符合條件，其下子樹被剪?！?1”表示不符合狀態(tài)轉(zhuǎn)換條件，無返回。“-”表示轉(zhuǎn)換無效，值與之前得到的同。X→Y代表將X瓶中的酒倒入Y瓶中，[（A，B，C），（D，E，F(xiàn)，）-X→Y]表示狀態(tài)的遷移過程，由狀態(tài)“D，E，F(xiàn)”是在狀態(tài)“A，B，C”下將X瓶中的酒倒入Y瓶中得到的。

當(dāng)從搜索隊列中取出狀態(tài)是“8，0，0”時，隊列為空。廣搜結(jié)果如表1所示。

依次搜索與隊列首節(jié)點相鄰的節(jié)點并添加到搜索隊列中，直到搜索到要求的狀態(tài)或者隊列為空。本例經(jīng)過上述過程的13次循環(huán)，搜索得到的結(jié)果樹如圖4所示。

搜索到狀態(tài)“4，4，0”時，根據(jù)map中的記錄利用棧進(jìn)行逆序輸出，輸出結(jié)果如路徑II所示。

5 結(jié)語

本文基于圖論和廣度優(yōu)先搜索算法解決了分酒問題的一般性問題。其中剪枝函數(shù)的設(shè)置和存儲方式的選擇，極大地優(yōu)化了程序的結(jié)構(gòu)，降低了時間復(fù)雜度，有效的提高了算法的效率。該方法對各種無刻度液體的多種狀態(tài)轉(zhuǎn)換或者特定方式的分配提供了有益的解決方法和思路，具有現(xiàn)實意義。

參考文獻(xiàn)

[1]許卓群，張乃孝，等.數(shù)據(jù)結(jié)構(gòu)[M].北京：高等教育出版社，1981

[2]張軍.算法設(shè)計與分析[M].北京：清華大學(xué)出版社，2011.

[3]周培德.計算幾何———算法設(shè)計與分析（第4版）[M].北京：清華大學(xué)出版社，2011

[4]鄭宗漢，鄭曉明.算法設(shè)計與分析[M].北京：清華大學(xué)出版，2011

[5]王德超.程序設(shè)計中的動態(tài)數(shù)組空間分配方法研究[J].軟件導(dǎo)刊，2014，13（4）：6-8.

[6]劉艮，楊玉琴，蔣天發(fā).基于容器對象的動態(tài)控件數(shù)組研究[J].現(xiàn)代電子技術(shù)，2012，35（1）：146-149.

[7]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，2009：44-47