• 此為課題組所指導(dǎo)本科生和低年級(jí)碩士生學(xué)習(xí)組合優(yōu)化問(wèn)題匯報(bào)
• 所用教材：北京大學(xué)屈婉玲教授《算法設(shè)計(jì)與分析》
• 課程資料：https://www.icourse163.org/course/PKU-1002525003 承諾不用于任何商業(yè)用途，僅用于學(xué)術(shù)交流和分享
• 更多內(nèi)容請(qǐng)關(guān)注許志偉課題組官方中文主頁(yè)：https://JaywayXu.github.io/zh-cn/

1. 貨郎問(wèn)題的分支限界算法求解 （10.4）

1.1. 貨郎問(wèn)題的定義

• 給定一個(gè)城市集合 \(C = \{c_1, c_2, \dots, c_n\}\)，任何兩個(gè)城市之間都有距離 \(d\left(c_i, c_j\right)=d\left(c_j, c_i\right) \in \mathbf{Z}^{+}, 1 \leq i<j \leq n\)。
• 目標(biāo)： 找到一個(gè)城市的排列，使得從一個(gè)城市出發(fā)，訪問(wèn)每個(gè)城市恰好一次，并返回出發(fā)城市，總路徑長(zhǎng)度最短。

1.2. 算法設(shè)計(jì)

• 解向量：
  解: \(1,2, \ldots, n\) 的排列 \(k_1, k_2, \ldots, k_n\) 使得:

• 搜索空間：
  排列樹(shù)結(jié)構(gòu)，每個(gè)結(jié)點(diǎn) \(\langle i_1, i_2, \dots, i_k \rangle\) 表示前 \(k\) 步的路線已確定。

• 約束條件：

  • 已走過(guò)的城市標(biāo)號(hào)放入集合 \(B = \{i_1, i_2, \dots, i_k\}\)。
  • 下一步只能選擇未訪問(wèn)過(guò)的城市：\(i_{k+1} \in \{2, \dots, n\} \setminus B\)。
  • 即每個(gè)節(jié)點(diǎn)只能訪問(wèn)一次

1.3. 代價(jià)函數(shù)與界的定義

• 界 (Bound)： 當(dāng)前已找到的最短巡回路線的長(zhǎng)度。

• 代價(jià)函數(shù)：
  假設(shè)頂點(diǎn) \(c_i\) 出發(fā)的最短邊為 \(l_i\)，\(d_j\) 為已選定的巡回路線中第 \(j\) 段的長(zhǎng)度，則代價(jià)函數(shù)為：

• 前半部分：已走過(guò)的路徑長(zhǎng)度。
• 后半部分：剩余未訪問(wèn)的城市，從每個(gè)城市出發(fā)的最短邊構(gòu)成的下界。

1.4. 代價(jià)函數(shù)示例

1.4. 代價(jià)函數(shù)示例

我們通過(guò)一個(gè)具體路徑的代價(jià)函數(shù)計(jì)算示例，來(lái)更好理解分支限界算法中如何評(píng)估路徑的代價(jià)和下界。

示例路徑及紅色路徑描述

如圖所示，我們假設(shè)貨郎從 1號(hào)城市 出發(fā)，依次訪問(wèn)了 3號(hào)城市 和 2號(hào)城市，形成了部分路徑 \(\langle 1, 3, 2 \rangle\)。現(xiàn)在我們已經(jīng)走到 2號(hào)城市，接下來(lái)需要計(jì)算該路徑的代價(jià)函數(shù)，來(lái)評(píng)估當(dāng)前路徑的花費(fèi)以及剩余部分的下界。

代價(jià)函數(shù)的計(jì)算公式

代價(jià)函數(shù) \(L\) 的通用表達(dá)式如下：

• 已走過(guò)的路徑長(zhǎng)度：
  將已訪問(wèn)的城市之間的路徑距離累加，例如在路徑 \(\langle 1, 3, 2 \rangle\) 中，

  \[1 \to 3：9 \,\, (單位) \]
  \[3 \to 2：13 \,\, (單位) \]

  已走過(guò)的路徑總長(zhǎng)度為：

  \[9 + 13 = 22 \,\, (單位) \]

