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

1、搬運工問題的啟示重慶外語學校劉汝佳三用IDA算法解搬運工問題實現(xiàn)與改進在上一節(jié)中，我們知道了IDA算法是我們解決搬運工問題的核心算法。在這一節(jié)里，我們將用IDA算法來做一個解決搬運工問題的程序–雖然是我們的最初版本(我們稱做S4Baby)，但是不要小看它哦！1IDA算法框架算法框架由前所述，IDA算法是基于重復式深度優(yōu)先的A算法忽略所有f值大于深度限制的結(jié)點。那么，我們不難寫出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這只是一個很粗略的框架，什么事情都不能做。不過我想大家可能比較急于試驗一下IDA的威力，因此我們不妨就做一個最最基本的程序。2.第一個

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

5、0118351423101924312223462424104324486359312542345121386582611846461417876352731847829681139289384881569412291014249560105143086415011144511151331719251NA1M124193231252NA1M1341433115153847014620341133254162427015657351611

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