• 此為課題組所指導本科生和低年級碩士生學習組合優化問題匯報
• 所用教材：北京大學屈婉玲教授《算法設計與分析》
• 課程資料：https://www.icourse163.org/course/PKU-1002525003
• 承諾不用于任何商業用途，僅用于學術交流和分享
• 更多內容請關注許志偉課題組官方中文主頁：https://JaywayXu.github.io/zh-cn/

1. 連續郵資問題 （10.6）

1.1 問題定義

在連續郵資問題中，給定了 \(n\) 種不同面值的郵票，每個信封至多貼 \(m\) 張郵票。我們的目標是設計一個郵票面值集合，使得從面值 \(1\) 開始，能夠連續支付的郵資區間盡可能大。

• 輸入條件：

  • \(n = 5\)：郵票種類數為 5。
  • \(m = 4\)：每個信封最多可以貼 4 張郵票。

• 目標：

  • 在給定郵票面值的設計下，從 \(1\) 開始，所有整數郵資都能用郵票貼出，且所能覆蓋的連續區間最大。

• 問題示例：

  • 設計1：郵票面值為 \(\{1, 3, 11, 15, 32\}\)。

    • 解釋：
      • 使用最多 4 張郵票進行組合，可以覆蓋郵資區間 1 到 70，即可以支付所有從 1 到 70 的郵資。
      • 例如：
        • 只用面值為 \(1\) 的郵票：最多貼出 \(4 \times 1 = 4\)。
        • 使用郵票面值 \(1\) 和 \(3\)：如 \(3 + 3 + 1 = 7\)。
        • 使用面值 \(11, 15\)，可組合成更大面值。
      • 這個設計成功地貼出了1 到 70 的連續郵資，因此是一個好的設計。

  • 設計2：郵票面值為 \(\{1, 6, 10, 20, 30\}\)。

    • 解釋：
      • 使用最多 4 張郵票，無法貼出所有從 1 開始的郵資。例如：
        • 用 4 張面值 \(1\) 的郵票最多貼出 \(4\)。
        • 想要貼出 \(5\) 時，必須要有四張面值為 \(1\) 的郵票，無法貼出 5。
      • 因此，設計2 無法貼出 完整的連續郵資，是一個不好的設計。

1.2 搜索空間與約束條件

1.2.1 搜索空間

在連續郵資問題的算法設計中，可行解的搜索空間是 郵票面值的所有組合，并滿足以下條件：

• 每個可行解表示為一個 向量：
  $ (x_1, x_2, \dots, x_n) $
  其中，\(x_1\) 一定是 \(1\)，因為面值 1 是確保支付連續區間的最小單位。
• 向量中的面值是 嚴格遞增，即
  \(x_1 < x_2 < \dots < x_n\)。
• 每個信封上最多可以貼 \(m\) 張郵票，用以支付指定的郵資。

1.2.2 約束條件

為了確保連續郵資區間最大化，每個郵票面值的選取需要滿足以下約束：

1. 第一個面值的固定性：

   • \(x_1 = 1\)，因為任何可行的郵資設計都必須能支付 1 單位郵資。

2. 后續面值的選取范圍：

   • 設 \(r_i\) 表示使用 \(i\) 種郵票時，能夠貼出的最大連續郵資區間的上界。
   • 下一個面值 \(x_{i+1}\) 的選取必須滿足：
     \[x_{i+1} \in [x_i + 1, r_i + 1] \]

   • 解釋：
     • \(x_{i+1} \geq x_i + 1\)：因為郵票面值遞增。
     • \(x_{i+1} \leq r_i + 1\)：保證所有 \(r_i + 1\) 以內的郵資能夠支付。若 \(x_{i+1} > r_i + 1\)，則 \(r_i + 1\) 單位郵資將無法支付。

3. 最大化郵資區間的策略：

   • 對于每一層的搜索，當選定了 \(i\) 種郵票的面值 \((x_1, \dots, x_i)\) 后，應確保最大化郵資區間 \([1, r_i]\)，使得在這個區間內的每個郵資都能用 \(i\) 種郵票的組合支付。

