分枝-限界（branchbound）-文庫吧
2025-08-26 13:23 本頁面
【正文】 ) 0/1Knapsack ? FIFO Search ? Nodes are expended in a breadthfirst manner ? Live nodes are stored in a queue ? Maxprofit search ? Nodes are expended in a maxprofit manner ? Live nodes are stored in a max heap 0/1Knapsack:status of SP ? n=3， c= 30 ? w= [ 20 , 15 , 15 ] ? p= [ 40 , 25 , 25 ] TSP ? FIFO search ? Leastcost search（ minheap） 應用問題 ? 作業(yè)調度問題 (Job Scheduling) ? 旅行商問題 (TSP) Least Cost Search (Bounding function) 成本函數(shù) (Cost function) ? 設 Cost(x)為可行解的成本， (最小 )優(yōu)化問題要求找有最小成本的可行解 ? 定義狀態(tài)空間樹上任一結點 x的成本函數(shù) c(x)如下 : ? 如 x為可行葉結點則 c(x)=cost(x)。 ? 如 x為非葉結點 ? c(x)=狀態(tài)空間樹上以 x為根的子樹中可行解成本的最小值 ? 如其子樹中無可行解則 c(x)=∞ LC檢索過程 ? 每次從活節(jié)點表中取出最小成本節(jié)點作為 E節(jié)點并展開其全部子節(jié)點 ? 但在展開前不知道 c(x)的值 ? 以 c(x)的下界估值 ?(x)做 LC檢索 啟發(fā)式 ? 要求 ?(x)滿足 : ? ?(x)=Cost(x),當 x為可行 葉節(jié)點 時 LC限界 ? 令 U為當前最優(yōu)成本值 ? 對當前的選取的擴展節(jié)點 E，當 ?(E)≥U時算法結束。因為，這時活節(jié)點表中其它節(jié)點的下界估計也 ≥U， 展開這些活節(jié)點不能產(chǎn)生更好的解 ? 對
教學課件相關推薦
鄂ICP備17016276號-1