分支限界法——TSP問題講訴.ppt

分支限界法旅行售貨員問題 TSP 小燕子 6 1分支限界法的基本思想 1 分支限界法與回溯法的不同 1 求解目標(biāo) 回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解 而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解 或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解 2 搜索方式的不同 回溯法以深度優(yōu)先的方式搜索解空間樹 而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹 6 1分支限界法的基本思想 2 分支限界法基本思想分支限界法常以廣度優(yōu)先或以最小耗費(fèi) 最大效益 優(yōu)先的方式搜索問題的解空間樹 在分支限界法中 每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn) 活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn) 就一次性產(chǎn)生其所有兒子結(jié)點(diǎn) 在這些兒子結(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ò)展過程 這個(gè)過程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止 6 1分支限界法的基本思想 3 常見的兩種分支限界法 1 隊(duì)列式 FIFO 分支限界法按照隊(duì)列先進(jìn)先出 FIFO 原則選取下一個(gè)節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn) 2 優(yōu)先隊(duì)列式分支限界法按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級(jí)選取優(yōu)先級(jí)最高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn) 最大優(yōu)先隊(duì)列 使用最大堆 體現(xiàn)最大效益優(yōu)先最小優(yōu)先隊(duì)列 使用最小堆 體現(xiàn)最小費(fèi)用優(yōu)先 旅行售貨員問題 TSP 某售貨員要到若干城市去推銷商品 一直各城市之間的路程 他要選定一條從駐地出發(fā) 經(jīng)過每個(gè)城市一遍 最后回到住地的路線 使總的路程最短 該問題是一個(gè)NP完全問題 有 n 1 條可選路線 路線是一個(gè)帶權(quán)圖 圖中各邊的費(fèi)用 權(quán) 為正數(shù) 圖的一條周游路線是包括V中的每個(gè)頂點(diǎn)在內(nèi)的一條回路 周游路線的費(fèi)用是這條路線上所有邊的費(fèi)用之和 問題陳述 旅行售貨員問題的解空間可以組織成一棵樹 從樹的根結(jié)點(diǎn)到任一葉結(jié)點(diǎn)的路徑定義了圖的一條周游路線 旅行售貨員問題要在圖G中找出費(fèi)用最小的周游路線 即 設(shè)G V E 是一帶權(quán)有向圖 V 1 2 n 其耗費(fèi)矩陣C ci j 當(dāng) i j E時(shí) 記ci j 且ci j 問如何選擇周游路線使耗費(fèi)最小 TSP問題 算法思路 設(shè)周游路線從結(jié)點(diǎn)1開始 解為等長(zhǎng)數(shù)組X 1 x2 xn xi 2 n 則解空間樹為排列樹 在樹中做廣度優(yōu)先搜索 約束條件 xi xj i j 目標(biāo)函數(shù) 解向量對(duì)應(yīng)的邊權(quán)之和 Cij目標(biāo)函數(shù)限界初值 U 活結(jié)點(diǎn)隊(duì)列 隊(duì)列式分支限界法 初始擴(kuò)展結(jié)點(diǎn)為B 活結(jié)點(diǎn)隊(duì)列為空 C 30 11 4 26 6 25 14 59 25 24 算法描述 算法開始時(shí)創(chuàng)建一個(gè)最小堆 用于表示活結(jié)點(diǎn)優(yōu)先隊(duì)列 堆中每個(gè)結(jié)點(diǎn)的子樹費(fèi)用的下界lcost值是優(yōu)先隊(duì)列的優(yōu)先級(jí) 接著算法計(jì)算出圖中每個(gè)頂點(diǎn)的最小費(fèi)用出邊并用minout記錄 如果所給的有向圖中某個(gè)頂點(diǎn)沒有出邊 則該圖不可能有回路 算法即告結(jié)束 如果每個(gè)頂點(diǎn)都有出邊 則根據(jù)計(jì)算出的minout作算法初始化 優(yōu)先隊(duì)列式分支限界法用極小堆存儲(chǔ)活結(jié)點(diǎn)表 B被擴(kuò)展后 它的三個(gè)兒子結(jié)點(diǎn)C D E被依次插入堆中 E被擴(kuò)展后 它的兒子結(jié)點(diǎn)J K被依次插入當(dāng)前堆中 D被擴(kuò)展后 它的兒子結(jié)點(diǎn)H I被依次插入當(dāng)前堆中 初始擴(kuò)展結(jié)點(diǎn)為B 優(yōu)先隊(duì)列為空 B E D C E D J K C D H J K I C H J K I C J K I C K I C I C C K被擴(kuò)展后 得到可行解費(fèi)用為59 高于當(dāng)前最優(yōu)解25 算法的while循環(huán)體完成對(duì)排列樹內(nèi)部結(jié)點(diǎn)的擴(kuò)展 對(duì)于當(dāng)前擴(kuò)展結(jié)點(diǎn) 算法分2種情況進(jìn)行處理 首先考慮s n 2的情形 此時(shí)當(dāng)前擴(kuò)展結(jié)點(diǎn)是排列樹中某個(gè)葉結(jié)點(diǎn)的父結(jié)點(diǎn) 如果該葉結(jié)點(diǎn)相應(yīng)一條可行回路且費(fèi)用小于當(dāng)前最小費(fèi)用 則將該葉結(jié)點(diǎn)插入到優(yōu)先隊(duì)列中 否則舍去該葉結(jié)點(diǎn) 當(dāng)s n 2時(shí) 算法依次產(chǎn)生當(dāng)前擴(kuò)展結(jié)點(diǎn)的所有兒子結(jié)點(diǎn) 由于當(dāng)前擴(kuò)展結(jié)點(diǎn)所相應(yīng)的路徑是x 0 s 其可行兒子結(jié)點(diǎn)是從剩余頂點(diǎn)x s 1 n 1 中選取的頂點(diǎn)x i 且 x s x i 是所給有向圖G中的一條邊 對(duì)于當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一個(gè)可行兒子結(jié)點(diǎn) 計(jì)算出其前綴 x 0 s x i 的費(fèi)用cc和相應(yīng)的下界lcost 當(dāng)lcost bestc時(shí) 將這個(gè)可行兒子結(jié)點(diǎn)插入到活結(jié)點(diǎn)優(yōu)先隊(duì)列中 算法中while循環(huán)的終止條件是排列樹的一個(gè)葉結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn) 當(dāng)s n 1時(shí) 已找到的回路前綴是x 0 n 1 它已包含圖G的所有n個(gè)頂點(diǎn) 因此 當(dāng)s n 1時(shí) 相應(yīng)的擴(kuò)展結(jié)點(diǎn)表示一個(gè)葉結(jié)點(diǎn) 此時(shí)該葉結(jié)點(diǎn)所相應(yīng)的回路的費(fèi)用等于cc和lcost的值 剩余的活結(jié)點(diǎn)的lcost值不小于已找到的回路的費(fèi)用 它們都不可能導(dǎo)致費(fèi)用更小的回路 因此已找到葉結(jié)點(diǎn)所相應(yīng)的回路是一個(gè)最小費(fèi)用旅行售貨員回路 算法可結(jié)束 算法結(jié)束時(shí)返回找到的最小費(fèi)用 相應(yīng)的最優(yōu)解由數(shù)組v給出 while E s n 1 非葉結(jié)點(diǎn)if E s n 2 當(dāng)前擴(kuò)展結(jié)點(diǎn)是葉結(jié)點(diǎn)的父結(jié)點(diǎn) 再加2條邊構(gòu)成回路所構(gòu)成回路是否優(yōu)于當(dāng)前最優(yōu)解if a E x n 2 E n 1 NoEdge 下界 if bN N x newint n for intj 0 j n j N x j E x j N x E s 1 E x i N x i E x E s 1 N cc cc N s E s 1 N lcost b N rcost rcost H Insert N delete E x 完成結(jié)點(diǎn)擴(kuò)展 取下一擴(kuò)展結(jié)點(diǎn) try H DeleteMin E catch OutOfBounds break 堆已空 if bestc NoEdge returnNoEdge 無回路for i 0 i n i v i 1 E x i 將最優(yōu)解復(fù)制到v 1 n while true 釋放最小堆中所有結(jié)點(diǎn)delete E x try H DeleteMin E catch OutOfBounds break returnbestc 面試題1 有一根27厘米長(zhǎng)的細(xì)木桿 在第3厘米 7厘米 11厘米 17厘米 23厘米這五個(gè)位置上各有一只螞蟻 木桿很細(xì) 不能同時(shí)通過兩只螞蟻 開始時(shí) 螞蟻的頭朝向左還是右是任意的 他們只會(huì)朝前走或掉頭 但不會(huì)后退 當(dāng)兩只螞蟻相遇后 螞蟻會(huì)同時(shí)掉頭朝反方向走 假設(shè)螞蟻們每秒鐘可以走1厘米的距離 求所有螞蟻都離開木桿的最小時(shí)間和最大時(shí)間 問題分析 1 最小時(shí)間肯定是各自朝最近的一端跑 27 11 14 1123 所以最長(zhǎng)時(shí)間是24 算法 1 找出中間的螞蟻離兩端的距離中較小的 a 2 11a 2 27 11 14 因?yàn)閍 2 a 2 所以最小距離是11 時(shí)間11 1 112 找出兩端的螞蟻距兩端的距離中較大的 a 0 3a 0 27 3 24a 4 23a 4 27 23 4這四個(gè)數(shù)中最大的是243 所以 最大時(shí)間24 最小時(shí)間11 程序 publicclassAnt privatestaticintLONG 27 privateint a 3 7 11 17 23 privateintmin 0 max 0 publicvoidgogogo for inti 0 i a length i min Math max min Math min a i LONG a i max Math max max Math max a i LONG a i publicintgetMax returnmax publicintgetMin returnmin publicstaticvoidmain String args Antclient newAnt client gogogo System out println client getMax System out println client getMin 面試題2 猴子分桃有5只猴子在海邊發(fā)現(xiàn)一堆桃子 決定第二天來平分 第二天清晨 第一只猴子最早來到 它左分右分分不開 就朝海里扔了一只 恰好可以分成5份 它拿上自己的一份走了 第2 3 4 5只猴子也遇到同樣的問題 采用了同樣的方法 都是扔掉一只后 恰好可以分成5份 問這堆桃子至少有多少只 分析題目 只要能求出每一個(gè)猴子當(dāng)前桃子總數(shù) 最后就能求出最終結(jié)果 還有一個(gè)問題就是從什么地方入手 是知道第一只猴子面前的總數(shù)還是最后一只猴子面前的總數(shù) 再次假設(shè) 1 知道第一只猴子面前的總數(shù)n 那么下一只猴子面前應(yīng)該有 n n 1 5 個(gè)桃子 可以利用一個(gè)循環(huán)來實(shí)現(xiàn)n的值是否滿足要求 這是算法1 2 如果知道最后一只猴子面前的總數(shù)n 那么上一只猴子面前應(yīng)該有n 4 5 1個(gè)桃子 同樣 也可以利用一個(gè)循環(huán)來驗(yàn)證滿足條件的n值 這是算法2 下面發(fā)算法2的代碼 結(jié)果為3121 includevoidmain intCount 1 while true inti 0 intTemp C