理論知識

1. 介紹

為什么分析演算法？

• 改進演算法
• 選擇演算法

分析演算法的指標？

• Correctness（正確性）
  • 對于每一個合法輸入，演算法都會在有限的時間內輸出一個滿足要求的結果
• Amount of work done（時間復雜度）
• Amount of space used（空間復雜度）
• Simplicity（簡單性）
  • 盡管并非總是如此，但通常情況下，最簡單，最直接的解決問題的方法并不是最有效的， 然而，演算法的簡單性是期望的特征，
  • 它可以使驗證演算法的正確性更加容易，并且使撰寫，除錯和修改演算法程式變得更加容易，
  • 選擇演算法時應考慮生成除錯程式所需的時間，但是如果要經常使用該程式，則其效率可能是選擇的決定因素，
• Optimality（最優性）
  • 我們可以證明定理確定了解決問題所需的運算元的下限，然后，執行該數量操作的任何演算法都是最佳的

演算法的完整開發步驟：

1. Statement of the problem
2. Development of a Model
3. Design of the algorithm
4. Correctness of the algorithm
5. Implementation
6. Analysis and complexity of the algorithm
7. Program testing
8. Documentation

2. 分而治之（分治、減治、變治）

1. 分治：將原始問題(難以解決的大問題)分解為若干個規模較小的相同的子問題，在逐個解決各個子問題的基礎上，得到原始問題的解，

• MAXMIN 問題
• 二分搜索
• 合并排序
• 尋找第K小的元素
• 大整數的乘法
• 矩陣相乘

2. 減治：一個問題給定實體的解和同樣問題較小實體的解之間的關系，(利用了解之間的關系，也就是說可以減少相應的計算，也可以說是一種時空平衡)
   • 分治法是分解的部分需要進行分開的單獨計算(需要計算兩遍)，而減治法則利用了"一個問題給定實體的解和同樣問題較小實體的解之間的關系"從而減少了計算量，

• 減去一個常量：
  • 插入排序
  • 快速排序(每一次運行一次劃分演算法都只是排好了一個元素)
  • 深度優先查找
  • 廣度優先查找
  • 拓撲排序
  • 生成排列
  • 生成子集
• 減去常量因子：
  • 折半查找
  • 假幣問題
• 減可變規模：
  • 二叉查找樹

3. 變治

• 變換為同樣問題的一個更簡單或者更方便的實體：實體化簡
  • 檢驗陣列中元素的惟一性 – 實體化簡_預排序
  • 模式計算 – 實體化簡_預排序
  • AVL樹 – 二叉排序樹
• 變換為同樣實體的不同表現：改變表現
  • 2-3樹、2-3-4樹 – 二叉排序樹
  • 堆和堆排序
  • 霍納法則 – 多項式的計算
• 變換為另一個問題的實體，這種問題的演算法是已知的：問題化簡
  • 背包問題 – 線性規劃

3. 動態規劃

動態規劃是解決多階段決策程序最優化的一種方法，

多階段決策問題：

• 由于它的特殊性，可將程序劃分為若干互相聯系的階段；
• 在它的每一個階段都需要作出決策，并且一個階段的決策確定以后，常影響下一個階段的決策，從而影響整個程序的活動路線；
• 各個階段所確定的決策就構成一個決策序列，通常稱為一個策略；
• 每一個階段可供選擇的決策往往不止一個，對應于一個策略就有確定的活動效果；
• 多階段決策問題，就是要在允許選擇的那些策略中間，選擇一個最優策略，使在預定的標準下達到最好的效果，

動態規劃最優化原理：

作為整個程序的最優策略具有這樣的性質：即無論過去的狀態和決策如何，對前面的決策所形成的狀態而言，余下的諸決策必須構成最優策略，

動態規劃與與窮舉法的對比：

1. 減少了計算量
2. 豐富了計算結果
   • 求出的不是一個最優策略，而是一族的最優策略，（參見動態規劃最優化原理）

動態規劃解題思路：

1. 首先確定狀態變數和決策變數；
2. 根據決策變數定義狀態變數之間的狀態轉移方程；
3. 寫出求解變數的遞推關系式；
4. 定義表格，大小為狀態變數 X 決策變數 X 決策次數，根據遞推關系式，逐步使用最優決策及其相應的狀態填表，最終得到最優解及其決策路線，

