組合爆炸

當解決問題所需計算的數量級過於巨大時所造成的障礙。例如在設計下棋軟件時就遇到組合爆炸的困擾，每一手棋常要計算和分析幾千種可能的步法。解決這類問題人比電腦似乎更勝一籌，因為人憑籍着説不太清楚的“直覺”思考把可能的步法限制在力所能及的範圍內。這就是優秀的棋藝選手能打敗最好的下棋程序的原因所在。 ^[2] 

旅行商問題，簡稱TSP問題，又稱貨郎擔問題、郵遞員問題，是英國數學家剋剋曼（T.P. Kirkman）於19世紀初提出的一個數學問題，是指旅行商要從某個城市出發，旅行n個城市然後回到出發城市，要求各個城市經歷且僅經歷一次，並要求所走的路程最短。

用最原始的方法解決TSP問題可以找出所有可能的迴路，從中選取路徑長度最短的迴路，對每對路徑來説，不同的只是路徑的方向，因此，可以將所有可能的旅行路線減半，對於具有n個頂點的TSP問題，可能的解有(n-1)!/2個。這是一個非常大的數，隨着n的增長，TSP問題的可能解也在迅速地增長，從而產生所謂的組合爆炸。例如：

10城市的TSP問題有大約180 000個可能解。

20城市的TSP問題有大約60 000 000 000 000 000個可能解。

TSP問題屬於組合優化問題，即尋找一個組合對象（一個排列或一個組合），這個對象能夠滿足特定的約束條件並使得某個目標函數取得極值：價值最大或成本最小。

無論從理論的觀點還是實踐的觀點，組合優化問題都是計算領域中最難的問題，其原因是：

（1）隨着問題規模的增大，組合對象的數量增長極快，即使是中等大小的實例，其組合對象的數量也會達到不可思議的數量級，產生組合爆炸；

（2）還沒有一種已知算法能在可接受的時間內，精確地求解絕大多數這類問題。 ^[3] 

一個組合優化問題π由三個基本要素（D,F,f）組成。其中：

（1）D表示決策變量的定義域，其每個決策變量的有限個取值的不同組合形式構成了組合優化問題的不同實例，所有這些實例構成了實例集合S(I)。

（2）對於每一個實例I，存在一個有窮的可行解集合F(I)。

（3）對於每一個實例I和每一個可行解σ∈F(I)，其目標函數都可以被賦予一個實數值f(I,σ)。如果組合優化問題π為求極（大）小值問題，則實例I的最優解σ1是這樣一個可行解，即對於∀σ∈F(I)，都滿足f(I,σ)≥f（I,σ)[對於極大值問題則為f(1,σ1)≤f(1,σ)]。

對於一個組合優化問題π，給定任意一個實例I，如果能設計一個解法程序P使其總能夠找到該問題的一個可行解σ∈F(I)，則稱P為π的近似算法；進一步，如果總能夠找到該問題的一個最優解，則稱P為π的精確算法。

組合優化問題的最大特點是決策變量取值是離散的、有限的；可行解集合同樣也是有限的。因此，從理論上講，只要將這些有限的點逐一判斷是否滿足約束條件和比較目標函數值的大小，該問題的精確解算法一定存在並可以找到。但是，由於現實優化問題的規模都比較大、約束條件較為複雜等原因，在可以容忍的有限時間及費用範圍內，通過精確算法尋找最優解十分困難，不得已退而求其次，需要採用近似算法求其局部最優解。 ^[1] 

人工智能由相互有差異但都令人感興趣的幾個方面組成，其中多數AI應用的基礎是問題求解。所有問題基本分為兩類。第一類通過某種確保成功的決定過程（即計算過程）解決。解決第一類問題的方法常常易於轉換成計算機能執行的算法。然而，沒有幾個現實問題是適合計算解決方案的。事實上，許多問題（即第二類問題）是非計算性的。解決第二類問題的辦法是搜索，即人工智能關心的問題求解方法。

人工智能迫求的目標之一，是建立一個通用問題求解器。通用問題求解器是一種程序，其中沒有特定領域的專門知識，但又能夠產生對各種問題的解。

早期研究AI的主要目的是研究優秀的搜素方法。其原因有二：需要和願望。把AI技術應用到現實問題的最大障礙就是多數情況下的規模和複雜性，因此我們需要高效率的搜索技術。此外，研究人員一直認為搜索是問題求解的關健，而問題求解又是智能的關鍵成分。 ^[4]