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

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

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

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

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

1 引言

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

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

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

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

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

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

BFS是一種基于圖的基礎(chǔ)搜索方法，是以一種分層遞進(jìn)的搜索方式進(jìn)行搜索的過程，如圖1所示。……