14-回溯法-展示頁
2024-08-19 08:28本頁面
【正文】 易于搜索的解空間組織結(jié)構(gòu)（按樹或圖組織解）；（3）以深度優(yōu)先方式搜索解空間，搜索過程中裁減掉死結(jié)點的子樹提高搜索效率?！到y(tǒng)性算法搜索至解空間樹的任一結(jié)點時，判斷該結(jié)點為根的子樹是否包含問題的解，如果肯定不包含，則跳過以該結(jié)點為根的子樹的搜索，逐層向其祖先結(jié)點回溯。14 回溯法(sch2)l 方法的基本思想回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點出發(fā)搜索解空間樹。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。l 術(shù)語: 三種搜索空間, 活結(jié)點, 死結(jié)點, 擴(kuò)展結(jié)點, 開始結(jié)點, 終端結(jié)點三種搜索空間： 表序表示: 搜索對象用線性表數(shù)據(jù)結(jié)構(gòu)表示。 隱式圖表示: 除了初始結(jié)點, 其他結(jié)點在搜索過程中動態(tài)生成. 緣于搜索空間大, 難以全部存儲.活結(jié)點：已生成一個以上子節(jié)點，但所有子結(jié)點尚未全部生成的結(jié)點死節(jié)點：不在進(jìn)一步擴(kuò)展或已產(chǎn)生了所有子結(jié)點的結(jié)點。 //葉結(jié)點是可行解，輸出解elsewhile( all Xt) do // Xt為所有x[t]的合法取值集{ x[t]= Xt中第i個值。}}執(zhí)行時： Backtrack(1) //從1擴(kuò)展并回溯（2）排列樹回溯算法框架Backtrack(int t) //搜索到樹的第t層{//由第t層向第t+1層擴(kuò)展，確定x[t]的值if tn then output(x)。if
法律信息相關(guān)推薦
鄂ICP備17016276號-1