分枝-限界branchbound-wenkub.com
2025-09-15 13:23 本頁面
【正文】 為成本矩陣時(shí) f的長度 +Σ1≤j≤nrj ? 列歸約 ? ci=min{A(j,i)|1≤j≤n} ? Σ1≤j≤ncj 為列歸約數(shù) . ? 對 195。因?yàn)椋@時(shí)活節(jié)點(diǎn)表中其它節(jié)點(diǎn)的下界估計(jì)也 ≥U， 展開這些活節(jié)點(diǎn)不能產(chǎn)生更好的解 ? 對正在展開的子節(jié)點(diǎn) x， 如 ?(x)≥U，則停止產(chǎn)生子節(jié)點(diǎn) x， 即不將其放入活節(jié)點(diǎn)表 ? 這種限界方法也可用于 FIFO活結(jié)點(diǎn)表上，稱為 FIFO分枝 限界。這個(gè)過程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止 ? 活節(jié)點(diǎn)選取規(guī)則 ? FIFO ? LIFO ? Max Profit（ MP） ? Least Cost (LC) 算法思路 (2) ? 分支限界法與回溯法的不同 ? 求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。分枝 限界 (Branch amp。 ? 搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹。 U初始為 ∞ ，其后用新得到的可行解值加以修改 帶截止期的作業(yè)調(diào)度問題（ 1） ? n個(gè)作業(yè)， 1臺(tái)處理機(jī)，每個(gè)作業(yè) i對應(yīng)一個(gè)三元組(pi,di,ti) ? pi－ 罰款額 ? di－ 截止期 ? ti － 需要的處理機(jī)時(shí)間 ? 求可行的作業(yè)子集 J，使得罰款額 Σpj最小 ,其中 j為不在J中的作業(yè) ? 定長元組表示可行作業(yè)子集 :(x(1),┅ ,x(n)) ? 設(shè) X=(x(1),…x(k)) 為狀態(tài)空間樹的節(jié)點(diǎn) ? 下界 ?(x)可估計(jì)為已確知的罰款額 : Σ(1x(j))pj ,求和范圍為1≤j≤k 帶截止期的作業(yè)調(diào)度問題（ 2） ? 限界 ? 可行解的必要條件： Σij=1xjtjdi ? 為能較早地使用 ?(x) ≥ U的限界功能 ,可以在每個(gè)結(jié)點(diǎn) x計(jì)算 c(x)的上界 u(x),并用 u(x
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1