张晨　王明根　李宇豪　王洁　霍迎秋

摘要：为了解决泊松分酒的一般性问题，本文结合图论以及广度优先搜索算法，考虑求解的时空复杂度，借助map存放复杂类型数据的特点并根据实际设置剪枝函数，进而设计出该类问题的一般性求解算法。

关键词：泊松分酒问题；广度优先搜索；状态转移；图论

中图分类号：TP301.6 文献标识码：A 文章编号：1007-9416（2018）04-0038-02

1 引言

泊松分酒问题是由泊松所提出来的求解三个无刻度酒瓶由12、8、5品脱多次转移为6、6、0品脱的过程的智力问题，一直在中小学奥赛乃至大学的数学类竞赛中频繁出现，引发了广泛关注。 对这类问题的一般性问题，即当无刻度的酒瓶个数为n时的状态转移问题，成为研究的热点。

2 一般性泊松分酒问题及分析

一般性的分酒问题是指n个没有刻度的酒瓶，n个瓶子的容量表示为，n个瓶子的初始状态表示为，讨论是否存在使n个酒瓶的最终状态为的方法。

一般性分酒问题的求解方法空间复杂度为，每一种瓶子的状态有种可能，故状态数为，随着n的增加，基于邻接矩阵的方法，将会产生很多无用的状态节点，造成空间的浪费。对于一般问题的时间复杂度则是，状态迁移过程直接影响了时间复杂度，状态的每一次转移都有种可能性。并可能出现重复遍历或者循环遍历的情况，增加了时间复杂度。

3 BFS算法及其在分酒问题的应用

3.1 广度优先搜索（BFS）

BFS是一种基于图的基础搜索方法，是以一种分层递进的搜索方式进行搜索的过程，如图1所示。……