4. 貪心演算法

貪心演算法所做的每一步選擇都必須滿足：

1. 可行的：必須滿足問題的約束
2. 區域最優：是當前步驟中所有可行性選擇中最佳的區域選擇
3. 不可取消：選擇一旦做出，在演算法的后面步驟中就無法改變了

最優子結構：對于一個問題，如果它的一個最優解包含了其子問題的最優解，則稱該問題具有最優子結構，

什么是擬陣(Matroids)：

擬陣理論不能完全覆寫所有的貪心演算法（如赫夫曼編碼問題），但它可以覆寫大多數具有實際意義的情況，

擬陣是滿足條件的一個序對，滿足交換性質和遺傳性質，

擬陣的通用貪心解法：

Greedy (M, w) {
  A ← ?;
  sort MS into monotonically decreasing order by weight w;
  while (MS ≠ ?) {
    x ← getMax(MS);
    if ( A ∪ {x} ∈ Ml )
      A ← A ∪ {x};
  }
  return A;
}

5. 回溯演算法

• 任何難問題，均可通過窮盡搜索數量巨大但有限多個可能性而獲得一個解，
• 大多數難問題都不存在用窮盡搜索之外的方法來解決問題的演算法，
• 產生了開發系統化的搜索技術的需要，并且希望能夠將搜索空間減少到盡可能的小，
• 組織搜索的一般技術之一是回溯法，這種演算法設計技術可以被描述為有組織的窮盡搜索，它常常可以避免搜索所有的可能性，

回溯法的基本思想：

• 針對所要做的選擇構造一棵所謂的狀態空間樹，樹的每一層節點代表了對解的每一個分量所做的選擇，
• 用深度優先法搜索狀態空間樹，
• 在狀態空間樹中的任一節點，滿足一定條件的情況下，搜索回溯，

一般回溯法：

1. v ← Φ
2. flag ← false
3. backrec(1)
4. if flag then output v
5. else output “no solution”

procedure backrec (k)
  for 每個 x ∈ Xk
    xk ← x; 將xk加入v
    if v 為最終解 then set flag ← true and exit
    else if v 是部分解 then backrec(k+1)
  end for

6. 分支定界

分支定界法的主要思想： 最優化問題是根據某些約束尋求目標函式的最大或最小值，可以利用回溯的思想，且回溯的思想得到進一步的強化，和回溯法相比，分支定界法需要兩個額外的條件：

1. 對于一棵狀態空間樹的每一個節點所代表的部分解，我們要提供一種方法，計算出通過這個部分解繁衍出的任何解在目標函式上的最佳值邊界，
2. 目前求得的最佳解的值，

分支定界解題思路：

1. 構造一個搜索樹；
2. 定義遍歷搜索樹的原則：前進、分支、回溯、剪枝；
3. 不斷更新演算法的界，

7. NP 完備

• P 問題(easy to find)：多項式時間內可解決的問題，當然在多項式時間是可驗證的
• NP 問題(easy to check)：非確定性多項式時間可解決的問題，但是在多項式時間是可驗證的

P 類問題是可以在多項式時間內解決并驗證的一類問題，NP 類問題是可以多項式時間驗證但是不確定能否在多項式時間內解決的一類問題，

我們通常將多項式時間看作是計算機解決問題的分水嶺，因為超過多項式時間之后時間消耗上就不太好接受了，

P=NP 問題在表達什么：是否所有 NP 類問題都可以在多項式時間內解決并驗證，也就是轉化為 P 類問題，

雖然目前 P=NP 問題還沒有被證明或者證偽，但是存在不成立的傾向，即 NPC 問題的發現，

NPC 問題的兩個基本特征定義：

1. NPC 問題屬于 NP 問題；
2. 對于所有 NP 問題都可以歸約化到它，

NP-Hard 問題是滿足 NPC 問題定義的第二條，但不滿足第一條，也就是說所有 NP 問題可以歸約化到 NPH 問題，但是 NP-Hard 問題不一定是 NP 問題，所以 NPH 問題比 NPC 問題更難，NPH 至少和 NPC 一樣難，但是不一定可以在多項式時間內驗證，所以可能難于 NP，

• 在 P=NP 成立和不成立情況下的集合關系

8. 近似演算法

