五大演算法策略

枚舉法

枚舉法是一種通過列舉所有可能解，然後篩選出符合條件或最優解的解題方法，也教作暴力破解法，適合於解決問題規模較小的情況。

• 特點
  • 全解空間遍歷：列舉所有可能的解決方案，找到滿足條件的解。
  • 全局最優保證：能夠找到全局最優解，因為所有可能性都被探索。
  • 高時間複雜度：枚舉所有可能性，適合處理問題規模較小的情況。
• 步驟：
  1. 列出所有可能解：針對問題，枚舉所有可行的解決方案或組合。
  2. 驗證每個解：逐一檢查每個可能解是否符合問題的條件。
  3. 選擇最優解：在符合條件的解中，選擇最符合優化目標的解。

學習影片：https://www.youtube.com/watch?v=YlVJjXgr22Q&t=585s

枚舉法的核心在於暴力搜索，它遍歷所有可能性並檢查每一個解的可行性，儘管計算量較大，但它的簡單性和普遍性使得它成為解決許多問題的一個基本方法，尤其在規模較小的問題中，隨著問題規模增大，必須通過剪枝或動態規劃等技術來優化性能。

貪婪法

貪婪法是一種在求解最優化問題時，透過當前階段選擇局部最優解，希望最終能得到全局最優解的演算法，常見的應用像是背包問題、最小生成樹、哈夫曼編碼等。

• 特點
  • 局部最優：每一步選擇都是基於當前最好的結果，不考慮未來可能的情況。
  • 無後悔性：選擇一旦作出，無法更改。
  • 高效性：一般來說，貪婪法具有較低的時間複雜度，適合處理一些結構簡單的問題。
  • 無法保證全局最優：雖然貪婪法的解通常接近最優解，但並非所有問題都能用貪婪法得到全局最優解。
• 步驟：
  1. 選擇性質：確定問題中能夠應用貪婪選擇策略的性質。
  2. 局部最優：在每一步選擇當下看起來最優的解決方案。
  3. 可行性檢查：確保每一步的選擇都是合法且可行的。
  4. 合併子問題：將每一步的解決方案合併成完整的最終解。

學習影片：https://www.youtube.com/watch?v=wUpL4jSmWU0

貪婪法的特點是每次選擇局部最優，而不考慮未來影響，適合解決具備貪婪選擇性質和最優子結構的問題，如活動選擇問題、最小生成樹、哈夫曼編碼等，貪婪法的優點在於簡單、高效，適合問題結構清晰的情況，但其局限在於無法保證全局最優解，因此不適用於所有問題。

回溯法

回溯法是一種通過不斷嘗試每一條可能的解路徑，遇到無法滿足條件的解時則返回上一步，進行其他選擇的解題方法，它的核心在於試探與回溯，適合用於解決組合問題，如排列、子集、圖中的著色問題等。

• 特點
  • 試探性：逐步構建解決方案，遇到問題則回退重新選擇路徑。
  • 回溯性：當發現當前選擇無法滿足問題時，回溯到上一步並進行其他選擇。
  • 適合解組合性問題：解空間通常很大，可以通過剪枝技術優化性能。
• 步驟
  1. 選擇可能的解決路徑。
  2. 逐步嘗試，檢查當前選擇是否滿足條件。
  3. 若滿足條件，繼續嘗試下一步；若不滿足條件，回溯到上一步進行其他選擇。
  4. 直到找到符合條件的解或探索完所有可能路徑。

學習影片：https://www.youtube.com/watch?v=s7_ekB1hD0g

回溯法適合解決組合性問題，如 N 皇后、迷宮路徑、數獨等。它逐步嘗試所有可能解，遇到無法滿足條件時進行回退。回溯法雖然可以解決多種問題，但在解空間較大時效率不高，因此經常結合剪枝技術優化。

分治法

分治法是一種將問題劃分為多個子問題，逐個解決後將結果合併以解決原問題的算法，典型應用如快速排序、合併排序和二分搜索。

• 特點
  • 將問題分解：將一個大問題分解成若干個小問題，逐個解決。
  • 合併結果：解決完子問題後，將它們的結果合併成最終解。
  • 適合遞迴：分治法往往使用遞迴結構來處理子問題。
• 步驟
  1. 將問題劃分為多個規模較小的子問題。
  2. 遞迴地解決每個子問題。
  3. 將子問題的解合併成最終解。

學習影片：https://www.youtube.com/watch?v=iDwScuDlsGc

分治法主要應用於分而治之的問題，如快速排序、合併排序、二分搜索等。它將問題劃分為小部分逐個解決，再合併成最終解，分治法適合問題可以自然分解的場景，並且具有較高的效率。

分支界定法

分支界限法是一種用於解決整數規劃、背包問題等組合優化問題的算法，它在枚舉所有可能解的同時，通過界限來減少不必要的搜索，從而優化效率。

• 特點
  • 結合枚舉和剪枝：枚舉所有可能解，並在每步進行檢查，剪除無法得到最優解的分支。
  • 高效性：通過設定界限來避免對無解的路徑進行計算，從而提高效率。
  • 適合組合優化問題：如旅行推銷員問題、整數規劃問題等。
• 步驟
  1. 劃分解決空間：將問題劃分為不同分支，每個分支代表一種解決方案。
  2. 設置界限：對每個分支進行可行性檢查，設置界限來篩除不可能成為最優解的分支。
  3. 持續探索：繼續在有效分支中尋找最優解，直到搜索結束。

分支界限法專門針對組合優化問題，如背包問題和旅行推銷員問題。它利用分支探索所有可能解，並通過設置界限來剪去不可能達到最優解的分支，從而大幅減少計算量，適合處理規模較大的優化問題。