基于盲目搜索算法求解泊松分酒韩信分油问题.doc

《基于盲目搜索算法求解泊松分酒韩信分油问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、题目：基于盲目搜索算法求解泊松分酒问题【摘要】分酒问题的描述在历史上有很多版本，如泊松分酒、韩信分油等。但是它们的本质都是相同的，无论是中间的转换过程中的各个杯子的容量，还是目标和初始的容量，都可以看作是网络中的一个节点。而两种状态量之间是否可以进行转换可以看作是网络中两个节点是否连通。由此原问题的是否可解、最少步数、多少种方式可以转化为网络中两个节点是否连通、最短路径、最短路径的条数的问题。对于问题一，利用盲目搜索算法，由起始点出发进行搜索，如果找到了目标节点，则停止搜索，输出结果。如果没有找到，则说明原问题不可解。对于问

2、题二，本文通过研究各个状态之间的转换关系，列写方程，通过判断方程是否有整数解来判定原问题是否可解。并通过系数的求和来判断该解是否是最优解。对于问题三，通过研究各个版本的分酒问题，发现史泰因豪斯在《数学万花筒》中的表述：有装有14千克酒的容器，另外有可装5千克和9千克酒的容器，要把酒平分的问题即可满足要求。并利用该问题对模型进行了检验。最终，本文对于更大规模的分酒问题提出了自己的想法和改进思路，如利用模型二，首先剔除掉不连通的点，建立一个网络拓扑图，利用蚁群算法等智能算法，求解最短路问题，得到相对最优的解。关键词：泊松分酒盲目

3、搜索不定方程蚁群算法13一、问题重述分酒问题是一个十分著名的智力问题。在历史上这个问题有很多版本：泊松分酒、韩信分油等。他们的原问题可以表述为三个容积不等的瓶子，如何实现将酒量等分。显然这个问题的规模较小，可以通过人工来解决，然而当问题的规模变大，手工就变得无能为力了。这就要求我们建立合适的模型来描述更大规模和一般性的问题，并利用合适的算法求解模型。请尝试从基本问题出发建立数学模型解决以下问题：问题一：现有一只装满12斤酒的瓶子和三只分别装10斤、6斤和3斤酒的空瓶，如何才能将这12斤酒分成三等份。如果进行四等份呢，结果如何

4、？如果4个瓶子分别要求装5斤、3斤、2斤、2斤，又能否实现？试建立数学模型并设计算法，求最少经过多少步操作完成，且有多少种方式可采用最少步数完成。要求对实现方式给出详细操作步骤。问题二：一般问题:设有个瓶子，每个瓶子最多装酒数量用向量表示为。现在初始各瓶子装酒为。现要实现将各瓶子装酒为。要求不凭借任何其它工具，问能否实现？若能实现，给出实现的方法，并给出充分理由说明是否是最少步数。并对你所使用的模型和算法进行分析说明。问题三：设计一个实例，要求最少完成步数不少于13步。给出从初始状态到目标状态的详细实现步骤。二、问题的分析原

5、问题有很多个版本：版本1：日本分油问题。有一个装满油的8公升容器，另有一个5公升及3公升的空容器各一个，且三个容器都没有刻度，试将此8公升油分成4公升。.版本2：法国著名数学家泊松年轻时研究过的一道题：某人有12品脱美酒，想把一半赠人，但没有6品脱的容器，而只有一个8品脱和一个5品脱的容器，问怎样才能把6品脱的酒倒入8品脱的容器中。版本3：我国的韩信分油问题：韩信遇到两个路人争执不下，原因是两人有装满10斤的油篓和两个3斤、7斤的空油篓，无法平均分出两份，每份5斤油。韩信是如何解决这个难题的？版本4：史泰因豪斯在《数学万花筒

6、》中的表述：有装有14千克酒的容器，另外有可装5千克和9千克酒的容器，要把酒平分，该如何办？版本5：别莱利曼在《趣味几何学》中表述：一只水桶，可装12杓水，还有两只空桶，容量分别为9杓和5杓，如何把大水桶的水分成两半？虽然各个问题的表述不同，但是其本质之都是一样的。解决这一类问题一般有三种方法：作图法、尝试法和不定方程法。文献[1]说明了三种手工求解的方法，这对于小规模问题可以解决，但是对于大规模问题就无能为力了。文献[2][4]详细解释了如何用作图法解决该类问题，直观简洁。文献[5][6]又介绍了如何用算法求解该问题，其中

7、文献[6]是对文献[5]的一种改进。本质上原问题的最优解就是状态量之间的最短路问题，问题是否可解就是两个不同状态直接是否联通的问题。这样原问题就转换为一个网络拓扑的问题。通过参考上述文献，针对问题一，本文采取盲目搜索算法，搜索各种可能的路径，一旦得到目标状态量，就停止搜索，这时得到的结果就是问题的最优解。如果程序没有输出，则说明问题不可解。对于问题二，本文利用不定方程组来初步判定问题是否可解。问题三，通过试探，发现对于版本四问题的最小步数刚好13步，达到设计的要求。13三、基本假设1、假设每次倒油的时候都没有油漏掉；2、假设

8、倒油时三个容器都不会将由留剩余容器壁上；3、假设容器都没有损坏；4、假设每次都是到空杯子或者将另一一个杯子倒满。四、符号说明符号说明第个容器的最大容积第个容器的现存的容量第个容器向第个容器倒入的次数第个容器的目标的容量第个容器的初始的容量容器的个数五、模型的建立与求解5.1问题一模型的建立