目錄

• 1.問(wèn)題描述
  1.1 問(wèn)題描述
  1.2 各種方法的總結(jié)
  ?1.2.1 分支限界法的總結(jié)
  ?1.2.2 分支限界法與最小生成樹(shù)刀脏、最短路徑之間的聯(lián)系（都借助了貪心性質(zhì)）
• 2.最優(yōu)化模型——整數(shù)規(guī)劃
• 3.基于上下界的分支限界法——求解對(duì)稱(chēng)型TSP
  3.1 下界（估算）
  3.2 上界——貪心
  3.3 基于上下界的分支限界法——本質(zhì)上是一樣的
  3.4 一個(gè)示例
• 4.基于降階的分支限界法
  4.1 問(wèn)題描述
  4.2 分支限界法解決旅行商問(wèn)題
  4.3 一個(gè)示例
• 5.直觀的回溯法和分支限界法求解
  5.1 實(shí)例
  5.2 回溯法——深度優(yōu)先遍歷解空間樹(shù)
  5.3 分支限界法——廣度優(yōu)先遍歷
  5.4 采用基于歸約方式的分支限界法
• 6.動(dòng)態(tài)規(guī)劃
  6.1 刻畫(huà)一個(gè)最優(yōu)解的結(jié)構(gòu)特征（最優(yōu)子結(jié)構(gòu)）
  6.2 遞歸地定義最優(yōu)解的值（重疊子問(wèn)題）
  6.3 計(jì)算最優(yōu)解的值峻村，通常采用自底向上的方法
  6.4 利用計(jì)算出的信息構(gòu)造一個(gè)最優(yōu)解
• 7.近似算法
• 8 遺傳算法
• 9.模擬退火
• 10.神經(jīng)網(wǎng)絡(luò)

1.問(wèn)題描述

1.1 問(wèn)題描述

• 一個(gè)售貨員必須訪問(wèn)n個(gè)城市留夜，恰好訪問(wèn)每個(gè)城市一次眠菇，并最終回到出發(fā)城市镀层。
  售貨員從城市i到城市j的旅行費(fèi)用是一個(gè)整數(shù)炕柔，旅行所需的全部費(fèi)用是他旅行經(jīng)過(guò)的的各邊費(fèi)用之和象缀，而售貨員希望使整個(gè)旅行費(fèi)用最低。
• （等價(jià)于求圖的最短哈密爾頓回路問(wèn)題）令G=(V, E)是一個(gè)帶權(quán)重的有向圖斋扰，頂點(diǎn)集V=(v₀, v₁, ..., v_n-1)渡八。從圖中任一頂點(diǎn)v_i出發(fā)，經(jīng)圖中所有其他頂點(diǎn)一次且只有一次传货，最后回到同一頂點(diǎn)v_i的最短路徑屎鳍。

1.2 各種方法的總結(jié)

1.2.1 分支限界法的總結(jié)

• 對(duì)于分支限界法的本質(zhì)，可以描述如下：
  1）通過(guò)貪心思想獲得一個(gè)上界bound
  2）針對(duì)一條邊進(jìn)行分支（左邊選擇該邊问裕、右邊不選該邊）逮壁，然后對(duì)分支計(jì)算出下界，如果下界超過(guò)上界則剪去該分支粮宛；該分支的計(jì)算也是使用貪心思想
• 直觀的回溯法和分支限界法給的提示：
  1）Hamilton回路經(jīng)過(guò)所有頂點(diǎn)窥淆，因此從直觀的回溯法和分支限界法對(duì)于選擇哪個(gè)頂點(diǎn)開(kāi)始搜索沒(méi)有本質(zhì)區(qū)別
  2）直觀的解法給出了解空間樹(shù)規(guī)模大小：(n-1)!巍杈，因?yàn)閺哪膫€(gè)頂點(diǎn)先開(kāi)始都無(wú)所謂忧饭，所以是n-1.
