第一章 計算機難解問題與計算復雜性理論
本章簡要介紹計算機難解問題的基本概念及一些經典的難解問題。首先，以一個簡單的周游全國大城市的例子，給出計算機難解問題的一個具體應用。其次，介紹計算復雜性理論（computational complexity theory）的一些基本概念，包括問題與實例的概念、多項式時間與指數時間算法、P類與NP類問題等。最后，較為詳細地介紹本書中頻繁使用到的幾個經典的難解問題。
1.1 現實世界中的難解問題
在算法設計或者數據結構的很多知識體系中，存在很多有趣的問題，比如串的匹配問題、二叉樹的查找問題等。這些問題均可以在較短的時間（多項式時間）內快速求解。然而，在現實世界中，還存在一大類問題，它們的結構或簡單或復雜，但要獲得這些問題的精確解卻是極其困難的。
一個簡單的例子是：一位大學生規劃在畢業后周游全國主要的大城市，比如北京、上海、天津、重慶、南京、長沙、合肥、大連。他計劃從大連出發，經過上述每個城市一次，最后返回大連。現在的問題是：如何找到一條最合理的旅游路線，使得這位大學生的旅費最少？在這里，假設該大學生經過前期的調研，已經把各個城市之間直達的旅費調研清楚了。這個問題是一個非常有趣的問題，也非常簡單易懂，在5min內就可以向任何一位小學生講清楚。但是，如何獲得該問題的精確解，卻不像該問題的定義那么簡單。可以用一個排列來表示解，比如大連→北京→天津→重慶→長沙→合肥→上海→南京→大連。一種直觀的精確求解方法是窮舉法，把所有的可能性都試一次，然后挑出最好的解。如果用這種求解方法，則共有7！種可能性（注意到是固定地從大連出發，又回到大連）。對于少量的城市數而言，這種窮舉法是可行的，但是當城市數增加為100甚至更多時，需要嘗試的解的個數則迅速增加而難以逐一枚舉。另一種直觀方法是采用貪心法，即從大連出發，每次挑選距離當前城市最近且沒有訪問過的城市作為下一個訪問的城市，直到回到大連為止。這種方法顯然速度比窮舉法快得多，然而該方法是一種“鼠目寸光”的方法，并不能確保獲得的是精確解，通過反例法很容易證實。
實際上，上述例子就是經典的組合優化問題―――旅行商問題（traveling sales-man problem，TSP）的具體應用。在上述例子中，兩個城市之間的旅費，也可以換成是城市間的距離、旅行時間等。而TSP問題的應用背景實際是十分廣泛的，在交通調度、線路板設計、工業控制等諸多領域都能找到它的應用例子。以線路板設計為例，如何在線路板上放置若干個元器件，使得它們之間存在一條最短環路，以節省印制電路的成本？將元器件映射為城市，則該線路板設計問題就轉化為TSP問題。需要注意的是，這個應用中城市的數量（通常也稱為問題的規模）是成千上萬的，采用窮舉法，即便在目前的天河、藍光等超級計算機上的運行時間也是難以接受的。
有趣的是，TSP問題經過一些變換后，依然是很難求解的。比如，假設有些城市之間距離為無窮大（即兩個城市間沒有通車），那能否找到一條通過每個城市一次且回到出發地的環路？該問題實際上是另外一個難解問題，即哈密爾頓環路問題（Hamiltonian cycle problem）。另外一種針對TSP問題的變換是引入額外的目標函數，比如除了要求最少的旅費之外，還希望旅游線路的旅行時間最少。這實際上又將TSP問題轉化為雙目標優化問題。此時，精確解不再是單個解，而是一個解集。同時，由于兩個目標之間可能相互沖突，因此這個解集通常被稱為Pareto解集，即該解集中的任何一個解都不會比集合中其他解在兩個目標上均更優。這種雙目標優化問題通常比單個目標函數的問題更加困難。
以上討論的種種問題，都具有一些共同的特征，比如在多項式時間內難以精確求解，而若設計一些多項式時間復雜度的算法，通常只能給出一些近似的解。由于這類問題在實際應用中數量極其龐大，有必要在計算機科學及人工智能領域展開專門研究。
1.2 P與NP
本節將討論P和NP的概念，它們是計算復雜性理論的基礎定義，而計算復雜性理論則是整個計算機科學的基礎。為了介紹P和NP的含義，本節將首先給出問題和實例的定義，然后再定義多項式時間和指數時間算法的概念。
