基于圖的泊松分酒問(wèn)題一般解的研究

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

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

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

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

1 引言

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

2 一般性泊松分酒問(wèn)題及分析

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

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

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

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

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

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

3.2 分酒問(wèn)題分析

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

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

3.3 分酒問(wèn)題算法設(shè)計(jì)

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

現(xiàn)給出基本實(shí)現(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è)置三個(gè)，一是剪掉已經(jīng)遍歷過(guò)的狀態(tài)，是剪掉不能到達(dá)的狀態(tài)，三是具體問(wèn)題具體分析從而限制。通過(guò)對(duì)倒酒過(guò)程所到達(dá)的節(jié)點(diǎn)狀態(tài)的分析，存在一些不可能到達(dá)的狀態(tài)，如（0，0，…，0）等，鑒于很多它們的存在，為防止程序在搜索過(guò)程中，進(jìn)入死循環(huán)又不知的情況，必須為具體的問(wèn)題的步數(shù)設(shè)定一個(gè)限度。若超過(guò)了這個(gè)限度，即認(rèn)為問(wèn)題無(wú)解。

4 實(shí)例

4.1 實(shí)例分析

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

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

4.2 搜索過(guò)程

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

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

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

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

5 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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

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

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