• 直觀的回溯法和分支限界法沒(méi)有本質(zhì)區(qū)別，回溯法也可以借助分支限界法的貪心思想：
  1）回溯法可以借助貪心思想秉氧，找出一個(gè)在貪心操作下的可行解的界
  2）回溯其他分支時(shí)眷昆，回溯法可以借助貪心思想預(yù)測(cè)其他分支的下界
  3）但是如果分支眾多，回溯法每次總是找最優(yōu)汁咏、次優(yōu)等（一個(gè)點(diǎn)到其他點(diǎn)最優(yōu)亚斋、次優(yōu)...），但是實(shí)際上費(fèi)用矩陣并不能在O(1)內(nèi)找到最優(yōu)值攘滩，因?yàn)椴皇桥判虻乃Э設(shè)(lgn)都很難做到，n是頂點(diǎn)的個(gè)數(shù)漂问；——這個(gè)計(jì)算分散開(kāi)了
  分支限界法赖瞒，一次計(jì)算出了所有兒子節(jié)點(diǎn)的下界（但是這個(gè)下界的估算也需要一次性計(jì)算出每一行的最小值）女揭。——這個(gè)計(jì)算時(shí)一起算的
• 直觀的分支限界法與降階的分支限界法栏饮、動(dòng)態(tài)規(guī)劃的區(qū)別
  1）直觀的分支限界法是直接針對(duì)可能的解空間樹(shù)進(jìn)行遍歷的吧兔，按照貪心性質(zhì)（估算的下界最小）袍嬉；這個(gè)是正常的解空間樹(shù)
  2）降階的分支限界法是針對(duì)一條邊的選擇與否境蔼，造成左右兩個(gè)分支界限最大的貪心性質(zhì)選擇的，總是選擇這樣的邊首先加入（估算的下界最兴磐ā）箍土；這個(gè)是經(jīng)過(guò)調(diào)整的解空間樹(shù)
  3）基于降階的分支限界法，本質(zhì)上與動(dòng)態(tài)規(guī)劃類(lèi)似罐监；
  降階的分支限界法吴藻，通過(guò)選擇該邊，轉(zhuǎn)換為了子問(wèn)題的求解弓柱；動(dòng)態(tài)規(guī)劃也是通過(guò)選擇一條邊沟堡，轉(zhuǎn)換成了子問(wèn)題的求解；
  不過(guò)分支限界法是用貪心性質(zhì)進(jìn)行選邊吆你，動(dòng)態(tài)規(guī)劃是是通過(guò)選擇所有可能性的邊計(jì)算出最小的邊弦叶。

1.2.2 分支限界法與最小生成樹(shù)俊犯、最短路徑之間的聯(lián)系（都借助了貪心性質(zhì)）

2.最優(yōu)化模型——整數(shù)規(guī)劃

• c_ij表示頂點(diǎn)v_i和v_j之間的費(fèi)用妇多、距離等。
• x_ij若等于1燕侠，則表示邊v_iv_j在Hamilton回路上者祖；否則就不在。

• 最優(yōu)化模型（整數(shù)規(guī)劃）如下：

  
  

3.基于上下界的分支限界法——求解對(duì)稱(chēng)型TSP

3.1 下界（估算）

• 針對(duì)圖的鄰接矩陣绢彤，將矩陣中每一行最小的元素相加七问，就可得到一個(gè)簡(jiǎn)單的下界b1
• 改進(jìn)：考慮一個(gè)TSP的完整解，在每條路徑上茫舶，每個(gè)城市都有兩條鄰接邊械巡，一條進(jìn)，一條出饶氏。那么讥耗，如果把矩陣中每一行最小的兩個(gè)元素相加除以2（不失一般性，可以假定圖中所有距離權(quán)重都為整數(shù)）疹启，再對(duì)其結(jié)果向上取整古程，就可得到一個(gè)合理的下界b2。（為什么喊崖？試想一種情況：假設(shè)進(jìn)頂點(diǎn)和出頂點(diǎn)的邊都是最小挣磨。在這種巧合下雇逞，就正好是b2）

3.2 上界——貪心

• TSP的任何可行解都是上界，TSP上界的求法是借助貪心方法思想茁裙。
  總是選一條最短的且不形成回路塘砸，但是最終會(huì)形成回路的路徑。

3.3 基于上下界的分支限界法——本質(zhì)上是一樣的

• 通過(guò)貪心思想獲得一個(gè)上界bound
• 針對(duì)一條邊進(jìn)行分支（左邊選擇該邊晤锥、右邊不選該邊）谣蠢，然后對(duì)分支計(jì)算出下界，如果下界超過(guò)上界則剪去該分支

3.4 一個(gè)示例

• step1.計(jì)算出上界 U₁ = 16.
  1->3->5->4->2->1
