分枝-限界branchbound(專業(yè)版)
【正文】 迷宮問題：問題描述 ? 問題描述：內(nèi)有障礙物的長方形格子，含有一個(gè)入口和一個(gè)出口，找到一個(gè)從入口到出口，能繞過所有障礙物的路徑 ? 矩陣表示 0 0 0 0 1 1 0 0 0 迷宮問題： FIFO Search 1,1 1,2 1,3 2,1 2,2 2,3 3,1 3,2 3,3 擴(kuò)展節(jié)點(diǎn) 活節(jié)點(diǎn)隊(duì)列 ? 解空間按寬度優(yōu)先搜索 ? 活結(jié)點(diǎn)列表存儲于隊(duì)列中 (1,1) (1,2) (2,1) (3,1) (3,3) (1,3) (3,2) 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ī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)。為行歸約后的矩陣 ? Cost(f)≥Σ1≤j≤nrj ? Cost(
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1