基于盲目搜索算法求解泊松分酒韩信分油问题(10页).docx

《基于盲目搜索算法求解泊松分酒韩信分油问题(10页).docx》由会员分享，可在线阅读，更多相关《基于盲目搜索算法求解泊松分酒韩信分油问题(10页).docx（10页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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

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

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

4、对实现方式给出详细操作步骤。问题二：一般问题:设有个瓶子，每个瓶子最多装酒数量用向量表示为。现在初始各瓶子装酒为。现要实现将各瓶子装酒为。要求不凭借任何其它工具，问能否实现？若能实现，给出实现的方法，并给出充分理由说明是否是最少步数。并对你所使用的模型和算法进行分析说明。问题三：设计一个实例，要求最少完成步数不少于13步。给出从初始状态到目标状态的详细实现步骤。二、问题的分析原问题有很多个版本：版本1：日本分油问题。有一个装满油的8公升容器，另有一个5公升及3公升的空容器各一个，且三个容器都没有刻度，试将此8公升油分成4公升。.版本2：法国著名数学家泊松年轻时研究过的一道题：某人有12品脱美酒

5、，想把一半赠人，但没有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、假设每次都是到空杯子或者将另一一个杯子倒满。四、符号说明符号说明 第个容器的最大容积第个容器的现存的容量第个容器向第个容器倒入的次数第个容器的目标的容量第个容器的初始的容量容器的个数五、模型的建立与求解5.1问题一模型的建立与求解5.1.1模型的建立问题一的模型较为简单。酒瓶的初始状态，最终的目标状态分别是，。中间状态的下一个状态最大可能有种。这样从初始状态开始搜索，直到搜索到目标状态，如果遍历所有

8、可能状态都没有到达目标状态，说明初始状态与目标状态之间并没有联通。遍历过程中对于已经遍历的节点不再遍历，降低算法的复杂度。5.1.2模型的求解由于每一个中间状态节点都最大有12不同的孩子节点，所以算法的整体数据结构为一个十二叉树。对于每一个节点分别计算对应的12种情况，如果状态不存在，就将该节点接入树中。如果已经存在，则不链接该节点，进行下一种情况的判断。其中，树的建立要借助于队列这一个数据结构，借助其将每一个新节点入队、处理。一旦发现目标状态节点，则停止循环，同时将目标节点以及其各个双亲节点入栈，直到初始状态节点。最终再将各个节点出栈，出栈的顺序即为倒酒过程中，各个酒杯的酒量。该十二叉树最底

9、层叶子结点的个数即为可实现最短路径的方案个数。运行程序得到结果分别为：当目标状态为其中一条最短路径为(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,6,1)-(1,4,4,3)-(4,4,4,0)，总共九步。运行结果如下：当目标状态为(3,3,3,3)时，其中的一条最短路径为(12,0,0,0)-(6,0,6,0)-(3,0,6,3)-(3,3,6,0)-(3,3,3,3)，总共四步。运行结果如下：当目标状态为(5,3,2,2)时，没有得到结果说明，无法从初始状态到达目标状态。5.2问

10、题二模型的建立与求解5.2.1 模型的建立分析可知，由于没有刻度，所以需要将杯子倒空或者将另一个杯子倒满。所以每一次杯子内酒量的转换量都是各个杯子的容积或者他们的差值。而且任何一个差值都可以由 的加权和来表示，即 ，其中为整数。由此我们得到系数矩阵（1）其中 可以看作为第杯向第杯倒入的次数。其中矩阵对角线上元素为0。所以，第杯中的剩余容量为。如果每一杯的剩余容量都等于目标容量，则说明问题可解。函数方程为（2）如果方程有整数解，则说明原问题有解。式中如果所有系数的和较小，说明从初始状态到目标状态的最短步数相对较少。具体的最短步数和最短路径可由第一问的算法解得。5.2.2 模型的说明以日本分油问题

11、为例，有一个装满油的8公升容器，另有一个5公升及3公升的空容器各一个，且三个容器都没有刻度，试将此8公升油分成4公升。由于只有三个容器，问题的解可以转化为一个求解二元一次不定方程的解的过程。方程为：（3）其中，。解得：。说明问题可解。利用程序得到最短路径为(8,0,0)-(3,5,0)-(3,2,3)-(6,2,0)-(6,0,2)-(1,5,2)-(1,4,3)-(4,4,0)，总共7步。其中由大杯倒入中杯两次，小杯倒入大杯两次，与得到的系数一致。5.3问题三模型的建立与求解5.3.1 模型的建立通过试探，运用问题二的模型，发现版本4史泰因豪斯在数学万花筒中的表述：有装有14千克酒的容器，另

12、外有可装5千克和9千克酒的容器，要把酒平分的问题最短路径刚好为13步。其对应的不定方程为（4）最短路径为(14,0,0)-(5,9,0)-(5,4,5)-(10,4,0)-(10,0,4)-(1,9,4)-(1,8,5)-(6,8,0)-(6,3,5)-(11,3,0)-(11,0,3)-(2,9,3)-(2,7,5)-(7,7,0)六、模型的检验与结果分析利用版本16的不同问题，对于模型所对应的程序进行了运行都得到了较好的结果，说明模型能够很好的适应这类小规模的问题，程序算法具有较好的适应性。并且对所求最短路径进行检验，发现每条路径都是准确无误的。七、模型的改进虽然本模型对于上述问题得到了较