• step2.假定邊(1, 3)不在TSP回路中查近，即e13 = 0眉踱，此時(shí)，b2 = ((5+3) + (3+6) + (4+2) + (3+4) + (2+3))/2 = 17.5霜威，由于b2 = 17.5 > U1 = 16谈喳，因此邊(1, 3)一定在回路中，即e13 = 1戈泼；
• step3.在e13 = 1的情況下婿禽，假定e12 = 0，此時(shí)b2 = ((1+5) + (6+7) + (1+2) + (3+4) + (2+3))/2 = 17大猛，由于b2 = 17 > U1 = 16扭倾，因此邊(1, 2)一定在回路中，即e12 = 1挽绩；
• step4.在e12 = e13 = 1的情況下膛壹，由于頂點(diǎn)1已有兩條關(guān)聯(lián)邊在最優(yōu)回路中，因此在刪去邊(1, 4)和(1, 5)唉堪，由于邊(2, 3)與邊(1, 2)模聋、(1, 3)形成圈，因此在中刪去邊(2, 3)唠亚，即此時(shí)e14 = e15 = e23 = 0链方；
• step5.在e12 = e13 = 1，e14 = e15 = e23 = 0的情況下灶搜，假定e25 = 1祟蚀，此時(shí)b2 = ((1+3) + (3+9) + (1+2) + (3+4) + (2+9))/2 = 18.5，由于b2 = 18.5 > U1 = 16割卖，因此邊(2, 5)一定不在回路中前酿，即e25 = 0；

• step6.在e12 = e13 = 1究珊，e14 = e15 = e23 = e25 = 0的情況下薪者，由于與頂點(diǎn)2關(guān)聯(lián)的邊有且只有2條在回路中，因此有e24 = 1剿涮，進(jìn)而有e35 = e54 = 1言津，e34 = 0攻人。

  
  

4.基于降階的分支限界法

4.1 問(wèn)題描述

4.1.1 問(wèn)題描述

• c——費(fèi)用矩陣（鄰接矩陣），c_ij表示頂點(diǎn)v_i到頂點(diǎn)v_j的關(guān)聯(lián)邊的長(zhǎng)度悬槽。

4.1.2 費(fèi)用矩陣的特性及規(guī)約

• 令G=(V, E)是一個(gè)帶權(quán)重的有向圖怀吻，l是圖G的一條哈密爾頓回路，c是圖G的費(fèi)用矩陣初婆，則回路上的邊對(duì)應(yīng)于費(fèi)用矩陣c中每行每列各一個(gè)元素蓬坡。
  證明：因?yàn)閘上面的每個(gè)頂點(diǎn)v_i有且僅有一條入邊和出邊，入邊表示費(fèi)用矩陣第i列僅有一個(gè)元素對(duì)應(yīng)磅叛，出邊表示費(fèi)用矩陣第i行僅有一個(gè)元素對(duì)應(yīng)屑咳。
• 費(fèi)用矩陣c的第i行（或第j列）中的每個(gè)元素減去一個(gè)整數(shù)lh_i（或ch_j），得到一個(gè)新的費(fèi)用矩陣c'弊琴。使得c'中第i行（或第j列）中的最小元素為0兆龙，稱(chēng)為費(fèi)用矩陣的行歸約（或列歸約）。稱(chēng)lh_i為行歸約常數(shù)敲董，ch_j為列歸約常數(shù)紫皇。
  

• 對(duì)費(fèi)用矩陣c的每一行和每一列都進(jìn)行行歸約和列歸約，得到一個(gè)新的費(fèi)用矩陣c'腋寨，使得c'中每一行和每一列至少都有一個(gè)元素0聪铺，稱(chēng)為費(fèi)用矩陣的歸約。矩陣c'稱(chēng)為費(fèi)用矩陣c的歸約矩陣萄窜，稱(chēng)常數(shù)h為矩陣c的歸約常數(shù)铃剔。

  
  
• 令G=(V, E)是一個(gè)帶權(quán)重的有向圖，l是圖G的一條哈密爾頓回路脂倦，c是G的費(fèi)用矩陣番宁，w(l)是以費(fèi)用矩陣c計(jì)算的這條回來(lái)的費(fèi)用。如果c'是費(fèi)用矩陣c的歸約矩陣赖阻，歸約常數(shù)為h，w'(l)是以費(fèi)用矩陣c'計(jì)算的這條回路的費(fèi)用踱蠢。則有：
  w(l) = w'(l) + h
