窮盡搜尋及其複雜性

7.1 窮盡搜尋。

定義: 窮盡搜尋 (brute force) 是一種解決問題的方法， 它涉及檢查所有可能的解決方案並選擇最佳方案。 它保證找到最佳解， 但由於計算複雜性高，因此通常效率不高。

例子: 考慮旅行推銷員問題 (Travelling Salesman Problem, TSP)。 這裡需要找到一條經過所有城市並返回起始城市的最短路徑。 窮盡搜尋包括檢查所有可能的路徑排列，這具有階乘時間複雜性 O(n!)。

優點：

• 實現簡單。
• 保證找到最佳解決方案。

缺點：

• 計算複雜性高。
• 由於檢查次數呈指數增長，對於大型問題不切實際。

TSP 的 Python 範例：

import itertools

def calculate_distance(path, distance_matrix):
    return sum(distance_matrix[path[i - 1]][path[i]] for i in range(len(path)))
            
def tsp_brute_force(distance_matrix):
    n = len(distance_matrix)
    all_permutations = itertools.permutations(range(n))
    min_distance = float('inf')
    best_path = None
            
    for perm in all_permutations:
        current_distance = calculate_distance(perm, distance_matrix)
        if current_distance < min_distance:
            min_distance = current_distance
            best_path = perm
            
    return best_path, min_distance
            
# 使用範例
distance_matrix = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]
best_path, min_distance = tsp_brute_force(distance_matrix)
print(f"最佳路徑: {best_path} 最小距離: {min_distance}")
        

7.2 NP類的問題

NP類（非確定性多項式）包括問題，其解決方案可以在多項式時間內檢查。 然而，找到解決方案可能需要指數時間。

用人話說：NP 問題是那些最佳解決方案只能透過窮盡搜尋所有選項 (指數時間) 才能找到的問題。 但檢查找到的解決方案是否最佳則更快 (不需要指數時間)。

主要特點：

• 解決方案檢查: 如果給出問題的可能解決方案， 可以在多項式時間內檢查其正確性。
• NP 完全問題: NP 類問題的子集，它們在 NP 中是最困難的。 如果存在解決至少一個 NP 完全問題的多項式算法， 那麼所有 NP 類問題都可以在多項式時間內解決。
• NP 困難問題: 複雜度不低於 NP 類中任何問題的問題。

NP 完全問題的例子：

• 旅行推銷員問題 (Travelling Salesman Problem, TSP): 找出經過所有城市的最短路徑。
• 背包問題 (Knapsack Problem): 尋找項目組合，最大化價值但不超過給定重量。
• 頂點覆蓋問題 (Vertex Cover): 找到覆蓋圖中所有邊的最小頂點集。
• 布林公式滿足問題 (Boolean Satisfiability Problem, SAT): 確定是否存在一組變量滿足布林公式。

7.3 解決複雜問題的方法建議

如果找到最佳解決方案需要的不合理的時間，那麼用合理的時間可能可以找到足夠好的解決方案。

近似算法：

• 使用近似算法，這些算法可以在合理的時間內提供良好的 (雖非總是最佳的) 解決方案。
• 例子: 用於分數項目的背包問題的貪婪算法。

啟發式方法：

• 使用啟發式方法，比如蟻群算法、遺傳算法和人工智能算法， 來找到複雜問題的近似解。

問題分解方法：

• 將問題拆分為較小的子問題並分別解決。
• 例子: 用於背包問題的動態規劃。

使用多項式算法：

• 如果可能，使用多項式算法解決子問題或找到部分解。
• 例子: 用於尋找圖中最短路徑的 Dijkstra 算法。

窮盡搜尋和 NP 類問題是算法理論和計算複雜性中的重要概念。 窮盡搜尋保證找到最佳解決方案，但對於大型問題通常不切實際。 NP 類問題包括許多重要問題，這些問題只能通過使用啟發式方法和近似方法在合理時間內解決。