基于盲目搜索算法求解泊松分酒韓信分油問(wèn)題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上題目： 基于盲目搜索算法求解泊松分酒問(wèn)題 【摘 要】分酒問(wèn)題的描述在歷史上有很多版本，如泊松分酒、韓信分油等。但是它們的本質(zhì)都是相同的，無(wú)論是中間的轉(zhuǎn)換過(guò)程中的各個(gè)杯子的容量，還是目標(biāo)和初始的容量，都可以看作是網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)。而兩種狀態(tài)量之間是否可以進(jìn)行轉(zhuǎn)換可以看作是網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)是否連通。由此原問(wèn)題的是否可解、最少步數(shù)、多少種方式可以轉(zhuǎn)化為網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)是否連通、最短路徑、最短路徑的條數(shù)的問(wèn)題。對(duì)于問(wèn)題一，利用盲目搜索算法，由起始點(diǎn)出發(fā)進(jìn)行搜索，如果找到了目標(biāo)節(jié)點(diǎn)，則停止搜索，輸出結(jié)果。如果沒(méi)有找到，則說(shuō)明原問(wèn)題不可解。對(duì)于問(wèn)題二，本文通過(guò)研究各個(gè)狀態(tài)之間的轉(zhuǎn)換關(guān)

2、系，列寫(xiě)方程，通過(guò)判斷方程是否有整數(shù)解來(lái)判定原問(wèn)題是否可解。并通過(guò)系數(shù)的求和來(lái)判斷該解是否是最優(yōu)解。對(duì)于問(wèn)題三，通過(guò)研究各個(gè)版本的分酒問(wèn)題，發(fā)現(xiàn)史泰因豪斯在數(shù)學(xué)萬(wàn)花筒中的表述：有裝有14千克酒的容器，另外有可裝5千克和9千克酒的容器，要把酒平分的問(wèn)題即可滿足要求。并利用該問(wèn)題對(duì)模型進(jìn)行了檢驗(yàn)。最終，本文對(duì)于更大規(guī)模的分酒問(wèn)題提出了自己的想法和改進(jìn)思路，如利用模型二，首先剔除掉不連通的點(diǎn)，建立一個(gè)網(wǎng)絡(luò)拓?fù)鋱D，利用蟻群算法等智能算法，求解最短路問(wèn)題，得到相對(duì)最優(yōu)的解。關(guān)鍵詞：泊松分酒 盲目搜索 不定方程 蟻群算法一、問(wèn)題重述分酒問(wèn)題是一個(gè)十分著名的智力問(wèn)題。在歷史上這個(gè)問(wèn)題有很多版本：泊松分酒、韓

3、信分油等。他們的原問(wèn)題可以表述為三個(gè)容積不等的瓶子，如何實(shí)現(xiàn)將酒量等分。顯然這個(gè)問(wèn)題的規(guī)模較小，可以通過(guò)人工來(lái)解決，然而當(dāng)問(wèn)題的規(guī)模變大，手工就變得無(wú)能為力了。這就要求我們建立合適的模型來(lái)描述更大規(guī)模和一般性的問(wèn)題，并利用合適的算法求解模型。請(qǐng)嘗試從基本問(wèn)題出發(fā)建立數(shù)學(xué)模型解決以下問(wèn)題：?jiǎn)栴}一：現(xiàn)有一只裝滿12斤酒的瓶子和三只分別裝10斤、6斤和3斤酒的空瓶，如何才能將這12斤酒分成三等份。如果進(jìn)行四等份呢，結(jié)果如何？如果4個(gè)瓶子分別要求裝5斤、3斤、2斤、2斤，又能否實(shí)現(xiàn)？試建立數(shù)學(xué)模型并設(shè)計(jì)算法，求最少經(jīng)過(guò)多少步操作完成，且有多少種方式可采用最少步數(shù)完成。要求對(duì)實(shí)現(xiàn)方式給出詳細(xì)操作步驟。問(wèn)

4、題二：一般問(wèn)題:設(shè)有個(gè)瓶子，每個(gè)瓶子最多裝酒數(shù)量用向量表示為?，F(xiàn)在初始各瓶子裝酒為?，F(xiàn)要實(shí)現(xiàn)將各瓶子裝酒為。要求不憑借任何其它工具，問(wèn)能否實(shí)現(xiàn)？若能實(shí)現(xiàn)，給出實(shí)現(xiàn)的方法，并給出充分理由說(shuō)明是否是最少步數(shù)。并對(duì)你所使用的模型和算法進(jìn)行分析說(shuō)明。問(wèn)題三：設(shè)計(jì)一個(gè)實(shí)例，要求最少完成步數(shù)不少于13步。給出從初始狀態(tài)到目標(biāo)狀態(tài)的詳細(xì)實(shí)現(xiàn)步驟。二、問(wèn)題的分析原問(wèn)題有很多個(gè)版本：版本1：日本分油問(wèn)題。有一個(gè)裝滿油的8公升容器，另有一個(gè)5公升及3公升的空容器各一個(gè)，且三個(gè)容器都沒(méi)有刻度，試將此8公升油分成4公升。.版本2：法國(guó)著名數(shù)學(xué)家泊松年輕時(shí)研究過(guò)的一道題：某人有12品脫美酒，想把一半贈(zèng)人，但沒(méi)有6品脫的

