一種回溯算法入門教學(xué)思路(編輯修改稿)
2025-08-31 13:34 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 。(2)適合的方式組織解空間。(3)構(gòu)造約束函數(shù),搜索解空間,用約束函數(shù)殺死不可能產(chǎn)生解的節(jié)點(diǎn)。其中第(1)、(2)步描述含糊,又將這兩個(gè)密切相關(guān)步驟割裂開(kāi),學(xué)生很容易變得困惑。且活結(jié)點(diǎn)概念也較難理解。本文提出解題步驟為:(1)確定是排列問(wèn)題還是子集問(wèn)題。(2)用對(duì)應(yīng)算法生成所有可能解。(3)添加約束、剪枝進(jìn)行優(yōu)化。 確定類型首先拋開(kāi)題目約束和目標(biāo),將問(wèn)題簡(jiǎn)化抓本質(zhì):變的是元素還是位置？下面通過(guò)3個(gè)典型例子說(shuō)明:例1:01背包問(wèn)題:給出裝背包方案,使得背包物品總價(jià)值最大。不關(guān)心物品裝入順序,因此是子集類。例2:八皇后問(wèn)題:n*n的棋盤(pán)上放n個(gè)皇后,使皇后間互不攻擊?？瓷先ズ臀恢糜嘘P(guān),但交換兩個(gè)皇后的位置不產(chǎn)生新方案,因此也是子集問(wèn)題。例3:哈密爾頓回路問(wèn)題:選一條從駐地出發(fā),經(jīng)過(guò)每個(gè)城市一遍最后回到駐地的路線,使總旅費(fèi)最小。顯然是排列問(wèn)題。一般而言,難判定的往往是子集問(wèn)題。 所有可能解。問(wèn)題類型決定解空間表示法:通常是一維數(shù)組。但元素取值范圍要根據(jù)題目靈活設(shè)計(jì)。生成所有可能解,直接套用前述perm或subset即可:例1:r[i]=0或1表示第i件物品是否選中。例2:r[i]=1,
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1