分枝-限界branchbound-資料下載頁
2024-09-29 13:23本頁面
【導讀】分支限界法常以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索問。在分支限界法中，每一個活結點只有一次機會成為擴展結點。在這些兒子結點中，導致不可行解或導致非最優(yōu)解的兒子結點被舍棄，其余兒。此后，從活結點表中取下一結點成為當前擴展結點，并重復上述結點擴展過程。分支限界法與回溯法的不同。到一個從入口到出口，活結點列表存儲于隊列中。設Cost為可行解的成本，(最小)優(yōu)化問題。c=狀態(tài)空間樹上以x為根的子樹中可行解成本的最。每次從活節(jié)點表中取出最小成本節(jié)點作為E-節(jié)。但在展開前不知道c的值。令U為當前最優(yōu)成本值。稱為FIFO分枝-限界。求可行的作業(yè)子集J，使得罰款額Σpj最小,其中j為不在?？晒烙嫗橐汛_知的罰款額:Σpj,求和范圍為?？尚薪獾谋匾獥l件：Σij=1xjtj<di. 周游路線包括的邊在鄰接矩陣中不同行不同。ei為來自鄰接矩陣的第i行的邊，所有ei不同列。Σ1≤j≤nrj為行歸約數(shù)
【正文】 ????????????????167416318619425324161511103020C??????????????????????1230120153162031021413102020~A??????????????????????1202010123152030021112101710R行約數(shù)等于 10＋ 2＋ 2＋ 3＋ 4=21 列歸約數(shù)1＋0＋3＋0＋0=4 根節(jié)點的約數(shù) r=25 ?(1)=25 ?(X)計算 ? 令 S為 R的子節(jié)點且 S不是葉節(jié)點?(S)=?(R)+A(i,j)+r,r為節(jié)點 S處的歸約數(shù) . A(i,j)為 R的歸約矩陣中邊 i,j的權值 . ? 將 R的歸約矩陣中 i行 j列置為 ∞(禁止再選擇節(jié)點i的出邊和的 j入邊 )。將 A(j,i)置為 ∞.得到的 S處的矩陣 .對其歸約得到 r. ? 如 S為葉節(jié)點 ,?(S)=根到此葉節(jié)點的周游路線成本 ?(X)計算 ? 節(jié)點 2處的矩陣 ? 已是歸約矩陣 ? ?(2)=25+10=35 ??????????????????????????????12020012152000211C?(X)計算 ? 節(jié)點 3處的矩陣 ? 對其歸約得歸約數(shù) 11 ? ?(3)=25+17+11=53 ??????????????????????????????1200034203021C算法 LCBB生成的狀態(tài)空間樹
教學課件相關推薦
鄂ICP備17016276號-1