5、容器，而只有一個(gè)8品脫和一個(gè)5品脫的容器，問(wèn)怎樣才能把6品脫的酒倒入8品脫的容器中。版本3：我國(guó)的韓信分油問(wèn)題：韓信遇到兩個(gè)路人爭(zhēng)執(zhí)不下，原因是兩人有裝滿10斤的油簍和兩個(gè)3斤、7斤的空油簍，無(wú)法平均分出兩份，每份5斤油。韓信是如何解決這個(gè)難題的？版本4：史泰因豪斯在數(shù)學(xué)萬(wàn)花筒中的表述：有裝有14千克酒的容器，另外有可裝5千克和9千克酒的容器，要把酒平分，該如何辦？版本5：別萊利曼在趣味幾何學(xué)中表述：一只水桶，可裝12杓水，還有兩只空桶，容量分別為9杓和5杓，如何把大水桶的水分成兩半？雖然各個(gè)問(wèn)題的表述不同，但是其本質(zhì)之都是一樣的。解決這一類問(wèn)題一般有三種方法：作圖法、嘗試法和不定方程法。文獻(xiàn)

6、1說(shuō)明了三種手工求解的方法，這對(duì)于小規(guī)模問(wèn)題可以解決，但是對(duì)于大規(guī)模問(wèn)題就無(wú)能為力了。文獻(xiàn)24詳細(xì)解釋了如何用作圖法解決該類問(wèn)題，直觀簡(jiǎn)潔。文獻(xiàn)56又介紹了如何用算法求解該問(wèn)題，其中文獻(xiàn)6是對(duì)文獻(xiàn)5的一種改進(jìn)。本質(zhì)上原問(wèn)題的最優(yōu)解就是狀態(tài)量之間的最短路問(wèn)題，問(wèn)題是否可解就是兩個(gè)不同狀態(tài)直接是否聯(lián)通的問(wèn)題。這樣原問(wèn)題就轉(zhuǎn)換為一個(gè)網(wǎng)絡(luò)拓?fù)涞膯?wèn)題。通過(guò)參考上述文獻(xiàn)，針對(duì)問(wèn)題一，本文采取盲目搜索算法，搜索各種可能的路徑，一旦得到目標(biāo)狀態(tài)量，就停止搜索，這時(shí)得到的結(jié)果就是問(wèn)題的最優(yōu)解。如果程序沒(méi)有輸出，則說(shuō)明問(wèn)題不可解。對(duì)于問(wèn)題二，本文利用不定方程組來(lái)初步判定問(wèn)題是否可解。問(wèn)題三，通過(guò)試探，發(fā)現(xiàn)對(duì)于版本

7、四問(wèn)題的最小步數(shù)剛好13步，達(dá)到設(shè)計(jì)的要求。三、基本假設(shè)1、假設(shè)每次倒油的時(shí)候都沒(méi)有油漏掉；2、假設(shè)倒油時(shí)三個(gè)容器都不會(huì)將由留剩余容器壁上；3、假設(shè)容器都沒(méi)有損壞；4、假設(shè)每次都是到空杯子或者將另一一個(gè)杯子倒?jié)M。四、符號(hào)說(shuō)明符號(hào)說(shuō)明 第個(gè)容器的最大容積第個(gè)容器的現(xiàn)存的容量第個(gè)容器向第個(gè)容器倒入的次數(shù)第個(gè)容器的目標(biāo)的容量第個(gè)容器的初始的容量容器的個(gè)數(shù)五、模型的建立與求解5.1問(wèn)題一模型的建立與求解5.1.1模型的建立問(wèn)題一的模型較為簡(jiǎn)單。酒瓶的初始狀態(tài)，最終的目標(biāo)狀態(tài)分別是，。中間狀態(tài)的下一個(gè)狀態(tài)最大可能有種。這樣從初始狀態(tài)開(kāi)始搜索，直到搜索到目標(biāo)狀態(tài)，如果遍歷所有可能狀態(tài)都沒(méi)有到達(dá)目標(biāo)狀態(tài)，說(shuō)