1.2.3 舉例說明約束

• 假設前兩種郵票面值：
  \(x_1 = 1\)，\(x_2 = 2\)。

  • 使用最多 4 張郵票時，可以覆蓋的郵資區間為 \([1, 6]\)，即：
    • \(1 = 1\)
    • \(2 = 2\)
    • \(3 = 1 + 2\)
    • \(4 = 2 + 2\)
    • \(5 = 1 + 2 + 2\)
    • \(6 = 2 + 2 + 2\)

• 選擇第三種郵票面值的范圍：

  • 由于 \(r_2 = 6\)，因此第三種郵票的面值 \(x_3\) 必須滿足：
    \[x_3 \in [3, 7] \]

  • 例如，若 \(x_3 = 3\)，則可以使用 \(x_1, x_2, x_3\) 組合來支付更大的連續郵資區間。

1.3 上界 \(r_i\) 的計算

1.3.1 \(r_i\) 的含義

根據上述描述，\(r_i\) 是 前 \(i\) 種郵票所能支付的最大連續郵資區間的上界，即：

• 貼到 \(j\) 的郵資時，使用的郵票數量不超過 \(m\) 張。
• 當嘗試貼郵資 \(j + 1\) 時，需要的郵票數量超過 \(m\) 張，此時 \(j\) 就是 斷點。

這一部分的目標是計算這個最大連續的郵資區間上界 \(r_i\)，即從 1 開始的 最大連續郵資區間 能延伸到哪里。

1.3.2 \(y_i(j)\) 與上界的邏輯關系

在計算 \(r_i\) 時，我們重點依賴于 遞歸函數 \(y_i(j)\)，這個函數表示：
使用前 \(i\) 種郵票組合出郵資 \(j\) 所需的最少郵票數。公式如下：

• 解釋：
  • \(t\)：第 \(i\) 種郵票使用的數量。
  • \(x_i\)：第 \(i\) 種郵票的面值。
  • \(j - t \cdot x_i\)：剩余郵資，需要前 \(i-1\) 種郵票來補齊。
  • \(y_{i-1}(j - t \cdot x_i)\)：剩余部分的最少郵票數。

該公式遞歸地檢查在不超過 \(m\) 張郵票的情況下，如何用最少的郵票組合來支付郵資 \(j\)。

1.3.3 上界 \(r_i\) 的計算過程

根據遞歸函數 \(y_i(j)\)，我們定義了 上界 \(r_i\)，其計算公式如下：

• 解釋：
  1. 找到最大的 \(j\)，使得 \(y_i(j) \leq m\)，即 可以使用不超過 \(m\) 張郵票貼出郵資 \(j\)。
  2. 嘗試支付郵資 \(j + 1\) 時，若 \(y_i(j + 1) > m\)，即 不能在不超過 \(m\) 張郵票的限制內貼出 \(j + 1\)，則 \(j\) 為 斷點。
  3. 我們需要在所有可能的斷點中選擇 最小的那個 \(j\) 作為 \(r_i\)，確保能夠覆蓋最大連續區間。

1.3.4 分析與邏輯

1. 尋找斷點：

   • 對每個 \(j\)，檢查是否能在不超過 \(m\) 張郵票的限制下完成支付。
   • 一旦 \(j + 1\) 無法滿足上述條件，當前 \(j\) 就是上界 \(r_i\)。

2. 為何選擇最小的 \(j\)：

   • 在某些郵票設計下，可能會有多個 斷點，即多個 \(j\) 滿足 \(y_i(j) \leq m\) 且 \(y_i(j + 1) > m\)。我們選擇 最小的 \(j\) 作為 \(r_i\)，確保得到最長的連續區間。

3. 示例分析：

   • 若使用面值為 \(1, 3, 5\) 的郵票，且 \(m = 3\)，當我們嘗試支付 \(j = 9\) 時能夠成功，但支付 \(j + 1 = 10\) 時需要超過 3 張郵票，則斷點為 \(j = 9\)。此時 \(r_i = 9\)。

1.4 部分搜索樹示例與最優解的計算

