分枝-限界branchbound-wenkub
2022-10-10 13:23:47 本頁面
【正文】 )修改 U值 ? u(x)可取 x為根的子樹下包含的任一可行解的值 ? 例如取 x(k+1)=… x(n)=0,或用貪心法快速得到一個可行解 ? 算法每生成一個子節(jié)點(diǎn)時就用 u(x)修改 U 調(diào)度問題的定長元組表示 已知 4個作業(yè)的三元組 (pi,di,ti)分別為 (5,1,1) (10,3,2) (6,2,1) (3,1,1) 調(diào)度問題的另一種狀態(tài)空間樹 12543 X1=1876 1015911141312X1=2 X1=3X1=4X2=3X2=316X4=4 X3=3X3=4 X3=4X2=4X2=4 X2=4X3=4LC檢索＋限界 689 1 0213 4 51 21 171 3x1= 1x1= 2 x1= 3x1= 4x2= 2 x2= 3 x2= 4x2= 3 x2= 4x3= 3 x3= 48001 95U = 1 41 51 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
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1