8、明初始狀態(tài)與目標(biāo)狀態(tài)之間并沒(méi)有聯(lián)通。遍歷過(guò)程中對(duì)于已經(jīng)遍歷的節(jié)點(diǎn)不再遍歷，降低算法的復(fù)雜度。5.1.2模型的求解由于每一個(gè)中間狀態(tài)節(jié)點(diǎn)都最大有12不同的孩子節(jié)點(diǎn)，所以算法的整體數(shù)據(jù)結(jié)構(gòu)為一個(gè)十二叉樹(shù)。對(duì)于每一個(gè)節(jié)點(diǎn)分別計(jì)算對(duì)應(yīng)的12種情況，如果狀態(tài)不存在，就將該節(jié)點(diǎn)接入樹(shù)中。如果已經(jīng)存在，則不鏈接該節(jié)點(diǎn)，進(jìn)行下一種情況的判斷。其中，樹(shù)的建立要借助于隊(duì)列這一個(gè)數(shù)據(jù)結(jié)構(gòu)，借助其將每一個(gè)新節(jié)點(diǎn)入隊(duì)、處理。一旦發(fā)現(xiàn)目標(biāo)狀態(tài)節(jié)點(diǎn)，則停止循環(huán)，同時(shí)將目標(biāo)節(jié)點(diǎn)以及其各個(gè)雙親節(jié)點(diǎn)入棧，直到初始狀態(tài)節(jié)點(diǎn)。最終再將各個(gè)節(jié)點(diǎn)出棧，出棧的順序即為倒酒過(guò)程中，各個(gè)酒杯的酒量。該十二叉樹(shù)最底層葉子結(jié)點(diǎn)的個(gè)數(shù)即為可實(shí)現(xiàn)最短

9、路徑的方案?jìng)€(gè)數(shù)。運(yùn)行程序得到結(jié)果分別為：當(dāng)目標(biāo)狀態(tài)為其中一條最短路徑為(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)，專心-專注-專業(yè)總共九步。運(yùn)行結(jié)果如下：當(dāng)目標(biāo)狀態(tài)為(3,3,3,3)時(shí)，其中的一條最短路徑為(12,0,0,0)->(6,0,6,0)->(3,0,6,3)->(3,3,6,0)->(3,3,3,3)，總共四步。運(yùn)行結(jié)果如下

10、：當(dāng)目標(biāo)狀態(tài)為(5,3,2,2)時(shí)，沒(méi)有得到結(jié)果說(shuō)明，無(wú)法從初始狀態(tài)到達(dá)目標(biāo)狀態(tài)。5.2問(wèn)題二模型的建立與求解5.2.1 模型的建立分析可知，由于沒(méi)有刻度，所以需要將杯子倒空或者將另一個(gè)杯子倒?jié)M。所以每一次杯子內(nèi)酒量的轉(zhuǎn)換量都是各個(gè)杯子的容積或者他們的差值。而且任何一個(gè)差值都可以由 的加權(quán)和來(lái)表示，即 ，其中為整數(shù)。由此我們得到系數(shù)矩陣（1）其中 可以看作為第杯向第杯倒入的次數(shù)。其中矩陣對(duì)角線上元素為0。所以，第杯中的剩余容量為。如果每一杯的剩余容量都等于目標(biāo)容量，則說(shuō)明問(wèn)題可解。函數(shù)方程為（2）如果方程有整數(shù)解，則說(shuō)明原問(wèn)題有解。式中如果所有系數(shù)的和較小，說(shuō)明從初始狀態(tài)到目標(biāo)狀態(tài)的最短步數(shù)相

11、對(duì)較少。具體的最短步數(shù)和最短路徑可由第一問(wèn)的算法解得。5.2.2 模型的說(shuō)明以日本分油問(wèn)題為例，有一個(gè)裝滿油的8公升容器，另有一個(gè)5公升及3公升的空容器各一個(gè)，且三個(gè)容器都沒(méi)有刻度，試將此8公升油分成4公升。由于只有三個(gè)容器，問(wèn)題的解可以轉(zhuǎn)化為一個(gè)求解二元一次不定方程的解的過(guò)程。方程為：（3）其中，。解得：。說(shuō)明問(wèn)題可解。利用程序得到最短路徑為(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步。其中由大杯倒入中杯兩次，小杯倒入大杯兩次，與得到的系數(shù)一致。

12、5.3問(wèn)題三模型的建立與求解5.3.1 模型的建立通過(guò)試探，運(yùn)用問(wèn)題二的模型，發(fā)現(xiàn)版本4史泰因豪斯在數(shù)學(xué)萬(wàn)花筒中的表述：有裝有14千克酒的容器，另外有可裝5千克和9千克酒的容器，要把酒平分的問(wèn)題最短路徑剛好為13步。其對(duì)應(yīng)的不定方程為（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)六、模型的檢驗(yàn)

