數(shù)據(jù)結(jié)構(gòu)與算法實習(編輯修改稿)
2025-05-26 08:38 本頁面
【文章內(nèi)容簡介】 退回(即“回溯” )到第 i1行的皇后，重新安排 ? 前面的安排不太合理 回溯過程 ? 如果 8個皇后都排好了，則打印這種方案 ? 為了找到其它方案，應(yīng)該回溯，重新試探皇后的下一種安排方法 ? 抹掉前面試探留下的標記，即恢復(fù) A[j]、B[i+j]、 C[ij+7]為未被占用狀態(tài) ? 這種回溯過程將逐步返回 ? 使得各行的皇后都能試探到各種可能的擺法 回溯法的框架 ? 問題的解 n元組 (x0, x1,… ， xn1)： void rectry(k) { // 初始調(diào) rectry(0)。 置 X[k]為第一個可能值； while (X[k]可能值沒有試完 ) { 設(shè)置 X[k]所涉及的標記 。 if ((X[0], X[1]， … ， X[n1])是解 ) 打印一組解 。 else rectry(k+1)。 回溯，抹去 X[k]涉及的標記； 取下一個可能的 X[k]值 。 } } 八皇后的遞歸算法 void queen(int i) { int j。 for (j=0。 jn。 j++) { if (place(i,j)) { // 能放置嗎 X[i] = j。 mark(i,j)。 // 標記（ i,j） 的影響 if (i n1) queen(i+1)。 // 接著試下一個 else print(count)。 // 打印一個解 erase(i,j)。 // 回溯，去掉剛才標記 } } } 四皇后時，函數(shù)執(zhí)行模擬 ? 失敗情況下回溯過程模擬： queen(0) 試探 x[0]=0, mark(0,0) queen(1) // for (j=0。 jn。j++) 試探 x[1]=2, mark(1,2) queen(2) // 擺不了，函數(shù)返回 erase(1,2) // 回溯 試探 x[1]=3, mark(1,3) …… 0 1 ● ● ● ● 皇后函數(shù)執(zhí)行模擬 (續(xù) ) ? 四皇后成功情況下，回溯，繼續(xù)求解： X = [1, 3, 0, 2]為第一個解，求其他解 …… erase(3, 2) 試探下一個 j=3, 當然不能擺 erase(2, 0), 試探其他，都失 //queen(2) erase(1, 3), 試探其他，都失敗 //queen(1) erase(0, 1) // queen(0) x[0] = 2, mark(0,2) queen(1) x[1]=0, mark(1, 0) ……. 得到第二個解 X=[2, 0, 3, 1] 0 1 2 3 八皇后算法 討論 ?如果只要求出一個解，這個程序要作修改 ?求一個解的程序比求所有解反而要多一些判斷。 回溯算法 ?巡回售貨員問題 1 2 3 4 9 5 4 2 7 13 1 2 3 4 3 4 2 4 2 3 4 3 4 2 3 2 29 23 28 28 28 29 有一個售貨員，從他所在的城市出發(fā)去訪問 n1個城市，要求經(jīng)過每個城市恰好一次，然后返回原地問他的路線怎樣安排才最經(jīng)濟（即線路最短）？ 貪心法 ?問題的狀態(tài)空間很大時，窮舉法計算量可能會太大 ?當人們面對一個問題時，可能會采取目前看來最接近解狀態(tài)的選擇方案 ?貪心法可以看作回溯的特例 貪心法的過程 ?在搜索解的過程中，從根結(jié)點開始，設(shè)當前結(jié)點為 A， A的所有子結(jié)點中權(quán)值最大 的為 B，則選擇 B作為下一個結(jié)點 ?可以貪心解的問題需要滿足的性質(zhì) ? 貪心選擇性質(zhì) ? 最優(yōu)子結(jié)構(gòu)性質(zhì) ?時間代價 多為 線性 部分裝入背包問題 一個旅行者準備隨身攜帶一個背包?？梢苑湃氡嘲奈锲酚?n個，每個物品的重量和價值分別為 wj， vj， j=1,2,…,n ，旅行者可以選擇物品 i的全部，也可以選擇 i的 xi部分， 0≤xi≤1。如果背包的重量限制是 c，怎么選擇放入背包的物品以使得背包的價值最大？ 背包問題的形式定義 ? 輸入： c0, wi0, v
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1