第1章 什么是NP問(wèn)題

大部分的算法入門圖書，包括“算法詳解”系列圖書的第1卷到第3卷，都存在選擇性偏向的問(wèn)題。它們關(guān)注的是能夠由精巧、快速的算法所解決的計(jì)算性問(wèn)題。不管怎么說(shuō)，還有什么比學(xué)習(xí)一種精妙的快速算法更有樂(lè)趣、更有成就感呢？好消息是許多基本的、實(shí)用的問(wèn)題都可以歸入這個(gè)范疇，包括排序、圖的搜索、最短路徑、哈夫曼編碼、最小生成樹(shù)、序列對(duì)齊等。但是，如果只介紹這些精心選擇的問(wèn)題而忽略那些讓嚴(yán)肅的算法設(shè)計(jì)師和程序員深感頭痛的計(jì)算性難題，無(wú)疑是不客觀和不全面的。遺憾的是，有很多重要的計(jì)算性問(wèn)題，包括在我們的項(xiàng)目中經(jīng)常出現(xiàn)的一些問(wèn)題，并不存在已知的快速算法。更糟的是，我們無(wú)法期待解決這些問(wèn)題的算法能夠在未來(lái)得到突破，因?yàn)樗鼈円呀?jīng)被公認(rèn)存在死結(jié)，無(wú)法由任何快速算法所解決。

意識(shí)到這個(gè)嚴(yán)峻的事實(shí)之后，我們很快就會(huì)想到兩個(gè)問(wèn)題。首先，當(dāng)這類問(wèn)題在我們的工作中出現(xiàn)時(shí)，怎么才能認(rèn)識(shí)到它們的存在，以便相應(yīng)地調(diào)整自己的期望值，避免花費(fèi)大量的時(shí)間尋找注定是美夢(mèng)泡影的算法呢？其次，如果這類問(wèn)題對(duì)于我們的應(yīng)用是非常重要的，我們應(yīng)該如何調(diào)整自己的期望值，應(yīng)該使用什么算法工具來(lái)實(shí)現(xiàn)它們呢？本書將提供這兩個(gè)問(wèn)題的詳細(xì)答案。