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

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

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

3、酒、 韩信分油等。他们的原问题可以表述为三个容积不等的瓶子，如何实现将酒量等分。显 然这个问题的规模较小，可以通过人工来解决，然而当问题的规模变大，手工就变得无 能为力了。这就要求我们建立合适的模型来描述更大规模和一般性的问题，并利用合适 的算法求解模型。请尝试从基本问题出发建立数学模型解决以下问题：问题一：现有一只装满12斤酒的瓶子和三只分别装10斤、6斤和3斤酒的空瓶， 如何才能将这12斤酒分成三等份。如果进行四等份呢，结果如何？如果4个瓶子分别要求装5斤、3斤、2斤、2斤，又能否实现？试建立数学模型并设计算法，求最少经过 多少步操作完成，且有多少种方式可采用最少步数完成。要求对实现方式给

4、出详细操作 步骤。问题二：一般问题：设有n个瓶子，每个瓶子最多装酒数量用向量表示为(X1,X2川l，Xn)。现在初始各瓶子装酒为(Xi0,X20,|,Xn0)。现要实现将各瓶子装酒为(dl,d2|,dn)。要求不凭借任何其它工具，问能否实现？若能实现，给出实现的方法， 并给出充分理由说明是否是最少步数。并对你所使用的模型和算法进行分析说明。问题三：设计一个实例，要求最少完成步数不少于13步。给出从初始状态到目标状态的详细实现步骤。问题的分析原问题有很多个版本：版本1:日本分油问题。有一个装满油的 8公升容器，另有一个5公升及3公升的 空容器各一个，且三个容器都没有刻度，试将此 8公升油分成4公

5、升。.版本2:法国著名数学家泊松年轻时研究过的一道题：某人有12品脱美酒，想把一半赠人，但没有 6品脱的容器，而只有一个8品脱和 一个5品脱的容器，问怎样才能把6品脱的酒倒入8品脱的容器中。版本3:我国的韩信分油问题：韩信遇到两个路人争执不下，原因是两人有装满10斤的油篓和两个3斤、7斤的空油篓，无法平均分出两份，每份 5斤油。韩信是如何解 决这个难题的？版本4:史泰因豪斯在数学万花筒中的表述：有装有 14千克酒的容器，另外有 可装5千克和9千克酒的容器，要把洒平分，该如何办？版本5:别莱利曼在趣味几何学中表述：一只水桶，可装 12杓水，还有两只空桶，容量分别为9杓和5杓，如何把大水桶的水分成

6、两半？虽然各个问题的表述不同，但是其本质之都是一样的。解决这一类问题一般有三种 方法：作图法、尝试法和不定方程法。文献1说明了三种手工求解的方法，这对于小规模问题可以解决，但是对于大规 模问题就无能为力了。文献24详细解释了如何用作图法解决该类问题，直观简洁。 文献56又介绍了如何用算法求解该问题，其中文献6是对文献5的一种改进。本质上原问题的最优解就是状态量之间的最短路问题，问题是否可解就是两个不同状态直接是否联通的问题。这样原问题就转换为一个网络拓扑的问题。通过参考上述文献，针对问题一，本文采取盲目搜索算法，搜索各种可能的路径， 一旦得到目标状态量，就停止搜索，这时得到的结果就是问题的最优

7、解。如果程序没有 输出，则说明问题不可解。对于问题二，本文利用不定方程组来初步判定问题是否可解。 问题三，通过试探，发现对于版本四问题的最小步数刚好13步，达到设计的要求。三、基本假设1、假设每次倒油的时候都没有油漏掉；2、假设倒油时三个容器都不会将由留剩余容器壁上;3、假设容器都没有损坏；4、假设每次都是到空杯子或者将另一一个杯子倒满。四、符号说明符号Vi第i个容器的最大容积Xi第i个容器的现存的容量Cj第i个容器向第j个容器倒入的次数Di第i个容器的目标的容量A第i个容器的初始的容量N容器的个数五、模型的建立与求解5.1 问题一模型的建立与求解5.1.1 模型的建立问题一的模型较为简单。酒

8、瓶的初始状态(12, 0, 0, 0)最终的目标状态分别是(4, 4, 4,0), (3,3,3,3) , (5,3,2,2)。中间状态(X1,X2,X3,X4)的下一个状态最大可能有 席=12种。这样从初始状态开始搜索，直到搜索到目标状态，如果遍历所有可能状态 都没有到达目标状态，说明初始状态与目标状态之间并没有联通。遍历过程中对于已经 遍历的节点不再遍历，降低算法的复杂度。5.1.2 模型的求解由于每一个中间状态节点都最大有12不同的孩子节点，所以算法的整体数据结构为一个十二叉树。对于每一个节点分别计算对应的12种情况，如果状态不存在，就将该节点接入树中。如果已经存在，则不链接该节点，进行