• 剩余部分的估計(jì)長(zhǎng)度下界：

  • 當(dāng)前停留在 2號(hào)城市，我們需要從 2號(hào)城市出發(fā)選擇一條最短邊。
    2號(hào)城市的最短邊是 \(2 \to 4\)，邊長(zhǎng)為 \(2\)。
  • 在剩余的未訪問(wèn)城市中，還未訪問(wèn)的城市是 4號(hào)城市。從 4號(hào)城市出發(fā)的最短邊也是 \(4 \to 2\)，長(zhǎng)度同樣為 \(2\)。

因此，剩余部分的估計(jì)長(zhǎng)度下界為：

完整代價(jià)函數(shù)值計(jì)算

將已走過(guò)的路徑長(zhǎng)度和剩余部分的下界相加，得到代價(jià)函數(shù)的值：

下界解釋

這個(gè)代價(jià)函數(shù)的結(jié)果表明，無(wú)論之后如何規(guī)劃剩余的路徑，完整路徑的總長(zhǎng)度不會(huì)小于 26。這個(gè)下界幫助算法在搜索時(shí)進(jìn)行剪枝，即當(dāng)其他路徑的代價(jià)超過(guò)該下界時(shí)，就不再繼續(xù)深入搜索該分支。

1.5. 搜索樹(shù)結(jié)構(gòu)

• 初始結(jié)點(diǎn)： 從城市 1 出發(fā)。

• 可選路徑：

  • 第一層：1 號(hào)城市之后可以去 2、3、4。
  • 第二層：假設(shè)選擇了 2 號(hào)城市，則下一步可選 3 或 4。

• 深度優(yōu)先遍歷：

  • 第一條路徑：\(\langle 1, 2, 3, 4, 1 \rangle\)，長(zhǎng)度 \(29\)。

    • 這是第一個(gè)找到的巡回路線，界 \(B = 29\)。

  • 更新界：
    找到路徑 \(\langle 1, 2, 4, 3, 1 \rangle\)，長(zhǎng)度 \(23\)。更新界 \(B = 23\)。

  • 剪枝：
    當(dāng)搜索路徑 \(\langle 1, 3, 2 \rangle\) 的代價(jià)函數(shù)值為 \(26\)，大于當(dāng)前界 \(B = 23\)，停止搜索該分支。

1.6. 實(shí)例運(yùn)行過(guò)程

1. 初始路徑：

   • 路徑 \(\langle 1, 2, 3, 4, 1 \rangle\)，長(zhǎng)度為 \(29\)。

2. 更新路徑：

   • 找到更優(yōu)路徑 \(\langle 1, 2, 4, 3, 1 \rangle\)，長(zhǎng)度為 \(23\)，更新界。

3. 剪枝：

   • 代價(jià)函數(shù)值 \(F = 26\)，停止該分支的搜索。

4. 最優(yōu)解：

   • 找到路徑 \(\langle 1, 3, 4, 2, 1 \rangle\)，長(zhǎng)度 \(23\)。
     • 該路徑與之前的最優(yōu)解長(zhǎng)度相同。

1.7. 算法分析

• 搜索樹(shù)的規(guī)模：

  • 樹(shù)葉的個(gè)數(shù)為 \(O((n - 1)!)\)。
  • 每個(gè)葉片對(duì)應(yīng)一條路徑，每條路徑有 \(n\) 個(gè)結(jié)點(diǎn)。

• 時(shí)間復(fù)雜度：

  • 單個(gè)路徑計(jì)算時(shí)間： \(O(n)\)。
  • 總時(shí)間復(fù)雜度： \(O(n!)\)。
  • 在最壞情況下，與蠻力算法的時(shí)間復(fù)雜度相同。

• 實(shí)際性能：
  通過(guò)剪枝操作，大大減少了實(shí)際搜索空間，因此平均運(yùn)行時(shí)間優(yōu)于蠻力算法。

1.8. 小結(jié)

• 貨郎問(wèn)題的分支限界算法：

  • 約束條件： 只能選擇未訪問(wèn)過(guò)的城市。
  • 代價(jià)函數(shù)： 已走過(guò)的路徑長(zhǎng)度 + 未訪問(wèn)部分的長(zhǎng)度下界。

• 時(shí)間復(fù)雜度： \(O(n!)\)，在最壞情況下與蠻力算法相同，但通過(guò)剪枝可顯著提升平均性能。