在一個4×4的方格的棋盤上，將數(shù)字1到15代表的15個棋子以任意的順序置入各方格中，空出一格。要求通過有限次的移動，把一個給定的初始狀態(tài)變成目標(biāo)狀態(tài)。移動的規(guī)則是：每次只能把空格周圍的四格數(shù)字（棋子）中的任意一個移入空格，從而形成一個新的狀態(tài)。為了有效的移動，設(shè)計了估值函數(shù)C1（x），表示在結(jié)點x的狀態(tài)下，沒有到達(dá)目標(biāo)狀態(tài)下的正確位置的棋子的個數(shù)。
請使用該估計函數(shù)，對圖示的初始狀態(tài)，給出使用分支限界方法轉(zhuǎn)換到目標(biāo)狀態(tài)的搜索樹。
您可能感興趣的試卷
最新試題
在對Dijkstra算法進(jìn)行初始化時，如果兩個頂點之間沒有邊，則它們之間的距離為（）。
下列關(guān)于貪心算法與動態(tài)規(guī)劃算法說法正確的是（）。
分支限界法中，擴展出的孩子結(jié)點在入隊時，存儲該孩子結(jié)點的父結(jié)點的地址和左孩子標(biāo)志。其目的是什么？（）
在隊列式分支限界法解決裝載問題時，為什么在其改進(jìn)算法中，每次進(jìn)入左分支都要檢查更新bestw，而不是等搜索到達(dá)葉子結(jié)點時才去更新bestw，其目的是什么？（）
馬的遍歷問題能否有可行解，與（）有關(guān)。
根據(jù)活結(jié)點表的組織方式不同，分支限界法包括（）等形式。
下列關(guān)于效率的說法正確的是（）。
在解決活動安排問題時應(yīng)首先對活動進(jìn)行排序，排序的依據(jù)是（）。
回溯法采用的搜索策略是（）。
pollard算法找到一個整數(shù)因子的時間復(fù)雜性是（）。