當預算有限時，如何造出最輕的機器？——用回溯法解“最小重量機器設計問題”

在工程與算法的交匯處，我們常常要回答這樣一個問題：如何在約束下做到“剛剛好”？

今天想和大家聊一個經典但容易被忽略的組合優化問題——最小重量機器設計問題。它不像旅行商那樣廣為人知，卻真實反映了現實中的權衡藝術：在有限成本下，如何讓產品儘可能輕？

而解決它的利器之一，就是我們熟悉的——回溯法。

1. 問題是什麼？
   假設我們要設計一台機器，它由 \(n\) 個部件組成。
   每個部件可以從 \(m\) 家不同的供應商中選擇。
   第 \(i\) 個部件從第 \(j\) 家供應商採購，會帶來兩個屬性：重量 \(w_{ij}\)、價格 \(c_{ij}\)

我們的目標是：
為每個部件選一個供應商；使得總價格不超過預算 \(d\)；同時總重量儘可能小。

這本質上是一個帶約束的最優化問題，屬於 NP-hard 範疇。當 \(n\) 和 \(m\)

1.1 解空間：所有可能的“組裝方案”

首先，我們要明確：這個問題的解空間到底長什麼樣？
每個部件有 \(m\) 種選擇；
共有 \(n\) 個部件；
所有可能的組合數是：\(m^n\)。

比如，3 個部件，每種有 2 家供應商 → 總共 \(2^3 = 8\)

這些方案構成了問題的完整解空間。我們的任務，就是在這些方案中：
篩選出總成本 ≤ 預算 \(d\) 的可行解；
在可行解中，找到總重量最小的那個。

注意：解空間 ≠ 可行解空間。很多組合會超預算，直接被剪掉。

1.2 解空間樹：一棵“決策樹”

為了系統地遍歷所有可能，我們把解空間組織成一棵樹——稱為解空間樹（或狀態空間樹）。
樹的深度：\(n+1\) 層（第 0 層是根，第 1~n 層分別對應第 1~n 個部件的選擇）
每個非葉節點有 \(m\) 個子節點，代表當前部件選擇哪家供應商
從根到葉子的一條路徑，就對應一種完整的組裝方案

舉個例子（\(n=3, m=2\)）：

(根)
/ \
選1號 選2號 ← 第1個部件
/ \ / \
... ... ... ... ← 第2個部件
/ \ / \ / \ / \
... ... ... ... ... ... ← 第3個部件（葉子）

這樣一棵樹，共有 \(m^n\)

1.3 遍歷時，每個節點“記住”了什麼？

在回溯過程中，我們並不是盲目地走到葉子再判斷。為了高效剪枝，每個節點都需要維護當前的狀態信息。

具體來説，當我們處在第 \(k\) 層（即已經為前 \(k-1\)

剪枝策略（關鍵！）

1. 可行性剪枝：
   如果 current_cost > d，説明已經超預算，無需繼續向下搜索，直接回溯。
2. 最優性剪枝（限界）：
   即使還沒超預算，但如果 current_weight ≥ best_weight，
   那麼就算後面全選最輕的部件，也不可能比當前最優解更好——也可以剪掉。
   這些狀態值就像“揹包裏的賬本”，讓我們在探索過程中隨時知道：“還剩多少錢？已經多重了？還有沒有必要繼續？”
3. 我對回溯算法的理解
   回溯法，常被稱作“聰明的暴力搜索”。
   它不像動態規劃那樣依賴重疊子問題，也不像貪心那樣追求一步到位。
   它更像是一個有記憶、會反思的探險家：
   他一步步做選擇（比如“這個部件選哪家？”）；
   每走一步，就檢查當前狀態是否還有希望；
   一旦發現前方無路可走（超預算、不可能更優），就立刻退回上一步，嘗試其他選項；
   直到遍歷完所有可能性，或者提前找到最優解。

回溯的核心三要素：

1. 選擇（Choice）：在當前步驟有哪些可選項？
2. 約束（Constraint）：哪些選擇是合法的？（如預算限制）
3. 目標（Objective）：如何判斷一個解是否“更好”？（如重量更小）

它的優點與侷限：
✅ 優點：
思路直觀，易於實現；
能找到精確最優解（不是近似）；
配合剪枝，效率遠高於純暴力。
❌ 侷限：
時間複雜度仍是指數級（\(O(m^n)\)），只適用於小規模問題；
剪枝效果高度依賴問題結構和數據分佈。
所以，回溯法不是萬能的，但在“小而精”的組合優化場景中，它依然是我們的可靠夥伴。

🧩 結語：在約束中尋找最優，是工程師的日常

最小重量機器設計問題，看似抽象，實則映射了無數現實場景：
電路板選型（成本 vs 功耗）
供應鏈採購（價格 vs 交付時間）
甚至人生選擇（時間 vs 收益）

而回溯法教會我們的，不僅是算法技巧，更是一種思維方式：
在有限資源下，系統性地探索可能性，並及時止損、調整方向。

或許，這才是算法真正迷人的地方。