9、下一种情况的判断。其中，树 的建立要借助于队列这一个数据结构，借助其将每一个新节点入队、处理。一旦发现目标状态节点，则停止循环，同时将目标节点以及其各个双亲节点入栈， 直到初始状态节点。最终再将各个节点出栈，出栈的顺序即为倒洒过程中，各个酒杯的 酒量。该十二叉树最底层叶子结点的个数即为可实现最短路径的方案个数。运行程序得到结果分别为：当目标状态为 (4,4,4,0) 其中一条最短路径为(12,0,0,0)->(2,10,0,0)->(2,4,6,0)->(2,1,6,3->(8,1,0,3)->(11,1,0,0)->(1,10,0,1)->(1,4,

10、6,1)->(1,4,4,3)->(4,4,4,0),总共九步。运行结果如下:y/Au- 11 11 %lz J 50 3 3 J- J 5 12 0 nv L> J > o o o 7 J 1 J 5 6- o , 6 4 i- 翻 事 1 -nW dJ* VI f Tr J 11 Ai JI 1x 1 1- 1± 'MH on. 3 T. 3- 3 T Ir 12228 11111 4-一条最短路径为 ，总共四步。当目标状态为(3,3,3,3) 时，其中的(12,0,0,0)->(6,0,6,0)->(3,0,6,3)->(3,3

11、,6,0)->(3,3,3,3)运行结果如下：u- 1-0303当目标状态为(5,3,2,2)时，没有得到结果说明，无法从初始状态到达目标状态。5.2 问题二模型的建立与求解5.2.1 模型的建立分析可知，由于没有刻度，所以需要将杯子倒空或者将另一个杯子倒满。所以每一次杯子内酒量的转换量都是各个杯子的容积或者他们的差值。而且任何一个差值都可以N由Vi的加权和来表示，即£ CiVi ,其中Ci为整数。由此我们得到系数矩阵 i 1C11 HI Cin(1)C_：、：+Fl<Cni HI Cnn j其中Cj可以看作为第i杯向第j杯倒入的次数。其中矩阵对角线上元素为0。所以,NN

12、第i杯中的剩余容量为ACjVj -Z CjVi。如果每一杯的剩余容量都等于目标容量, j 1j 1则说明问题可解。函数方程为NNA 十£ CjiVj -z CijVi =Di(i =1,2,., N)(2)j 1j 1N N如果方程有整数解，则说明原问题有解。式中如果所有系数的和zz Cj较小，说ij j J明从初始状态到目标状态的最短步数相对较少。具体的最短步数和最短路径可由第一问 的算法解得。5.2.2 模型的说明以日本分油问题为例，有一个装满油的 8公升容器，另有一个5公升及3公升的空容器各一个，且三个容器都没有刻度，试将此 8公升油分成4公升。由于只有三个容器，问题的解可以转

13、化为一个求解二元一次不定方程的解的过程。方程为：C1V1 C2V2 =V3/2(3)其中，V1=5 ,V2=3 ,V3=8。解得：Ci=C2= 2。说明问题可解。利用程序得到最短路径为(8。0)->(3,5,0)->(3,2,3)->(6,2,0)->(6。2)->(1,5,2)->(1,4,3)->(4,4,0)，总共7步。其中由大杯倒入中杯两次，小杯倒入大杯两次，与得到的系数一致。5.3 问题三模型的建立与求解5.3.1 模型的建立通过试探，运用问题二的模型，发现版本 4史泰因豪斯在数学万花筒中的 表述：有装有14千克酒的容器，另外有可装 5千克和

14、9千克酒的容器，要把酒平分的 问题最短路径刚好为13步。其对应的不定方程为9c#5C2=7(4)最短路径为(14,0,0)->(5,9,0)->(5,4,5)->(10,4,0)->(10。4)->(1,9,4)->(1,8,5)->(6,8,0)-> (6,3,5)->(1130)->(11,0,3)->(2,9,3)->(2,7,5)->(7,7,0)六、模型的检验与结果分析利用版本16的不同问题，对于模型所对应的程序进行了运行都得到了较好的结果， 说明模型能够很好的适应这类小规模的问题，程序算法具有较好的适应性

15、。并且对所求 最短路径进行检验，发现每条路径都是准确无误的。七、模型的改进虽然本模型对于上述问题得到了较好的结果，但是不难发现本质上都属于小规模问 题。如果问题的规模继续扩大，算法的空间复杂度和时间复杂度增长迅速，使得问题很 难解决。在这里本文提出两种改进方法：1、可以首先将一些杯子合并成为一个系统， 减少杯子的总量，先解决系统之间的问 题，然后在解决系统内部的问题。2、每一个问题的可能的状态总数是确定的， 可以利用模型二，首先剔除掉不连通的 点，建立一个网络拓扑图，利用蚁群算法等智能算法得到相对最优的解。八、参考文献1张安军.韩信立马分油问题的三种策略J.中学数学杂志：初中版，2016(1)