13、好的结果，但是不难发现本质上都属于小规模问题。如果问题的规模继续扩大，算法的空间复杂度和时间复杂度增长迅速，使得问题很难解决。在这里本文提出两种改进方法：1、 可以首先将一些杯子合并成为一个系统，减少杯子的总量，先解决系统之间的问题，然后在解决系统内部的问题。2、 每一个问题的可能的状态总数是确定的，可以利用模型二，首先剔除掉不连通的点，建立一个网络拓扑图，利用蚁群算法等智能算法得到相对最优的解。八、参考文献1张安军. 韩信立马分油问题的三种策略J. 中学数学杂志:初中版, 2016(1).2郭俊杰, 毕双艳, 雷冠丽. 分油问题的网络最优化解法J. 吉林大学学报信息科学版, 1989(1):

14、33-38.3任永胜. 对“分油问题”的探微J. 山西师范大学学报(自然科学版), 2014(s2):32-34.4 彭世康, 李春梅, 彭金瑾. 完整状态转移图法求三桶分油问题全部解J. 数学通报, 2015(1):56-60.5詹明清, 詹横空. 泊松分酒问题的一般解J. 电脑, 1996(9)6谭亮辉. 再谈泊松分酒问题的解法J. 电脑, 1997(1).附录：#include #include #include #define Method 12#define OK 1#define TRUE 1#define FLASE 0#define ERROR 0#define INFESIB

15、LE#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;struct state *childMethod;state,*pstate;typedef pstate SElemType;typedef int Status;typedef

16、struct SElemType *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; pnew-data2=c;pnew-data3=d; / pnew-pro=pro; for(int i=0;ichildi=NULL; return pnew; typedef s

17、truct pstate *base; /队列的基址 int front; /队首指针 int rear; /队尾指针SqQueue;Status InitQueue ( SqQueue &q ) /初始化空循环队列 q q.base=(QElemType *)malloc( sizeof(QElemType)* QUEUE_MAXSIZE); /分配空间 if (!q.base) exit(OVERFLOW);/内存分配失败退出程序 q.front =q.rear=0; /置空队列 return OK; /InitQueue;Status EnQueue(SqQueue &q, QElemT

18、ype e)/向循环队列 q 的队尾加入一个元素 e if (q.rear+1) % QUEUE_MAXSIZE=q.front) return ERROR ; /队满则上溢，无法再入队 q.base q.rear = e; /新元素e入队 q.rear = (q.rear + 1) % QUEUE_MAXSIZE; /指针后移 return OK; / EnQueue;Status DeQueue ( SqQueue &q, QElemType &e) /若队列不空，删除循环队列q的队头元素， /由 e 返回其值，并返回OK if (q.front =q.rear) return ERROR

19、;/队列空 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.base) exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE;return OK;Status GetTop(SqStack S,SElemType &e) /若栈不为空，

20、则用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.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if (!S.base) exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREM

21、ENT;*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 d,int existence1804,int existsize)int i;for(i=0;iexistsize;i+)if(existencei0=a&existencei1=b&existencei2=c)return 1;return 0;Stat

22、us addexist(int a,int b,int c,int d,int existence1804,int &existsize)existenceexistsize0=a;existenceexistsize1=b;existenceexistsize2=c;existenceexistsize3=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,tem

23、p4,changenum=0;InitQueue(Q);EnQueue(Q,root);while(Q.front!=Q.rear)DeQueue(Q,e);changenum=0;next=0;for(i=0;i4;i+)for(j=0;j4;j+)if(i!=j)for(k=0;kdataj)datai?(volumej-e-dataj):e-datai;tempi=-tempj;if(tempi=0)continue;if(!judgeexist(e-data0+temp0,e-data1+temp1,e-data2+temp2,e-data3+temp3,existence,exist

24、size)e-childnext=newState(e,e-data0+temp0,e-data1+temp1,e-data2+temp2,e-data3+temp3);addexist(e-data0+temp0,e-data1+temp1,e-data2+temp2,e-data3+temp3,existence,existsize);EnQueue(Q,e-childnext);changenum+;if(judgeexist(last0,last1,last2,last3,existence,existsize)return e-childnext;next+;return NULL;

25、 Status show(pstate final)pstate temp;SqStack s;InitStack(s); temp=final;if(!final)printf(没有可行解n);return 0;elsewhile(temp)Push(s,temp);temp=temp-parent;while(s.base!=s.top)Pop(s,temp);printf(%d,%d,%d,%d)n,temp-data0,temp-data1,temp-data2,temp-data3);return 0; int main()pstate root,final;root=newState(NULL,13,0,0,0);int existence1804;int existsize=0;int volume4=16,14,6,3;int last4=6,5,2,0;final=BuildTree(root,existence,existsize,volume,last);show(final);return 0;目录一、问题重述2二、问题的分析2三、基本假设3四、符号说明3五、模型的建立与求解35.1问题一模型的建立与求解35.2问题二模型的建立与求解45.3问题三模型的建立与求解5六、模型的检验与结果分析5七、模型的改进5八、参考文献6附录：7