分枝-限界branchbound(完整版)
【正文】 1 82 12 10U = 91 05U = 81 1XXX此 刻 隊 列 為 空可行條件 (截至期 )作為一種限界方法 優(yōu)化解為 {2,3}，罰款額為 8 ?(x) u(x):該點(diǎn)對應(yīng)的可行解的值 非可行節(jié)點(diǎn) 被限界掉的節(jié)點(diǎn) 貨郎擔(dān)問題 (TSP) ? 狀態(tài)空間樹 (Permutation Tree) ? 費(fèi)用矩陣表示 ? 周游路線包括的邊在鄰接矩陣中不同行不同列 ? 歸約矩陣和歸約數(shù)（作為 ?(X)） TSP的狀態(tài)空間樹 一種計算 ?(X)的方法 ? 設(shè) f=(e1,┅, en)為一條周游路線 ? ei為來自鄰接矩陣的第 i行的邊，所有 ei不同列 ? cost(ei)=A(i,ji) ? 行歸約 ? ri=min{A(i,j)|1≤j≤n} ? Σ1≤j≤nrj 為行歸約數(shù) ? 設(shè) 195。為行歸約后的矩陣 ? Cost(f)≥Σ1≤j≤nrj ? Cost(f)=以 195。 ? 在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中 ? 此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。 迷宮問題：問題描述 ? 問題描述：內(nèi)有障礙物的長方形格子，含有一個入口和一個出口，找到一個從入口到出口，能繞過所有障礙物的路徑 ? 矩陣表示 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)隊列 ? 解空間按寬度優(yōu)先搜索 ? 活結(jié)點(diǎn)列表存儲于隊列中 (1,1) (1,2) (2,1) (3,1) (3,3) (1,3) (3,2) 0/1Knapsack ? FIFO Search ? Nodes are expended in a breadthfirs
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1