• 令G=(V, E)是一個(gè)帶權(quán)重的有向圖火欧，l是圖G的一條最短哈密爾頓回路，c是G的費(fèi)用矩陣茎截，c'是c的歸約矩陣苇侵，G'是與c'對(duì)應(yīng)的圖，c'是G'的費(fèi)用矩陣企锌，則l是G'的一條最短的哈密爾頓回路榆浓。

4.2 分支限界法解決旅行商問(wèn)題

4.2.1 分支方法（二叉分支）

• （分支1）選取沿著某一條邊出發(fā)的路徑，作為進(jìn)行搜索的一個(gè)分支結(jié)點(diǎn)
• （分支2）不沿這條邊的其他所有路徑集合撕攒，作為進(jìn)行搜索的另一個(gè)分支結(jié)點(diǎn)

4.2.2 下界確定

• 假定父親結(jié)點(diǎn)為X陡鹃， w(X)是父親結(jié)點(diǎn)的下界烘浦。
  現(xiàn)在，選擇沿v_iv_j邊向下搜索作為其一個(gè)分支結(jié)點(diǎn)Y萍鲸；
  不沿v_iv_j邊向下搜索作為另一個(gè)分支結(jié)點(diǎn)Y'闷叉。
• 分支Y：
  費(fèi)用矩陣被降階和歸約，歸約常數(shù)為h脊阴，則w(Y) = w(X) + h
• 分支Y'：
  將c_ij置位∞握侧。
  同時(shí)它必然包含費(fèi)用矩陣中第i行的某個(gè)元素和第j列的某個(gè)元素，令d_ij為第第i行和第j列中除c_ij之外的最小元素之和嘿期。
  如果這兩個(gè)最小元素不為零品擎，那么也即按照這兩個(gè)元素進(jìn)行歸約。本質(zhì)上d_ij也是矩陣進(jìn)一步的歸約常數(shù)备徐。
  
  
  因此有w(Y') = w(X) + d_ij孽查。

4.2.3 分支的選擇（貪心）

• 1）沿c_ij 為0的方向選擇，使所選擇的路線盡可能短坦喘。
• 2）在多個(gè)c_ij 為0的方向中盲再，沿d_ij最大的方向選擇，使w(Y')盡可能大
  令S是費(fèi)用矩陣中c_ij 為0的元素集合瓣铣，D_kl是S中使d_ij達(dá)到最大的元素答朋，即：
  
  
  即v_kl就是所要選擇的分支方向。

4.2.4 分支限界法的求解步驟

每個(gè)結(jié)點(diǎn)包含如下信息：
??c——?dú)w約過(guò)后的費(fèi)用矩陣
??k——費(fèi)用矩陣的階數(shù)
??w——下界
??ad——頂點(diǎn)鄰接表
bound——一個(gè)可行解的取值棠笑，當(dāng)做剪枝的標(biāo)準(zhǔn)

• step1.bound = ∞
• step2.建立父親結(jié)點(diǎn)X
  X.c 為費(fèi)用矩陣梦碗，并進(jìn)行歸約，歸約常數(shù)為h
  X.k = n
  X.w = h（下界）
  X.ad頂點(diǎn)鄰接表
• step3.由X.c中所有為0的c_ij蓖救，計(jì)算d_ij
• step4.選擇使d_ij最大的元素d_kl洪规，選擇邊v_kl作為分支方向。
  step5是分支Y'的處理
• step5.（分支1）建立兒子結(jié)點(diǎn)Y'
  Y'.c = X.c循捺，將Y'.c中元素c_kl置為∞斩例，歸約Y'.c
  Y'.ad = X.ad
  Y'.k = X.k
  計(jì)算下界Y'.w，并與bound進(jìn)行比較从橘，根據(jù)比較決定是否插入優(yōu)先隊(duì)列念赶。
  step6-step9是分支Y的處理
• step6.（分支2）建立兒子結(jié)點(diǎn)Y
  Y.c = X.c，根據(jù)下圖將相應(yīng)的邊置為∞
  Y.ad = X.ad
  Y.k = X.k
  
  
  
• step7.刪除Y.c的第k行與第l列元素
  Y.k = Y.k -1
  歸約Y.c
  計(jì)算Y.w
• step8.Y.k為2恰力，直接判斷最短回路的兩條邊叉谜，并登記Y.ad，使Y.k = 0
• step9. Y.w與bound進(jìn)行比較踩萎，處理是否插入優(yōu)先隊(duì)列和更新bound
• step10.取下優(yōu)先隊(duì)列元素作為結(jié)點(diǎn)X停局，若X.k為0，算法結(jié)束；否則轉(zhuǎn)向step3.

如果選擇kl邊董栽，置邊lk為∞是不行的

4.3 一個(gè)示例

5.直觀的回溯法和分支限界法求解

• 1）Hamilton回路經(jīng)過(guò)所有頂點(diǎn)码倦，因此從直觀的回溯法和分支限界法對(duì)于選擇哪個(gè)頂點(diǎn)開(kāi)始搜索沒(méi)有本質(zhì)區(qū)別
• 2）直觀的解法給出了解空間樹(shù)規(guī)模大小：(n-1)!裆泳，因?yàn)閺哪膫€(gè)頂點(diǎn)先開(kāi)始都無(wú)所謂叹洲，所以是n-1.