13、與結(jié)果分析利用版本16的不同問(wèn)題，對(duì)于模型所對(duì)應(yīng)的程序進(jìn)行了運(yùn)行都得到了較好的結(jié)果，說(shuō)明模型能夠很好的適應(yīng)這類小規(guī)模的問(wèn)題，程序算法具有較好的適應(yīng)性。并且對(duì)所求最短路徑進(jìn)行檢驗(yàn)，發(fā)現(xiàn)每條路徑都是準(zhǔn)確無(wú)誤的。七、模型的改進(jìn)雖然本模型對(duì)于上述問(wèn)題得到了較好的結(jié)果，但是不難發(fā)現(xiàn)本質(zhì)上都屬于小規(guī)模問(wèn)題。如果問(wèn)題的規(guī)模繼續(xù)擴(kuò)大，算法的空間復(fù)雜度和時(shí)間復(fù)雜度增長(zhǎng)迅速，使得問(wèn)題很難解決。在這里本文提出兩種改進(jìn)方法：1、 可以首先將一些杯子合并成為一個(gè)系統(tǒng)，減少杯子的總量，先解決系統(tǒng)之間的問(wèn)題，然后在解決系統(tǒng)內(nèi)部的問(wèn)題。2、 每一個(gè)問(wèn)題的可能的狀態(tài)總數(shù)是確定的，可以利用模型二，首先剔除掉不連通的點(diǎn)，建立一個(gè)網(wǎng)

14、絡(luò)拓?fù)鋱D，利用蟻群算法等智能算法得到相對(duì)最優(yōu)的解。八、參考文獻(xiàn)1張安軍. 韓信立馬分油問(wèn)題的三種策略J. 中學(xué)數(shù)學(xué)雜志:初中版, 2016(1).2郭俊杰, 畢雙艷, 雷冠麗. 分油問(wèn)題的網(wǎng)絡(luò)最優(yōu)化解法J. 吉林大學(xué)學(xué)報(bào)信息科學(xué)版, 1989(1):33-38.3任永勝. 對(duì)“分油問(wèn)題”的探微J. 山西師范大學(xué)學(xué)報(bào)(自然科學(xué)版), 2014(s2):32-34.4 彭世康, 李春梅, 彭金瑾. 完整狀態(tài)轉(zhuǎn)移圖法求三桶分油問(wèn)題全部解J. 數(shù)學(xué)通報(bào), 2015(1):56-60.5詹明清, 詹橫空. 泊松分酒問(wèn)題的一般解J. 電腦, 1996(9)6譚亮輝. 再談泊松分酒問(wèn)題的解法J. 電腦, 1

15、997(1).附錄：#include <stdio.h> #include <stdlib.h> #include <malloc.h>#define 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 /

16、最大隊(duì)列長(zhǎng)度#define QElemType pstatetypedef struct stateint data4; struct state *parent;struct state *childMethod;state,*pstate;typedef pstate SElemType;typedef int Status;typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;state *newState(state *parent,int a,int b,int c,int d) state *p

17、new=(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;i<Method;i+) pnew->childi=NULL; return pnew; typedef struct pstate *base; /隊(duì)列的基址 int front; /隊(duì)首指針 int rear; /隊(duì)尾指針SqQueue;Status Init

18、Queue ( SqQueue &q ) /初始化空循環(huán)隊(duì)列 q q.base=(QElemType *)malloc( sizeof(QElemType)* QUEUE_MAXSIZE); /分配空間 if (!q.base) exit(OVERFLOW);/內(nèi)存分配失敗退出程序 q.front =q.rear=0; /置空隊(duì)列 return OK; /InitQueue;Status EnQueue(SqQueue &q, QElemType e)/向循環(huán)隊(duì)列 q 的隊(duì)尾加入一個(gè)元素 e if (q.rear+1) % QUEUE_MAXSIZE=q.front) retu

19、rn ERROR ; /隊(duì)滿則上溢，無(wú)法再入隊(duì) q.base q.rear = e; /新元素e入隊(duì) q.rear = (q.rear + 1) % QUEUE_MAXSIZE; /指針后移 return OK; / EnQueue;Status DeQueue ( SqQueue &q, QElemType &e) /若隊(duì)列不空，刪除循環(huán)隊(duì)列q的隊(duì)頭元素， /由 e 返回其值，并返回OK if (q.front =q.rear) return ERROR;/隊(duì)列空 e = q.base q.front ; q.front=(q.front+1) % QUEUE_MAXSIZE

20、 ; 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) /若棧不為空，則用e返回S的棧頂元素if(S.top=S.base) return ERROR; e=*(S.top-1)

21、;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+=STACKINCREMENT;*S.top+=e;return OK; Status Pop(SqStack &a

22、mp;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;i<existsize;i+)if(existencei0=a&&existencei1=b&&existencei2=c)return 1;return 0;Status addexist(int

23、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,temp4,chang

24、enum=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(i!=j)for(k=0;k<4;k+)tempk=0;tempj=(volumej-e->dataj)<e->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,existsize)e->childnext=newState(e,e->data0+t