分枝-限界branchbound(更新版)
【正文】 t 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īng)用問題 ? 作業(yè)調(diào)度問題 (Job Scheduling) ? 旅行商問題 (TSP) Least Cost Search (Bounding function) 成本函數(shù) (Cost function) ? 設(shè) Cost(x)為可行解的成本， (最小 )優(yōu)化問題要求找有最小成本的可行解 ? 定義狀態(tài)空間樹上任一結(jié)點(diǎn) x的成本函數(shù) c(x)如下 : ? 如 x為可行葉結(jié)點(diǎn)則 c(x)=cost(x)。將 A(j,i)置為 ∞.得到的 S處的矩陣 .對(duì)其歸約得到 r. ? 如 S為葉節(jié)點(diǎn) ,?(S)=根到此葉節(jié)點(diǎn)的周游路線成本 ?(X)計(jì)算 ? 節(jié)點(diǎn) 2處的矩陣 ? 已是歸約矩陣 ? ?(2)=25+10=35 ??????????????????????????????12020012152000211C?(X)計(jì)算 ? 節(jié)點(diǎn) 3處的矩陣 ? 對(duì)其歸約得歸約數(shù) 11 ? ?(3)=25+17+11=53 ??????????????????????????????1200034203021C算法 LCBB生成的狀態(tài)空間樹
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1