【正文】 f)=以 195。分枝 限界 (Branch amp。為成本矩陣時(shí) f的長(zhǎng)度 +Σ1≤j≤nrj ? 列歸約 ? ci=min{A(j,i)|1≤j≤n} ? Σ1≤j≤ncj 為列歸約數(shù) . ? 對(duì) 195。 ? 搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹。 ? 如 x為非葉結(jié)點(diǎn) ? c(x)=狀態(tài)空間樹上以 x為根的子樹中可行解成本的最小值 ? 如其子樹中無可行解則 c(x)=∞ LC檢索過程 ? 每次從活節(jié)點(diǎn)表中取出最小成本節(jié)點(diǎn)作為 E節(jié)點(diǎn)并展開其全部子節(jié)點(diǎn) ? 但在展開前不知道 c(x)的值 ? 以 c(x)的下界估值 ?(x)做 LC檢索 啟發(fā)式 ? 要求 ?(x)滿足 : ? ?(x)=Cost(x),當(dāng) x為可行 葉節(jié)點(diǎn) 時(shí) LC限界 ? 令 U為當(dāng)前最優(yōu)成本值 ? 對(duì)當(dāng)前的選取的擴(kuò)展節(jié)點(diǎn) E，當(dāng) ?(E)≥U時(shí)算法結(jié)束。(i,j)=A(i,j)ri ,195。 Bound) 宮秀軍 天津大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 主要內(nèi)容 ? 引論 ? 主要思想 ? 求解步驟 ? 應(yīng)用 ? 作業(yè)調(diào)度問題 (Job Scheduling) ? 旅行商問題 (TSP) 算法思路 (1) ? 分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問題的解空間樹 ? 在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn) ? 活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。做列歸約得到矩陣 R和歸約數(shù) Σ1≤j≤ncj ? Cost(f)=f在 R中的成本 + Σ1≤j≤nrj+ Σ1≤j≤ncj 歸約矩陣和歸約數(shù) ? 每行每列均含有 0的矩陣稱為歸約陣 ? 矩陣歸約 ? 假設(shè)第 i行的約數(shù)為 ti,第 j列的約數(shù)為 rj, 1≤i, j≤n, 那么各行、列的約數(shù)之和稱為矩陣約數(shù) ??????njjni