文档介绍：题目： 基于盲目搜索算法求解泊松分酒问题
【摘要】
分酒问题的描述在历史上有很多版本，如泊松分酒、韩信分油等。但是它们的本质 都是相同的，无论是中间的转换过程中的各个杯子的容量，还是目标和初始的容量，都 可以看作是网络中的一个节点。而两种状态量之间是否可以进行转换可以看作是网络中 两个节点是否连通。由此原问题的是否可解、最少步数、多少种方式可以转化为网络中 两个节点是否连通、最短路径、最短路径的条数的问题。
对于问题一，利用盲目搜索算法，由起始点出发进行搜索，如果找到了目标节点, 则停止搜索，输出结果。如果没有找到，则说明原问题不可解。
对于问题二，本文通过研究各个状态之间的转换关系，列写方程，通过判断方程是 否有整数解來判定原问题是否可解。并通过系数的求和來判断该解是否是最优解。
对于问题三，通过研究各个版本的分酒问题，发现史泰因豪斯在《数学万花筒》中 的表述：有装有14千克酒的容器，另外有可装5千克和9千克酒的容器，要把酒平分 的问题即可满足要求。并利用该问题对模型进行了检验。
最终，本文对于更大规模的分酒问题提出了自己的想法和改进思路，如利用模型二, 首先剔除掉不连通的点，建立一个网络拓扑图，利用蚁群算法等智能算法，求解最短路 问题，得到相对最优的解。
关键词：泊松分酒盲目搜索不定方程蚁群算法
一、问题重述
分酒问题是一个十分著名的智力问题。在历史上这个问题有很多版本：泊松分酒、 韩信分油等。他们的原问题可以表述为三个容积不等的瓶子，如何实现将酒量等分。显 然这个问题的规模较小，可以通过人工來解决，然而当问题的规模变大，手工就变得无 能为力了。这就要求我们建立合适的模型來描述更大规模和一般性的问题，并利用合适 的算法求解模型。请尝试从基本问题出发建立数学模型解决以下问题：
问题一：现有一只装满12斤酒的瓶子和三只分别装10斤、6斤和3斤酒的空瓶， 如何才能将这12斤酒分成三等份。如果进行四等份呢，结果如何？如果4个瓶子分别 要求装5斤、3斤、2斤、2斤，又能否实现？试建立数学模型并设计算法，求最少经过 多少步操作完成，且有多少种方式可采用最少步数完成。要求对实现方式给出详细操作 步骤。
问题二一般问题:设有〃个瓶子，每个瓶子最多装酒数量用向量表示为貼,花,…心）。 现在初始各瓶子装酒为（心,兀2。,…，兀°）。现要实现将各瓶子装酒为要求不 凭借任何其它工具，问能否实现？若能实现，给出实现的方法，并给出充分理由说明是 否是最少步数。并对你所使用的模型和算法进行分析说明。
问题三：设计一个实例，要求最少完成步数不少于13步。给岀从初始状态到目标 状态的详细实现步骤。
二、问题的分析
原问题有很多个版本：
版本曰本分油问题。有一个装满油的8公升容器，另有一个5公升及3公升的 空容器各一个，且三个容器都没有刻度，试将此8公升油分成4公升。.
版本2：法国著名数学家泊松年轻时研究过的一道题：
某人有12品脱美酒，想把一半赠人，但没有6品脱的容器，而只有一个8品脫和 一个5品脱的容器，问怎样才能把6品脱的酒倒入8品脱的容器中。
版本3：我国的韩信分油问题：韩信遇到两个路人争执不下，原因是两人有装满10 斤的油篓和两个3斤、7斤的空油篓，无法平均分出两份，每份5斤油。韩信是如何解 决这个难题的？
版本4：史泰因豪斯在《数学万花筒》中的表述：有装有14千克酒的容器，另外有 可装5千克和9千克酒的容器，要把酒平分，该如何办？
版本5：别莱利曼在《趣味儿何学》中表述：一只水桶，可装12杓水，还有两只空 桶，容量分别为9杓和5杓，如何把大水桶的水分成两半？
虽然各个问题的表述不同，但是其木质之都是一样的。解决这一类问题一般有三种 方法：作图法、尝试法和不定方程法。
文献［1］说明了三种手工求解的方法，这对于小规模问题可以解决，但是对于大规模 问题就无能为力了。文献［2］［4］详细解释了如何用作图法解决该类问题，直观简洁。文 献［5］［6］又介绍了如何用算法求解该问题，其中文献［6］是对文献［5］的一种改进。
本质上原问题的最优解就是状态量之间的最短路问题，问题是杏可解就是两个彳、同 状态直接是否联通的问题。这样原问题就转换为一个网络拓扑的问题。
通过参考上述文献，针对问题一，本文采取盲冃搜索算法，搜索各种可能的路径， 一旦得到目标状态量，就停止搜索，这时得到的结果就是问题的最优解。如果程序没有 输出，则说明问题不可解。对于问题二，木文利用不定方程组来初步判定问题是否可解。 问题三，通过试探，发现对于版本四问题的最小步数刚好
13步，达到设计的要求。
三、基本假设
1、 假设每次倒油的时候都没有油漏掉；
2、 假设倒油时三个容器都不会将由留剩余容器壁上;
3、 假设容器都没有损坏