基于盲目搜索算法求解泊松分酒韓信分油問(wèn)題-文庫(kù)吧資料
2025-03-31 12:45本頁(yè)面
【正文】 ase。i++) { pnewchild[i]=NULL。 for(int i=0。 pnewdata[3]=d。 pnewdata[1]=b。 pnewparent=parent。 }SqStack。 SElemType *top。typedef int Status。}state,*pstate。 struct state *parent。 每一個(gè)問(wèn)題的可能的狀態(tài)總數(shù)是確定的，可以利用模型二，首先剔除掉不連通的點(diǎn)，建立一個(gè)網(wǎng)絡(luò)拓?fù)鋱D，利用蟻群算法等智能算法得到相對(duì)最優(yōu)的解。如果問(wèn)題的規(guī)模繼續(xù)擴(kuò)大，算法的空間復(fù)雜度和時(shí)間復(fù)雜度增長(zhǎng)迅速，使得問(wèn)題很難解決。并且對(duì)所求最短路徑進(jìn)行檢驗(yàn)，發(fā)現(xiàn)每條路徑都是準(zhǔn)確無(wú)誤的。 模型的建立通過(guò)試探，運(yùn)用問(wèn)題二的模型，發(fā)現(xiàn)版本4——史泰因豪斯在《數(shù)學(xué)萬(wàn)花筒》中的表述：有裝有14千克酒的容器，另外有可裝5千克和9千克酒的容器，要把酒平分的問(wèn)題最短路徑剛好為13步。利用程序得到最短路徑為(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步。解得：。由于只有三個(gè)容器，問(wèn)題的解可以轉(zhuǎn)化為一個(gè)求解二元一次不定方程的解的過(guò)程。具體的最短步數(shù)和最短路徑可由第一問(wèn)的算法解得。函數(shù)方程為（2）如果方程有整數(shù)解，則說(shuō)明原問(wèn)題有解。所以，第杯中的剩余容量為。由此我們得到系數(shù)矩陣（1）其中 可以看作為第杯向第杯倒入的次數(shù)。所以每一次杯子內(nèi)酒量的轉(zhuǎn)換量都是各個(gè)杯子的容積或者他們的差值。運(yùn)行結(jié)果如下：當(dāng)目標(biāo)狀態(tài)為(5,3,2,2)時(shí)，沒(méi)有得到結(jié)果說(shuō)明，無(wú)法從初始狀態(tài)到達(dá)目標(biāo)狀態(tài)。運(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)，12總共九步。最終再將各個(gè)節(jié)點(diǎn)出棧，出棧的順序即為倒酒過(guò)程中，各個(gè)酒杯的酒量。其中，樹(shù)的建立要借助于隊(duì)列這一個(gè)數(shù)據(jù)結(jié)構(gòu)，借助其將每一個(gè)新節(jié)點(diǎn)入隊(duì)、處理。對(duì)于每一個(gè)節(jié)點(diǎn)分別計(jì)算對(duì)應(yīng)的12種情況，如果狀態(tài)不存在，就將該節(jié)點(diǎn)接入樹(shù)中。遍歷過(guò)程中對(duì)于已經(jīng)遍歷的節(jié)點(diǎn)不再遍歷，降低算法的復(fù)雜度。中間狀態(tài)的下一個(gè)狀態(tài)最大可能有種。四、符號(hào)說(shuō)明符號(hào)說(shuō)明 第個(gè)容器的最大容積第個(gè)容器的現(xiàn)存的容量第個(gè)容器向第個(gè)容器倒入的次數(shù)第個(gè)容器的目標(biāo)的容量第個(gè)容器的初始的容量容器的個(gè)數(shù)五、模型的建立與求解問(wèn)題一的模型較為簡(jiǎn)單。問(wèn)題三，通過(guò)試探，發(fā)現(xiàn)對(duì)于版本四問(wèn)題的最小步數(shù)剛好13步，達(dá)到設(shè)計(jì)的要求。如果程序沒(méi)有輸出，則說(shuō)明問(wèn)題不可解。這樣原問(wèn)題就轉(zhuǎn)換為一個(gè)網(wǎng)絡(luò)拓?fù)涞膯?wèn)題。文獻(xiàn)[5][6]又介紹了如何用算法求解該問(wèn)題，其中文獻(xiàn)[6]是對(duì)文獻(xiàn)[5]的一種改進(jìn)。文獻(xiàn)[1]說(shuō)明了三種手工求解的方法，這對(duì)于小規(guī)模問(wèn)題可以解決，但是對(duì)于大規(guī)模問(wèn)題就無(wú)能為力了。韓信是如何解決這個(gè)難題的？版本4：史泰因豪斯在《數(shù)學(xué)萬(wàn)花筒》中的表述：有裝有14千克酒的容器，另外有可裝5千克和9千克酒的容器，要把酒平分，該如何辦？版本5：別萊利曼在《趣味幾何學(xué)》中表述：一只水桶，可裝12杓水，還有兩只空桶，容量分別為9杓和5杓，如何把大水桶的水分成兩半？雖然各個(gè)問(wèn)題的表述不同，但是其本質(zhì)之都是一樣的。.版本2：法國(guó)著名數(shù)學(xué)家泊松年輕時(shí)研究過(guò)的一道題：某人有12品脫美酒，想把一半贈(zèng)人，但沒(méi)有6品脫的容器，而只有一個(gè)8品脫和一個(gè)5品脫的容器，問(wèn)怎樣才能把6品脫的酒倒入8品脫的容器中。二、問(wèn)題的分析原問(wèn)題有很多個(gè)版本：版本1：日本分油問(wèn)題。問(wèn)題三：設(shè)計(jì)一個(gè)實(shí)例，要求最少完成步數(shù)不少于13步。要求不憑借任何其它工具，問(wèn)能否實(shí)現(xiàn)？若能實(shí)現(xiàn)，給出實(shí)現(xiàn)的方法，并給出充分理由說(shuō)明是否是最少步數(shù)?，F(xiàn)在初始各瓶子裝酒為。要求對(duì)實(shí)現(xiàn)方式給出詳細(xì)操作步驟。請(qǐng)嘗試從基本問(wèn)題出發(fā)建立數(shù)學(xué)模型解決以下問(wèn)題：?jiǎn)栴}一：現(xiàn)有一只裝滿12斤酒的瓶子
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1