在這一節，我們通過一個具體的搜索樹示例來說明如何根據不同郵票面值計算出連續郵資的上界 \(r_i\)，并找到最終的最優解。

1.4.1 示例設置

• 郵票種類：\(n = 4\)
• 每信封最多郵票數：\(m = 3\)
• 初始郵票面值：\(x_1 = 1\)

在此示例中，我們需要設計合理的郵票面值，使得能夠貼出的連續郵資區間最大化。每一步都將使用深度優先搜索策略遍歷子樹，并不斷更新可能的解。

1.4.2 搜索樹結構與遞進計算

1. 第一種郵票面值 \(x_1 = 1\)：

   • 用 \(x_1 = 1\) 的郵票最多貼 3 張，可以覆蓋的最大郵資區間為：
     \[r_1 = 3 \quad \text{（即郵資 1, 2, 3）} \]

   • 這意味著，加入更多面值的郵票時，它們的面值必須至少比 \(x_1\) 大 1，即從 2 開始 ，并且最大應該為\(r_1+1=4\) , 因此此節點會分出三個樹枝。

2. 第二種郵票面值 \(x_2 = 2\)：

   • 由深度優先搜索，如果選擇 \(x_2 = 2\)，則最多 3 張郵票可以覆蓋：
     \[r_2 = 6 \quad \text{（郵資 1 到 6）} \]

   • 接下來的郵票面值應至少比 \(x_2\) 多 1，即從 3 開始，且不能超過 \(r_2 + 1 = 7\)。

3. 第三種郵票面值 \(x_3 = 3\)：

   • 若 \(x_3 = 3\)，則用 \(x_1, x_2, x_3\) 的組合最多能貼出：
     \[r_3 = 9 \quad \text{（郵資 1 到 9）} \]

   • 第四種郵票的面值應位于 \([4, 10]\) 之間。

4. 第四種郵票面值 \(x_4 = 4\)：

   • 當 \(x_4 = 4\) 時，使用 1、2、3 和 4 這些郵票的組合，可以貼出的最大連續區間為：
     \[r_4 = 17 \quad \text{（郵資 1 到 17）} \]

1.4.3 搜索樹的遍歷與剪枝

在搜索樹中，每一層代表一個郵票面值的選擇，而每個節點表示當前面值的累計狀態。我們采用深度優先遍歷來找到最優解。在遍歷過程中，如果發現某條路徑上的解不優于已有解，則會執行剪枝操作，避免冗余計算。

1. 節點 (1, 4, 5, 6)：

   • 貼出的最大連續區間為 18。

2. 節點 (1, 4, 6, 7)：

   • 通過進一步的搜索，我們找到一個更優的解，其連續區間為：
     \[\{1, \ldots, 21\} \]

1.4.4 最優解

• 最優解的郵票面值組合為：
  \[X = \langle 1, 4, 6, 7 \rangle \]

• 最大連續區間為：
  \[\{1, \ldots, 21\} \]

這表明，使用面值為 1、4、6、7 的郵票設計，在每封信最多貼 3 張郵票的情況下，可以覆蓋的最大連續郵資區間為 1 到 21。

1.5 小結：回溯算法全面解析

(1) 回溯算法的適用范圍

回溯算法是一種系統化的搜索策略，廣泛應用于組合問題、優化問題以及約束滿足問題。具體應用場景包括：

• 八皇后問題：尋找所有不互相攻擊的皇后擺放方式。
• 旅行商問題：尋找訪問所有城市且路徑最短的旅行路徑。
• 背包問題：在容量有限的情況下，選擇物品使得總價值最大。
• 數獨求解和其他復雜的排列組合問題。

(2) 求解條件：多米諾性質

在回溯算法中，多米諾性質要求每一步選擇都能夠自然銜接后續步驟。每一個解的子結構是后續完整解的一部分。例如，在旅行商問題中，選擇一個城市路徑后，后續城市的路徑構建依賴于當前路徑的選擇。

(3) 解的表示與構建過程

