算法合集之《搬運(yùn)工問(wèn)題的啟示(3)用ida星算法解搬運(yùn)工問(wèn)題 》

1、搬運(yùn)工問(wèn)題的啟示重慶外語(yǔ)學(xué)校劉汝佳三用IDA算法解搬運(yùn)工問(wèn)題實(shí)現(xiàn)與改進(jìn)在上一節(jié)中，我們知道了IDA算法是我們解決搬運(yùn)工問(wèn)題的核心算法。在這一節(jié)里，我們將用IDA算法來(lái)做一個(gè)解決搬運(yùn)工問(wèn)題的程序–雖然是我們的最初版本(我們稱做S4Baby)，但是不要小看它哦！1IDA算法框架算法框架由前所述，IDA算法是基于重復(fù)式深度優(yōu)先的A算法忽略所有f值大于深度限制的結(jié)點(diǎn)。那么，我們不難寫出IDA算法框架的偽代碼偽代碼1IDA算法框架procedur

2、eIDA_STAR(StartState)beginPathLimit:=H(StartState)–1Success:=Falserepeatinc(PathLimit)StartState.g:=0Push(OpenStackStartState)repeatCurrentState:=Pop(OpenStack)IfSolution(CurrentState)thenSuccess=TrueElseifPathLimit=Curr

3、entState.gH(CurrentState)thenFeachChild(CurrentState)doPush(OpenStackChild(CurrentState))untilSuccessempty(OpenStack)untilSuccessResourceLimitsReachedend這只是一個(gè)很粗略的框架，什么事情都不能做。不過(guò)我想大家可能比較急于試驗(yàn)一下IDA的威力，因此我們不妨就做一個(gè)最最基本的程序。2.第一個(gè)

4、程序第一個(gè)程序要從框架做一個(gè)程序需要填充一些東西。在這里我們就展開(kāi)一些討論。輸入輸出文件格式輸入輸出文件格式什么！第一關(guān)都就沒(méi)有動(dòng)靜了…55555，生成了18萬(wàn)個(gè)結(jié)點(diǎn)不過(guò)很多關(guān)都很快就過(guò)了的。我們用1000000個(gè)結(jié)點(diǎn)為上限(在我的Celeron300A上要運(yùn)行十多分鐘)得到以下的測(cè)試結(jié)果：No.步數(shù)步數(shù)結(jié)點(diǎn)數(shù)結(jié)點(diǎn)數(shù)No.步數(shù)步數(shù)結(jié)點(diǎn)數(shù)結(jié)點(diǎn)數(shù)No.步數(shù)步數(shù)結(jié)點(diǎn)數(shù)結(jié)點(diǎn)數(shù)11518647621810241111452624227110421

5、0118351423101924312223462424104324486359312542345121386582611846461417876352731847829681139289384881569412291014249560105143086415011144511151331719251NA1M124193231252NA1M1341433115153847014620341133254162427015657351611

6、11855NA1M1612394736102425614331817663379117157NA1M18115108381155658NA1M191046739107259113282010168140920360NA1M61NA1M沒(méi)有解決的幾關(guān)是：51525557586061比較困難的幾關(guān)是1161820263035373850535456下面，我們來(lái)看看“困難關(guān)卡”的下界估計(jì)的情況，看看“偷懶”付出的代價(jià)。關(guān)卡關(guān)卡最優(yōu)步數(shù)最優(yōu)步數(shù)