基于盲目搜索算法求解泊松分酒韓信分油問題_第1頁
基于盲目搜索算法求解泊松分酒韓信分油問題_第2頁
基于盲目搜索算法求解泊松分酒韓信分油問題_第3頁
基于盲目搜索算法求解泊松分酒韓信分油問題_第4頁
基于盲目搜索算法求解泊松分酒韓信分油問題_第5頁
已閱讀5頁,還剩7頁未讀 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

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

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

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

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

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

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

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

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

9、路徑的方案個數(shù)。運行程序得到結(jié)果分別為:當目標狀態(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è)總共九步。運行結(jié)果如下:當目標狀態(tài)為(3,3,3,3)時,其中的一條最短路徑為(12,0,0,0)->(6,0,6,0)->(3,0,6,3)->(3,3,6,0)->(3,3,3,3),總共四步。運行結(jié)果如下

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

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

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

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

14、絡(luò)拓撲圖,利用蟻群算法等智能算法得到相對最優(yōu)的解。八、參考文獻1張安軍. 韓信立馬分油問題的三種策略J. 中學數(shù)學雜志:初中版, 2016(1).2郭俊杰, 畢雙艷, 雷冠麗. 分油問題的網(wǎng)絡(luò)最優(yōu)化解法J. 吉林大學學報信息科學版, 1989(1):33-38.3任永勝. 對“分油問題”的探微J. 山西師范大學學報(自然科學版), 2014(s2):32-34.4 彭世康, 李春梅, 彭金瑾. 完整狀態(tài)轉(zhuǎn)移圖法求三桶分油問題全部解J. 數(shù)學通報, 2015(1):56-60.5詹明清, 詹橫空. 泊松分酒問題的一般解J. 電腦, 1996(9)6譚亮輝. 再談泊松分酒問題的解法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、最大隊列長度#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; /隊列的基址 int front; /隊首指針 int rear; /隊尾指針SqQueue;Status Init

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

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論