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