一種回溯算法入門教學(xué)思路-文庫吧資料
2024-08-17 13:34本頁面
【正文】 這樣算法效率很低,因此需要優(yōu)化。這也是子集方法解決排列問題的途徑。注意:從例中看到子集問題每個(gè)元素取值范圍不一定通過數(shù)組給定,可以采用靈活手段來生成。例3:r[i]=1,…,n,表示第i次訪問城市r[i]。生成所有可能解,直接套用前述perm或subset即可:例1:r[i]=0或1表示第i件物品是否選中。問題類型決定解空間表示法:通常是一維數(shù)組。一般而言,難判定的往往是子集問題。例3:哈密爾頓回路問題:選一條從駐地出發(fā),經(jīng)過每個(gè)城市一遍最后回到駐地的路線,使總旅費(fèi)最小。例2:八皇后問題:n*n的棋盤上放n個(gè)皇后,使皇后間互不攻擊。 確定類型首先拋開題目約束和目標(biāo),將問題簡(jiǎn)化抓本質(zhì):變的是元素還是位置？下面通過3個(gè)典型例子說明:例1:01背包問題:給出裝背包方案,使得背包物品總價(jià)值最大。(2)用對(duì)應(yīng)算法生成所有可能解。且活結(jié)點(diǎn)概念也較難理解。(3)構(gòu)造約束函數(shù),搜索解空間,用約束函數(shù)殺死不可能產(chǎn)生解的節(jié)點(diǎn)。2 回溯解題步驟回溯法解題步驟通常為3步[2]:(1)定義解空間包含問題的解。//恢復(fù)r[i..n]原狀end。//放到位置i上perm(r,i+1,n)。//r[i
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1