16、.2郭俊杰，毕双艳，雷冠丽.分油问题的网络最优化解法J.吉林大学学报信 息科学版，1989(1):33-38.3任永胜.对“分油问题”的探微 J.山西师范大学学报(自然科学版),2014(s2):32-34.4彭世康，李春梅，彭金瑾.完整状态转移图法求三桶分油问题全部解J.数学通报，2015(1):56-60.5詹明清，詹横空.泊松分酒问题的一般解J.电脑，1996(9)6谭亮辉.再谈泊松分酒问题的解法J.电脑，1997(1).附录：#include <stdio.h>#include <stdlib.h>#include <malloc.h># defin

17、e Method 12# define OK 1# define TRUE 1# define FLASE 0# define ERROR 0# define INFESIBLE# define OVERFLOW -2# define STACK_INIT_SIZE 100# define STACKINCREMENT 10# define SElemType pstate#define QUEUE_MAXSIZE 500 / 最大队列长度#define QElemType pstatetypedef struct stateint data4;struct state *parent;str

18、uct state *childMethod;state,*pstate;typedef pstate SElemType;typedef int Status;typedef structSElemType *base;SElemType *top;int stacksize;SqStack;state *newState(state *parent,int a,int b,int c,int d)state *pnew=(state *)malloc(sizeof(state);pnew->parent=parent;pnew->data0=a;pnew->data1=b

19、;pnew->data2=c;pnew->data3=d;/ pnew->pro=pro;for(int i=0;i<Method;i+)pnew->childi=NULL;return pnew;typedef struct pstate*base; /队列的基址intfront; /队首指针intrear; /队尾指针SqQueue;Status InitQueue ( SqQueue &q ) /初始化空循环队列 q q.base=(QElemType *)malloc( sizeof(QElemType)* QUEUE_MAXSIZE);/分配空间

20、if (!q.base) exit(OVERFLOW);/内存分配失败退出程序q.front =q.rear=0; /置空队歹!Jreturn OK; /InitQueue;Status EnQueue(SqQueue &q, QElemType e)/向循环队列q的队尾加入一个元素eif (q.rear+1) % QUEUE_MAXSIZE=q.front)return ERROR ; /队满则上溢，无法再入队q.base q.rear = e; /新元素 e 入队q.rear = (q.rear + 1) % QUEUE_MAXSIZE; / 指针后移return OK;/ EnQ

21、ueue;Status DeQueue ( SqQueue &q, QElemType &e)/若队列不空，删除循环队列q的队头元素，/ 由e返回其值，并返回OKif (q.front =q.rear) return ERROR;/队列空e = q.base q.front;q.front=(q.front+1) % QUEUE_MAXSIZE ;return OK;/ DeQueueStatus InitStack(SqStack &S)S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S

22、.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE; return OK;Status GetTop(SqStack S,SElemType &e) /若栈不为空，则用e返回S的栈顶元素if(S.top=S.base)return ERROR;e=*(S.top-1);return OK;Status Push(SqStack &S,SElemType e)插入元素e为新的栈顶元素if(S.top-S.base>=S.stacksize)S.base=(SElemType*)realloc(S.bas

23、e,(S.stacksize+STACKINCREMENT) *sizeof(SElemType);if (!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Pop(SqStack &S,SElemType &e)/若栈不空，则删除S的栈顶元素并返回eif(S.top=S.base)return ERROR;e=*-S.top;return OK;Status judgeexist(int a,int b,int c,int

24、 d,int existence1804,int existsize) int i;for(i=0;i<existsize;i+)if(existencei0=a&&existencei1=b&&existencei2=c) return 1; return 0;Status addexist(int a,int b,int c,int d,int existence1804,int &existsize)existenceexistsize0=a;existenceexistsize1=b;existenceexistsize2=c;existe

25、nceexistsize3=d;existsize+=1;return 0;pstate BuildTree(pstate root,int existence1804,int &existsize,int* volume,int* last)SqQueue Q;pstate e;int i,j,k,next,temp4,changenum=0;InitQueue(Q);EnQueue(Q,root);while(Q.front!=Q.rear)DeQueue(Q,e);changenum=0;next=0;for(i=0;i<4;i+)for(j=0;j<4;j+)if(

26、i!=j)for(k=0;k<4;k+) tempk=0;tempj=(volumej-e->dataj)<e->datai?(volumej-e->dataj):e->data i;tempi=-tempj;if(tempi=0) continue;if(!judgeexist(e->data0+temp0,e->data1+temp1,e->data2+temp2, e->data3+temp3,existence,existsize)e->childnext=newState(e,e->data0+temp0,e->data1+temp1,e->data 2+temp2,e->data3+temp3);addexist(e