當 NP 類問題的輸入極大時，要求該問題的最優解，演算法的執行時間將會是指數級別的，這時，我們很難找到問題的最優解(即使能夠找到，花費的代價也是極大的)，因此我們通常會選擇在多項式時間內再到問題的一個近似解，

• 多項式近似方案 PTAS (Polynomial-Time Approximation Scheme)：若對于每一個固定的 ε>0，演算法的運行時間以實體 I 的規模的多項式為上界，
• 完全多項式近似方案 FPTAS (Fully Polynomial-Time Approximation Scheme)：在 PTAS 的基礎上，我們進一步要求演算法 Aε，即演算法 Aε 的運行時間以實 I 的規模和 1/ε 的多項式為上界，

FPTAS 被認為是最值得研究的近似演算法，僅有極少的 NP-Hard問題存在 FPTAS

9. 隨機演算法

• Monte Carlo 演算法：Monte Carlo 演算法每次都能得到問題的解，但不保證所得解的準確性，
• Las Vegas 演算法：Las Vegas 演算法不會得到不正確的解，一旦用拉斯維加斯演算法找到一個解，這個解就一定是正確解，但有時用拉斯維加斯演算法找不到解，

可以在Monte Carlo演算法給出的解上加一個驗證演算法，如果正確就得到解，如果錯誤就不能生成問題的解，這樣Monte Carlo演算法便轉化為了Las Vegas演算法，

10. 啟發式演算法

• 不以達到最優性條件或找到理論上的精確最優解為目標；
• 對目標函式和約束函式的要求通常十分寬松；
• 演算法思想都是來自對某種自然規律的模仿，具有人工智能的特點；
• 這些演算法的理論作業相對薄弱，一般不能保證收斂到最優解，但是實用性強，

1. 遺傳演算法(Genetic Algorithm，GA)
   • 模仿生物種群中優勝劣汰的選擇機制，通過種群中優勢個體的繁衍進化來實作優化的功能，
2. 禁忌搜索(Tabu Search，TS)
   • 將記憶功能引入到最優解的搜索程序中，通過設定禁忌區阻止搜索程序中的重復，提高尋優程序的搜索效率，
3. 模擬退火(Simulated Annealing，SA)
   • 模擬熱力學中退火程序能使金屬原子達到能量最低狀態的機制，通過模擬的降溫程序按波爾茲曼方程計算狀態間的轉移概率來引導搜索，使演算法具備很好的全域搜索能力，
4. 蟻群演算法(Ant Search，ACO)
   • 借鑒螞蟻群體利用資訊素相互傳遞資訊來實作路徑優化的機理，通過記憶路徑資訊素的變化來解決組合優化問題，
5. 粒子群優化演算法(Particle Swarm Optimization ，PSO)
   • 模擬鳥類和魚類群體覓食遷徙中，個體與群體協調一致的機理求解實數優化問題，
6. 人工神經網路(Artificial Neural Networks，ANN)
   • 從資訊處理角度對人腦神經元網路進行模擬，人工神經網路是一種智能運算模型，由大量的節點(神經元)相互聯接構成，每個節點包含一種指定的激勵函式，每兩個節點間的連接用權重來加權，權重通 過一定的機制(如BP演算法)來調整，

判斷題

1、一個正確的演算法，對于每個合法輸入，都會在有限的時間內輸出一個滿足要求的結果，（對）

2、NP 完全問題比其他所有 NP 問題都要難，（錯）

錯：NP問題分為NP-hard問題和NP完全問題，NP完全問題是最難的，但是NP-hard問題又包含NP完全問題，
錯：NP完全問題至少同其他所有NP問題一樣難，

3、回溯法用深度優先法或廣度優先法搜索狀態空間樹，（錯）

錯：回溯法用深度優先法搜索狀態空間樹，

4、在動態規劃中，各個階段所確定的策略就構成一個策略序列，通常稱為一個決策 ，（錯）

錯：在動態規劃中，各個階段所確定的決策構成一個決策序列，通常稱為一個策略，

5、P類和NP類問題的關系用P?NP來表示是錯誤的，（錯）

錯：P中所有問題均屬于NP，
P：存在求解判定問題P1的多項式時間演算法，
NP：對P1的每一個肯定實體均存在一個多項式時間內的驗證，
NP-Complete：P1是一個NP問題，且NP中所有問題都可以多項式轉化為P1.
NP-Hard：NP中所有問題都可以多項式轉化為P1，但是P1不一定是一個NP問題，
NP-Hard問題范圍大于NP-Complete問題范圍，

