第5章 經典NP-Complete問題#

理論告訴我們 NP-complete 問題「彼此一樣難」，但要真正運用這個知識，我們必須認識這個家族中最具代表性的成員。本章將介紹幾個最經典的 NP-complete 問題：3-SAT、子集合加總（SUBSET-SUM）、背包問題、圖著色、頂點覆蓋、旅行銷售員與漢米爾頓迴路。這些問題不只出現在教科書上，更頻繁地以各種偽裝出現在工程與工業界的日常決策中。熟悉它們的「長相」，你就能在新問題出現時迅速辨識出 NP-hard 的徵兆，進而選擇正確的應對策略——這也是後續章節的實戰基礎。