5.1 實(shí)例

5.2 回溯法——深度優(yōu)先遍歷解空間樹(shù)

• 回溯法的一個(gè)可能改進(jìn)：從某點(diǎn)開(kāi)始按照貪心思想進(jìn)行深度優(yōu)先
• 貪心思想：如果是從頂點(diǎn)1開(kāi)始，則選擇與頂點(diǎn)1最近的4工禾，然后根據(jù)4開(kāi)始运提，選擇可以組成環(huán)路的最近點(diǎn)，直至找到一個(gè)可行解闻葵。一直在某點(diǎn)以最優(yōu)->次優(yōu)->再次等的方式進(jìn)行搜索民泵。前提條件是能夠形成Halmilton回路。
• 界的預(yù)測(cè)：可以提前預(yù)估其下界槽畔，按照分支限界法的那種方式

5.3 分支限界法——廣度優(yōu)先遍歷

5.4 采用基于歸約方式的分支限界法

6.動(dòng)態(tài)規(guī)劃

6.1 刻畫(huà)一個(gè)最優(yōu)解的結(jié)構(gòu)特征（最優(yōu)子結(jié)構(gòu)）

• 假設(shè)s₀s₁s₂...s_n栈妆，其中s₀=s_n，是一條從s₀出發(fā)的最短簡(jiǎn)單回路厢钧。
  那么有s_is_i+1...s_n也是從s_i出發(fā)鳞尔，回到起點(diǎn)s_n的一條最短回路。（cut-and-paste證明）

6.2 遞歸地定義最優(yōu)解的值（重疊子問(wèn)題）

• 設(shè)TSP頂點(diǎn)編號(hào)為0,1,2,...,n-1.
  假設(shè)從頂點(diǎn)0出發(fā)
• d(i, V')定義為從頂點(diǎn)i出發(fā)經(jīng)過(guò)V'中各頂點(diǎn)有且僅有一次早直，最后回到頂點(diǎn)0的最短路徑長(zhǎng)度
• c_ij定義為頂點(diǎn)i到頂點(diǎn)j的距離
  

一個(gè)示例：

費(fèi)用矩陣

遞歸求解子問(wèn)題（重疊子問(wèn)題）

6.3 計(jì)算最優(yōu)解的值寥假，通常采用自底向上的方法

• 假設(shè)頂點(diǎn)總數(shù)為n
  則6.2中表的i范圍是0 ≤ i ≤ n-1，j的范圍是0 ≤ j ≤ 2^n-1 - 1

• 一個(gè)特別的規(guī)律：k表示第k-1位上是否為1霞扬，如下圖所示

  
  

因此將一個(gè)集合轉(zhuǎn)變成了一個(gè)數(shù)與之對(duì)應(yīng)糕韧，數(shù)中對(duì)應(yīng)的為位1，表示該數(shù)包含在集合中喻圃，否則萤彩，該數(shù)不在集合中。

按程序計(jì)算的表格

6.4 利用計(jì)算出的信息構(gòu)造一個(gè)最優(yōu)解

第一個(gè)打印0

7.近似算法

8 遺傳算法

9.模擬退火

10.神經(jīng)網(wǎng)絡(luò)