6、若近似演算法A求解某極小化問題一實體的解為Sa，且已知該問題的最優解為Sa/3，則該近似演算法的性能比為3，（錯）

錯：性能比是所有實體可能的精確率的上界，3只是這一實體的精確率，不是所有實體的，

7、通常來說，演算法的最壞情況的時間復雜性比平均情況的時間復雜性容易計算，（對）

8、若P2多項式時間轉化為(polynomial transforms to)P1 ，則P2至少與P1一樣難，（錯）

錯：應該是p1至少和p2一樣難，有可能p1更難，
總是可以在可比時間內用P1的演算法解決P2，但不能說P1和P2一樣難，事實上，有時候可能P2簡單而P1更難，
可以將P1比作NPC問題，P2比作NP問題，NPC問題至少和NP一樣難，但是可能難于NP，

9、快速排序演算法的平均時間復雜度是O(nlogn)，使用隨機化快速排序演算法可以將平均時間復雜度降得更低，（錯）

錯：排序演算法的最快時間復雜度就是O(nlogn)

10、基于比較的尋找陣列A[1,…,n]中最大元素的問題下屆是Ω(n/3) ，（錯）

對：下界理論：問題的下界不唯一，越高越好，演算法最優：下界=上界
幾個問題的下界：
排序問題：Ω(nlogn)
找最大：Ω(n/2)或Ω(n-1)
找最大最小：Ω(3n/2-2)
找第二大元素：Ω(n+logn-2)

11、O(f(n))+O(g(n))=O(min{f(n),g(n)})，（錯）

錯，應該是max，O代表的是演算法的上界，

12、若f(n)=Ω(g(n))，g(n)=Ω(h(n))，則f(n)=Ω(h(n))，（對）

對：Ω相當于小于等于，

13、若f(n)=O(g(n))，則g(n)=Ω(f(n))，（對）

對：O相當于大于等于，

14、貪婪技術所做的每一步選擇所產生的部分解，不一定是可行性的，（錯）

錯：貪心演算法每一步必須滿足：可行的（即它必須滿足問題的約束）、區域最優、不可撤銷，
貪心演算法通常包含一個用以尋找區域最優解的迭代程序，在某些實體中這些區域最優解轉變成了全域最優解，而在另外一些實體中則無法找到全域最優解，

15、LasVegas 演算法只要給出解就是正確的，（對）

對：拉斯維加斯演算法不會得到不正確的解，一旦用拉斯維加斯演算法找到一個解，這個解就一定是正確解，但有時用拉斯維加斯演算法找不到解，與蒙特卡羅演算法類似，拉斯維加斯演算法找到正確解的概率隨著它所用的計算時間的增加而提高，對于所求解問題的任一實體，用同一拉斯維加斯演算法反復對該實體求解足夠多次，可使求解失敗的概率任意小，

16、一個完全多項式近似方案是一個近似方案{Aε}，其中每一個演算法Aε在輸入實體I的規模的多項式時間內運行， （錯）

錯：題目中定義的是多項式近似方案，
完全多項式近似方案：是一個近似方案{A_ε}，其中每一個演算法A_ε在輸入實體I的規模和1/ε兩者的多項式時間內運行

簡述題

1、二叉查找樹屬于減治策略的三個變種中的哪一個的應用?什么情況下二叉查找樹表現出最差的效率?此時的查找和插入演算法的復雜性如何?

1. 二叉查找樹屬于減可變規模變種的應用，
2. 當先后插入的關鍵字有序時，構成的二叉查找樹蛻變為單支樹，樹的深度等于n，此時二叉查找樹表現出最差的效率，
3. 查找和插入演算法的時間效率都屬于Θ(n)，

2、何謂偽多項式演算法?如何將一 Monte Carlo 演算法轉化為 Las Vegas 演算法?