• 解向量：使用向量來表示問題的解，如 \((x_1, x_2, \ldots, x_i)\) 表示解的部分結構。隨著搜索的深入，解的向量會不斷擴展，直到形成完整解。
• 通過逐步擴展向量的方式，保證了算法的系統性與邏輯性。

(4) 回溯條件

1. 搜索問題的條件：

   • 滿足約束條件才是可行解，否則立即回溯。
     例如，在八皇后問題中，兩個皇后不應在同一行、列或對角線。

2. 優化問題的條件：

   • 代價函數：除了約束條件，還需計算解的代價，通過代價函數找到最優解。
     例如，在旅行商問題中，代價函數是路徑的總長度，目標是使其最小。

• 代價函數裁剪的作用：
  若發現某分支中的解代價大于當前最優解，則立即剪枝，停止進一步搜索。
  例如，若某路徑的部分長度已經大于當前已知的最短路徑，則無需繼續探索該路徑。

(5) 多種分支策略

根據問題性質，可以選擇不同的分支策略：

• 深度優先搜索 (DFS)：優先深入探索路徑的盡頭。這適用于需要盡快找到一個可行解的情況。
• 廣度優先搜索 (BFS)：按層次擴展所有可能解，適用于尋找最優解，但耗費更多空間。
• 啟發式搜索：使用特定啟發函數來引導搜索。
  例如，A*算法在路徑規劃中使用估計代價來優先訪問可能的最優路徑。
• 寬深結合策略：交替使用DFS和BFS，在保證效率的同時平衡內存消耗。

(6) 結點狀態分類

在搜索樹的遍歷中，結點狀態可分為：

• 白色結點：未被訪問的結點。
• 灰色結點：當前正在遍歷的結點。
• 黑色結點：已經處理完畢的結點，不再需要訪問。

(7) 算法時間復雜度分析

回溯算法的時間復雜度取決于：

• 每個結點的工作量 \(p(n)\)：即在某個結點上的計算代價。
• 結點個數 \(f(n)\)：搜索樹中的總結點數量。

時間復雜度：

• 最壞情況下：時間復雜度通常為指數級，例如 \(O(2^n)\)，和蠻力算法類似。
• 平均情況下：由于剪枝策略的應用，實際運行時間要比蠻力算法更好。

(8) 降低時間復雜度的策略

1. 優先策略設計：

   • 優先選擇結點較少的分支或潛在解更多的路徑。
   • 例如，在背包問題中，可以優先探索價值最高的物品組合。

2. 利用對稱性剪枝：

   • 如果搜索樹具有對稱結構，可以只探索一部分解。例如，在八皇后問題中，探索一半子樹即可推導另一半解。

3. 問題分解：

   • 將規模為 \(n\) 的問題分解為 \(k\) 個子問題，每個子問題的規模為 \(\frac{n}{k}\)。
   • 每個子問題的復雜度為 \(O(2^{n/k})\)，總復雜度為：
     \[T(n) = k \cdot c \cdot 2^{n/k} + O(2^{n/k}) = O(2^{n/k}) = o(2^n) \]

   • 這種方法有效降低了整體復雜度，提升了解決問題的效率。

(9) 回溯算法的優勢與局限

• 優勢：

  • 空間復雜度低：回溯算法通常只需維護當前路徑及少量狀態信息，因此空間開銷較小。
  • 靈活性高：適用于各種組合問題和約束問題。

• 局限：

  • 時間復雜度高：在最壞情況下，仍然是指數時間復雜度。
  • 路徑依賴性：算法的效率很大程度上依賴于分支策略和剪枝規則的設計。

(10) 小結

回溯算法是一種功能強大的求解策略，廣泛用于組合搜索問題和優化問題。其核心思想是通過深度優先搜索和剪枝策略在解空間中高效地探索解集。通過引入代價函數和多種搜索策略，回溯算法能夠在復雜度高的問題中找到接近最優的解。

在實踐中，通過設計優良的剪枝策略和利用問題的對稱性，可以大大提升回溯算法的效率，減少不必要的搜索路徑。同時，通過分解問題，可以進一步降低算法的時間復雜度。這些優化方法確保了回溯算法不僅適用于理論研究，更能在實際問題求解中展現出色的性能。