基于图的泊松分酒问题一般解的研究

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

摘要：为了解决泊松分酒的一般性问题，本文结合图论以及广度优先搜索算法，考虑求解的时空复杂度，借助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所示。对应广度优先搜索算法过程如下：

（1）从顶点①出发，并访问此顶点；（2）从①出发，访问①的各个未曾访问的邻接点②，④，⑤；然后，依次从②，④，⑤出发访问各自未被访问的邻接点；（3）重复（2）直到全部节点被访问或找到结果。

3.2 分酒问题分析

对于一般分酒问题，状态遍历过程会造成巨大的时间开销。并且当搜索的过程不断地深入，必存在很多节点重复遍历的情况，将会导致很多无用遍历或者死循环遍历等，故需要对每一个遍过的状态进行标记。据分析可知其状态构成的矩阵为低密度矩阵，存在着大量不可到达的无用状态节点。因此当n很大时，将导致巨大且无用的空间开销，故并不需要专门开辟大量空间去存储，而可通过队列实时动态变化。并采用map容器进行存储，其可通过的方式进行存储数据，用key表示一个具体的状态字符串，value表示上一具体状态迁移变化成key状态过程的字符串。从而可以方便的回溯寻找最小路径。

综上，将状态节点的遍历过程视为广搜遍历一棵满（n*（n-1））叉树的过程（當前状态到下一状态有n*（n-1）种可能）。当搜索到结果时，可将map容器存储的内容输出或无结果。

3.3 分酒问题算法设计

根据初始、最终状态及酒瓶容量，利用getResult（）函数求初始到最终状态所经历的路径。其中getResult（）函数调用了Dochange（）得到转移后的结果以及printTrace（）函数输出路径。

现给出基本实现流程如图2所示。

其中变量含义如下：

i，j：第一、二次循环的循环变量；A，B：分别代表了倒出瓶和倒入瓶；A.v，B.v：分别代表了A，B瓶的状态；A.B，B.B：分别代表了A，B瓶的容量。

本算法剪枝函数共设置三个，一是剪掉已经遍历过的状态，是剪掉不能到达的状态，三是具体问题具体分析从而限制。通过对倒酒过程所到达的节点状态的分析，存在一些不可能到达的状态，如（0，0，…，0）等，鉴于很多它们的存在，为防止程序在搜索过程中，进入死循环又不知的情况，必须为具体的问题的步数设定一个限度。若超过了这个限度，即认为问题无解。

4 实例

4.1 实例分析

运用上述所设计的算法，下面以一个实例来演示问题的解决和进行算法说明的过程。其中n取3，3个瓶子容量为（8 5 3），3个瓶子的初始状态为（8 0 0），3个瓶子的最终状态为（4，4，0）。

依照上述算法，因有3个酒瓶，故当从搜索队列中取出一个状态后，现状态到下一状态的选择有6条路径（2*3），包括0、1、2瓶分别倒入其它非自己的瓶。故搜索树是一个满6叉树，如图3所示。

4.2 搜索过程

“A，B，C”代表酒瓶的状态，若其后跟×表示该状态不符合条件，其下子树被剪。“-1”表示不符合状态转换条件，无返回。“-”表示转换无效，值与之前得到的同。X→Y代表将X瓶中的酒倒入Y瓶中，[（A，B，C），（D，E，F，）-X→Y]表示状态的迁移过程，由状态“D，E，F”是在状态“A，B，C”下将X瓶中的酒倒入Y瓶中得到的。

当从搜索队列中取出状态是“8，0，0”时，队列为空。广搜结果如表1所示。

依次搜索与队列首节点相邻的节点并添加到搜索队列中，直到搜索到要求的状态或者队列为空。本例经过上述过程的13次循环，搜索得到的结果树如图4所示。

搜索到状态“4，4，0”时，根据map中的记录利用栈进行逆序输出，输出结果如路径II所示。

5 结语

本文基于图论和广度优先搜索算法解决了分酒问题的一般性问题。其中剪枝函数的设置和存储方式的选择，极大地优化了程序的结构，降低了时间复杂度，有效的提高了算法的效率。该方法对各种无刻度液体的多种状态转换或者特定方式的分配提供了有益的解决方法和思路，具有现实意义。

参考文献

[1]许卓群，张乃孝，等.数据结构[M].北京：高等教育出版社，1981

[2]张军.算法设计与分析[M].北京：清华大学出版社，2011.

[3]周培德.计算几何———算法设计与分析（第4版）[M].北京：清华大学出版社，2011

[4]郑宗汉，郑晓明.算法设计与分析[M].北京：清华大学出版，2011

[5]王德超.程序设计中的动态数组空间分配方法研究[J].软件导刊，2014，13（4）：6-8.

[6]刘艮，杨玉琴，蒋天发.基于容器对象的动态控件数组研究[J].现代电子技术，2012，35（1）：146-149.

[7]严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，2009：44-47