1. 若一個數值演算法的時間復雜度可以表示為輸入數值N的多項式，但其運行時間與輸入數值N的二進制位數呈指數增長關系，則稱其時間復雜度為偽多項式時間，
2. Las Vegas演算法不會得到不正確的解，一旦用拉斯維加斯演算法找到一個解，這個解就一定是正確解，但有時用拉斯維加斯演算法找不到解，
3. Monte Carlo演算法每次都能得到問題的解，但不保證所得解的準確性，
4. 轉化：可以在Monte Carlo演算法給出的解上加一個驗證演算法，如果正確就得到解，如果錯誤就不能生成問題的解，這樣Monte Carlo演算法便轉化為了Las Vegas演算法，

3、構造 AVL 樹和 2-3 數的主要目的是什么?它們各自有什么樣的查找和插入的效率?

1. 當先后插入的關鍵字有序時，構成的二叉查找樹蛻變為單支樹，樹的深度等于n，此時二叉查找樹表現出最差的效率，為了解決這一問題，可以構造AVL樹或2-3樹，使樹的深度減小，一棵AVL樹要求它的每個節點的左右子樹的高度差不能超過1，2-3樹和2-3-4樹允許一棵查找樹的單個節點不止包含一個元素，
2. AVL樹在最差情況下，查找和插入操作的效率屬于Θ(logn)，2-3樹無論在最差還是平均情況下，查找和插入的效率都屬于Θ(logn)，

4、寫出 0/1 背包問題的一個多項式等價(Polynomial Equivalent)的判定問題，并說明為什么它們是多項式等價的，

1. 0/1背包問題：從M件物品中，取出若干件放在空間為W的背包里，給出一個能獲得最大價值的方案，每件物品的體積為W1，W2……Wn，與之相對應的價值為P1,P2……Pn，+
2. 判定問題I：從M件物品中，取出若干件放在空間為W的背包里，是否存在一個方案，所獲價值≥P*？，每件物品的體積為W1，W2……Wn，與之相對應的價值為P1,P2……Pn，
3. 若判定問題I存在多項式時間的解法，則反復呼叫該演算法就可以在多項式時間內解決0/1背包的優化問題，因而這個判定問題與原問題多項式等價，

5、下面問題是否屬于 NP 問題?為什么?

問題表述:給定圖𝐺 = (𝑁, 𝐴)中的兩個點𝑝、𝑞，整數𝑐和𝑡，圖𝐺中每條邊的長度𝑐𝑖𝑗及便利這條邊的時間
𝑡𝑖𝑗，問圖𝐺中是否存在一條由𝑝到𝑞的路徑，使得其長度大于𝑐，且遍歷時間小于𝑡?

這個問題屬于NP問題，因為若給出該問題的一個解，可以在多項式時間內檢驗這個解的正確性，如給出一條由p到q的路徑，可以在多項式時間內計算出它的長度及遍歷時間，然后分別與C和t進行比較，從而可以判斷這個解的對錯，

分治題

一、陣列中的逆序對

同力扣題：劍指 Offer 51. 陣列中的逆序對

思想：使用分治法，利用歸并排序，使用歸并時右邊大于左邊的次數即可計算逆序數目，

時間復雜度的迭代公式為：

• T(n) = 1, n=1；
• T(n) = 2T(n/2) + O(n), n>1

因此演算法的時間復雜度為 T(n)=O(nlogn)；蠻力法的時間復雜度為 O(n^2)，當 n 數目較大時，分治法計算規模遠小于蠻力法，

• go 語言原始碼以及注釋：

func reversePairs(nums []int) int {
	count := MergeSort(nums, 0, len(nums)-1) // 使用歸并排序來計算逆序數目
	return count
}

// 合并 [l,r] 兩部分資料，mid 左半部分的終點，mid + 1 是右半部分的起點
func merge(arr []int, l int, mid int, r int) int {
	// 因為需要直接修改 arr 資料，這里首先復制 [l,r] 的資料到新的陣列中，用于賦值操作
	temp := make([]int, r-l+1)
	for i := l； i <= r； i++ {
		temp[i-l] = arr[i]
	}

	// 指向兩部分起點
	left := l
	right := mid + 1

	// 逆序的數目
	count := 0

	for i := l； i <= r； i++ {
		// 左邊的點超過中點，說明只剩右邊的資料
		if left > mid {
			arr[i] = temp[right-l]
			right++
			// 右邊的資料超過終點，說明只剩左邊的資料
		} else if right > r {
			arr[i] = temp[left-l]
			left++
			// 左邊的資料大于右邊的資料，選小的數字，即右邊的資料，此時存在逆序
		} else if temp[left-l] > temp[right-l] {
			arr[i] = temp[right-l]
			right++
			count += mid - left + 1 // 逆序的數目為 mid + 1 -left
			// 否則選左邊的資料，沒有逆序
		} else {
			arr[i] = temp[left-l]
			left++
		}
	}

	return count
}

