算法設(shè)計(jì)與分析 課件 第六章 回溯法6.2.1 解空間樹

計(jì)算機(jī)算法設(shè)計(jì)與分析第6章回溯法6.2.1解空間樹一個(gè)復(fù)雜問(wèn)題的解決方案是由若干個(gè)小的決策步驟組成的決策序列，解決一個(gè)問(wèn)題的所有可能的決策序列構(gòu)成該問(wèn)題的解空間。應(yīng)用回溯法求解問(wèn)題時(shí)，首先應(yīng)該明確問(wèn)題的解空間。解空間中滿足約束條件的決策序列稱為可行解。問(wèn)題的解由一個(gè)不等長(zhǎng)或等長(zhǎng)的解向量X={x1,x2,…,xn}組成，其中分量xi表示第i步的操作。所有滿足約束條件的解向量組構(gòu)成了問(wèn)題的解向量空間。如3個(gè)物品的0-1背包問(wèn)題，其解向量空間為：{（0,0,0），（0,0,1），（0,1,0），（0,1,1），

（1,0,0），（1,0,1），（1,1,0），（1,1,1）}。解向量的樹結(jié)構(gòu)表示形式101010101010013個(gè)物品的0-1背包問(wèn)題：x1=1或0x2=1或0x3=1或06.2.1解空間樹在回溯算法中，通常使用深度優(yōu)先搜索方式遍歷解空間樹。在搜索過(guò)程中，通過(guò)剪枝操作來(lái)減少搜索的路徑數(shù)量，提高算法的效率?；厮菟惴ǖ年P(guān)鍵是在搜索過(guò)程中正確地進(jìn)行狀態(tài)更新和回溯操作。當(dāng)搜索到某個(gè)結(jié)點(diǎn)時(shí)，如果發(fā)現(xiàn)當(dāng)前結(jié)點(diǎn)不滿足問(wèn)題的約束條件，就會(huì)進(jìn)行回溯操作，返回到上一層結(jié)點(diǎn)，繼續(xù)搜索其他可能的解。通過(guò)遍歷解空間樹，回溯算法可以找到問(wèn)題的所有解，或者找到滿足特定條件的解。（1）子集樹當(dāng)所給的問(wèn)題是從n個(gè)元素的集合S中找出滿足某種性質(zhì)的子集時(shí)，相應(yīng)的解空間樹稱為子集樹。例如3個(gè)物品的0-1背包問(wèn)題，可以用一棵完全二叉樹表示其解空間。10101010101001x1=1或0x2=1或0x3=1或0（2）排列樹當(dāng)所給的問(wèn)題是確定n個(gè)元素滿足某種性質(zhì)排列時(shí)，相應(yīng)的解空間樹稱為排列樹。例如4個(gè)城市的旅行商問(wèn)題，該旅行商問(wèn)題的帶權(quán)圖和解空間排列樹。1065912814323423244232431243x1

起點(diǎn)x2有三個(gè)選擇x3有二個(gè)選擇x4有一個(gè)選擇6.2.1解空間樹定義解空間樹中幾個(gè)相關(guān)結(jié)點(diǎn)概念：（1）擴(kuò)展結(jié)點(diǎn):一個(gè)正在產(chǎn)生子結(jié)點(diǎn)的結(jié)點(diǎn)稱為擴(kuò)展結(jié)點(diǎn)。（2）活結(jié)點(diǎn):一個(gè)自身已生成但其子結(jié)點(diǎn)還沒(méi)有全部生成的結(jié)點(diǎn)稱為活結(jié)點(diǎn)。（3）死結(jié)點(diǎn):一個(gè)所有子結(jié)點(diǎn)已經(jīng)產(chǎn)生的結(jié)點(diǎn)稱做死結(jié)點(diǎn)?；厮輘1sisi+1找其他路徑當(dāng)從結(jié)點(diǎn)si搜索到結(jié)點(diǎn)si+1后，如果si+1變?yōu)樗澜Y(jié)點(diǎn)，則從結(jié)點(diǎn)si+1回退到si，再?gòu)膕i找其他可能的路徑，所以回溯法體現(xiàn)出走不通就退回上一步選擇其他路徑再走的思路。6.2.1解空間樹若用回溯法求問(wèn)題的所有解時(shí)，需要回溯到根結(jié)點(diǎn)，且根結(jié)點(diǎn)的所有可行的子樹都要已被搜索完才結(jié)束。而若使用回溯法求任一個(gè)解時(shí)，只要搜索到問(wèn)題的一個(gè)解就可以結(jié)束。以深度優(yōu)先方式搜索整個(gè)解向量空間樹效率比較低，通常以下