func MergeSort(arr []int, l int, r int) int {
	if l >= r {
		return 0
	}

	// 遞回向下
	mid := (r + l) / 2
	leftCount := MergeSort(arr, l, mid) // 左半部分的逆序數目
	rightCount := MergeSort(arr, mid+1, r) // 右半部分的逆序數目
	// 歸并向上
	crossCount := merge(arr, l, mid, r) // 交叉項的逆序數目
	return leftCount + rightCount + crossCount
}

二、多數元素

同力扣題：169. 多數元素

思想：使用變治法，利用預排序，之后遍歷求解多數元素，

因此演算法的時間復雜度為 T(n)=O(nlogn)；蠻力法的時間復雜度為 O(n^2)，當 n 數目較大時，變治法計算規模遠小于蠻力法，

• go 語言原始碼以及注釋：

func majorityElement(nums []int) int {
	sort.Ints(nums) // 首先排序

	majCount := 1 	// 多數元素的個數
	maj := nums[0]	// 多數元素
	curCount := 1 	// 當前元素的個數
	cur := nums[0]	// 當前元素

	for i := 1； i < len(nums)； i++ {
		if cur == nums[i] {
			curCount++ // 當前元素的個數加一
		} else {
			// 更新多數元素
			if curCount > majCount {
				majCount = curCount
				maj = cur
			}

			// 更新當前元素
			curCount = 1
			cur = nums[i]
		}
	}

	// 更新多數元素
	if curCount > majCount {
		majCount = curCount
		maj = cur
	}

	return maj
}

動態規劃題

一、生產庫存問題

• 共需要四次決策：k=1，2，3，4
• 需求量為：Need_k, nk=2，3，2，4
• 狀態變數為月初庫存：Reservation_k, rk=0，r2，r3，r4，0
• 決策變數為生產量：Production_k, pk=p1，p2，p3，p4

寫出狀態轉移方程：rk+1 = rk + pk - nk

每月的費用為：CurCost_k

• cck = 0.5 (rk - nk), pk=0
• cck = 3 + pk + 0.5 (rk - nk), pk>0

則遞推關系式為 k~n 月的最優費用為：Cost_k, ck = min{ck+1 + cck}

且 c5=0，c1 即為所求的最優解，

將三維表（狀態變數 X 決策變數 X 決策次數），列為多個二維表（狀態變數 X 決策變數），其中某狀態下的最優決策使用紅色標出，

• k=4, n4=4, r5=r4+p4-n4=0, 且 c4=c5(r5)+cc4

• k=3, n3=2, r4=r3+p3-n3, 且 c3=c4(r4)+cc3

• k=2, n2=3, r3=r2+p2-n2, 且 c2=c3(r3)+cc2

• k=1, n1=2, r2=r1+p1-n1, 且 c1=c2(r2)+cc1

部分省略，其中

• 最優成本為 20.5
• 最優決策為：5->0->6->0
• 最優狀態為：0->3->0->4->0

二、專案投資問題

• 共需要三次決策：k=1，2，3
• 狀態變數為專案 k~n 的投資額：X_k
• 決策變數為專案 k 的投資額：U_k
• 專案 k 投資 U_k 的盈利為：g_k(U_k)
• 專案 k~n 投資 X_k 的盈利為：f_k(X_k)

寫出狀態轉移方程：X_k+1 = X_k - U_k

則遞推關系式為投資專案 k~n 的最優利潤為：f_k(X_k)=max{g_k(U_k) + f_k+1(X_k+1)}

且 f_1(8) 即為所求的最優解，

將三維表（狀態變數 X 決策變數 X 決策次數），列為多個二維表（狀態變數 X 決策變數），其中某狀態下的最優決策使用紅色標出，

• k=3

• k=2

• k=1

部分省略，其中

• 最優理論為 140
• 最優決策為：4->4->0
• 最優狀態為：8->4->0

分支定界題

一、網路搭建問題

1. 可以根據線路(l1,l2,…,lm)的取舍構建一棵m層二叉搜索樹，第i層的所有左分支表示鋪設線路li，右分支則表示不鋪設，如果存在可行解，遍歷此二叉搜索樹即可找到最優解，
2. 遍歷原則：
   • 前進：當前節點未被剪枝并且仍有子節點即可繼續前進，
   • 分支：先遍歷左分支，后遍歷右分支，
   • 回溯：左右分支都被遍歷時回傳父節點，
   • 剪枝：剪枝條件如下：
     1. 有環路
     2. 當前地井數 + 地井數下界 > UMAX
     3. 當前跨區鋪設線路數 + 跨區鋪設線路數下界 > DMAX
     4. 當前費用 + 費用下界 >= 已知最優方案的費用
3. 子問題的下界為費用下界、地井數下界、跨區線路數下界，費用下界是根據剩余站點數量定義的，累計最小的路線花費即可得到，由于限制被極度榷訓，所以非常粗糙，但是正確有效，另外兩個下界也類似，父問題的上界是已知最優方案的費用，顯然正確有效，

按費用從小到大排序所有路線l1,l2,...,lm
計算子問題下界：
	1，費用下界：剩余站點數量->最小花費	#累計最小的線路花費即可得到，下同
	2，地井數下界：剩余站點數量->最小地井數
	3，跨區線路數下界：剩余站點數量->最小跨區線路數
search(空集, l1)
回傳最優結果

def search(線路集合S，當前線路l):
	判斷線路集合S是否合格，條件如下：
		1，無環路
		2，當前地井數 + 地井數下界 <= UMAX
		3，當前跨區鋪設線路數 + 跨區鋪設線路數下界 <= DMAX
		4，當前費用 + 費用下界 < 已知最優方案的費用
	如果合格：
		當前網路已經覆寫所有站點:
			記S為已知最優
		否則若剩下的線路數有可能使所有站點構成網路:
			search(S ∪ {l}, l的下一條路線)
			search(S, l的下一條路線)

二、貿易關稅問題

1. 可以根據除A外的51個國家定義一棵若干層二叉搜索樹，每個節點的左分支表示選擇其代表的國家為下一個貿易順序上的國家，右分支則表示不選擇，構造搜索樹需要兩個輔助變數，之前的貿易順序S（s為S的最后一個國家）和這一輪否決的國家V，任取可以和s國貿易的國家c（不屬于S和V）置于樹的當前生成位置，然后用(S’ = <S, c>和V’ = 空集)生成左子樹，用(S’ = S和V’ = V ∪ {c})生成右子樹，如果c不存在或者s = B則終止當前子樹的生成，如此反復可以建立一棵二叉搜索樹，
2. 遍歷原則：
   • 前進：當前節點未被剪枝并且仍有子節點即可繼續前進，
   • 分支：先遍歷左分支，后遍歷右分支，
   • 回溯：左右分支都被遍歷時回傳父節點，
   • 剪枝：剪枝條件如下：
     1. 當前稅費 + s國與B國貿易的最小稅費 >= 已知最優方案的稅費
     2. 當前時間 + s國與B國貿易的最短時間 > t
3. 子問題的下界為稅費下界和時間下界，均由dijkstra演算法演算法得到，表示某國與B國貿易的最小稅費和最短時間，兩個結果均由榷訓限制的方法得到，所以是正確的，計算復雜度也不高，當然有效，父問題的上界是已知最優方案的稅費，顯然正確有效，

使用Dijkstra演算法得到子問題下界：
     1、稅費下界：某國與B國貿易的最小稅費，順便記錄對應的事件和貿易順序
     2、時間下界：某國與B國貿易的最短時間
search(<A>, <V>)
回傳最優結果

def search(貿易順序S, 否決的國家V):
     令s為S的最后一個國家
     判斷S是否合格，條件如下：
          1.當前稅費 + s國與B國貿易的最小稅費 < 已知最優方案的稅費
          2.當前時間 + s國與B國貿易的最短時間 <= t
     如果合格：
          當前時間 + s國與B國貿易的最小稅費對應的時間 <= t:
               記<S,s國與B國貿易的最小稅費對應貿易順序(不包括s)>為已知最優
          否則對與s國貿易的不屬于S和不屬于V的國家c：
               search(<S, c>, V)
               search(<S>, <V, c>)