【正文】 計算復(fù)雜性與 NP完全問題 智能計算 P,NP,NPC和 NPhard 第一章 結(jié)束 智能計算 。稱判定問題 A為 NP－ hard，只要上述第二個條件成立。 計算復(fù)雜性與 NP完全問題 智能計算 P,NP,NPC和 NPhard 計算復(fù)雜性與 NP完全問題 智能計算 NP－ C （ NPComplete）和 NP－ hard類問題 Cook在 1971年給出并證明了有一類問題具有下述性質(zhì) （ 1）這類問題中任何一個問題至今未找出多項式時間算法；（ 2）如果這類問題中的一個問題存在有多項式時間算法，那么這類問題都有多項式時間的算法，這類問題中的每一個問題稱為 NP完全問題，這個問題的集合簡記 NPC。 NP類問題是比 P問題更為廣泛的問題類 。滿足 f(W)≤z的一個排列 W稱為判定問題的 “ 是 ” 答案（可行解）。 P,NP,NPC和 NPhard 計算復(fù)雜性與 NP完全問題 智能計算 NP類問題 (Nondeterministic polynomial) 定義 2 若一個問題的每個實(shí)例只有 “ 是 ” 或 “ 否 ”兩種回答，則稱該問題為 判定問題 。 計算復(fù)雜性的基本概念 計算復(fù)雜性與 NP完全問題 智能計算 P類問題（ deterministic polynomial ） 具有多項式時間求解算法的問題類 迄今為止，許多組合優(yōu)化問題都沒有找到求最優(yōu)解的多項式時間算法。 啟發(fā)式算法 智能計算 評價算法優(yōu)劣的指標(biāo) 算法的復(fù)雜性（計算效率） 解的偏離程度（計算效果） 算法的穩(wěn)健性（不同實(shí)例、不同時間、不同起點(diǎn)的差異） 評價算法優(yōu)劣的手段 最壞情況分析（純理論） 概率分析（理論分析） 計算模擬分析（統(tǒng)計特性） 啟發(fā)式算法的性能分析 計算復(fù)雜性與 NP完全問題 智能計算 時間復(fù)雜性和空間復(fù)雜性概念 算法 的 時間 復(fù)雜性 ：算法對時間的需要量（加、減、乘、除、比較、讀、寫等操作的總次數(shù)）； 算法 的 空間 復(fù)雜性 ：算法對空間的需要量（存儲空間的大小，二進(jìn)制位數(shù)）； 問題 的 時間 復(fù)雜性 ：所有算法中時間復(fù)雜性最小的算法時間復(fù)雜性； 問題 的 空間 復(fù)雜性 ：所有算法中空間復(fù)雜性最小的算法空間復(fù)雜性； 計算復(fù)雜性的基本概念 計算復(fù)雜性與 NP完全問題 智能計算 復(fù)雜性 問題 分類 P類、 NP類、 NP完全類 復(fù)雜性表示方法 復(fù)雜性表示為問題規(guī)模 n（如 TSP的 n）的函數(shù)， 時間復(fù)雜性 T(n)，關(guān)鍵操作的次數(shù)； 空間復(fù)雜性 S(n)，占用的存儲單元數(shù)量； 計算復(fù)雜性的基本概念 計算復(fù)雜性與 NP完全問題 智能計算 復(fù)雜性表示方法 若算法 A的時間復(fù)雜性為 TA(n)=O(p(n))， O(p(n))為復(fù)雜性函數(shù) p(n)主要項的階，且 p(n)為 n的多項式函數(shù)，則稱 算法 A為多項式算法 。 基于數(shù)學(xué)規(guī)劃的理論。 啟發(fā)式算法的缺點(diǎn) 1. 不能保證最優(yōu)； 2. 不穩(wěn)定； 3. 依賴于實(shí)際問題、設(shè)計者經(jīng)驗(yàn)。1:},2,1{ ?knacii?記成排列從大到小排列，不妨把對物品以。作出貪婪決策的依據(jù)稱為貪婪準(zhǔn)則（ greedy criterion）。 在每個階段，都作出一個看上去最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下）。 4 50 啟發(fā)式算法 智能計算 最優(yōu)算法 一個問題的最優(yōu)算法求得該問題每個實(shí)例的 最優(yōu)解 ； 啟發(fā)式算法 一個基于直觀或經(jīng)驗(yàn)構(gòu)造的算法，在可接受的花費(fèi)（計算時間、占用空間等）下給出待解決優(yōu)化問題每一個實(shí)例的一個 可行解 ，該可行解與最優(yōu)解的偏離程度不一定事先可以預(yù)計。 41 26。 58 35。 82 7。 18 40。 74 78。 58 69。 25 38。 83 46。 18 54。 83 69。 71 44。 2 99。 25 62。 37 84。 組合優(yōu)化問題 C1：第一 種顏色 C2：第二 種顏色 C3：第三 種顏色 C1 C1 C2 C3 C2 A B D C E 最優(yōu)化問題及其分類 智能計算 典型問題 —— 聚類問題（ Clustering problem） m維空間上的 n個模式 {Xi|i=1,2,…, n}，要求聚成 k類，使得各類本身內(nèi)的點(diǎn)最相近，如要求 其中 Rp為第 p類的中心，即 其中， p=1,2,…, k， np為第 p類中的點(diǎn)數(shù)。 組合優(yōu)化問題 背包問題的貪婪算法 最優(yōu)化問題及其分類 智能計算 典型問題 —— 裝箱問題（ Bin packing problem） 有 n個尺寸不超過 1的物品，有數(shù)個尺寸為 1的箱子，如何將這些物品裝入箱子，使得所需箱子的個數(shù)最少。 若各工件技術(shù)約束條件相同，轉(zhuǎn)化為 Flowshop。 組合優(yōu)化問題 1 2 3 4 12 1 8 10 3 2 最優(yōu)化問題及其分類 智能計算 典型問題 —— 旅行商問題（ Traveling salesman problem, TSP） 計算復(fù)雜度：指數(shù)災(zāi)難 組合優(yōu)化問題 城市數(shù) 24 25 26 27 28 29 30 31 計算 時間 1 sec 24 sec 10 min hour day day year 325 year 最優(yōu)化問題及其分類 智能計算 典型問題 —— 加工調(diào)度問題（ Scheduling problem,如 Flowshop, Jobshop） Jobshop： n個工件在 m臺機(jī)器上加工， Oij：第 i個工件在第 j臺機(jī)器上的操作， Tij：相應(yīng)的操作時間，已知。 組合優(yōu)化問題 ，構(gòu) 成},{ 21 的解空間為所有狀態(tài)令 ns,ssΩ ??要求尋找最對應(yīng)的目標(biāo)函數(shù)值為狀態(tài) ,)( ii ssC。 函數(shù)優(yōu)化問題 最優(yōu)化問題及其分類 智能計算 有約束的函數(shù)優(yōu)化 常用受約束測試函數(shù)； 影響因素： （ 1）曲面拓?fù)湫再|(zhì)，線性或凸函數(shù)比無規(guī)律的函數(shù)更容易求解； （ 2）可行區(qū)域的疏密程度，通常以可行區(qū)域占整個搜索空間的比值來度量； 函數(shù)優(yōu)化問題 最優(yōu)化問題及其分類 智能計算 有約束的函數(shù)優(yōu)化 常用受約束測試函數(shù)； 影響因素： （ 3）整體最優(yōu)解與可行區(qū)域最優(yōu)解之比； （ 4）在最優(yōu)解處活躍約束的數(shù)目，活躍約束數(shù)目越多則最優(yōu)解離可行區(qū)域的邊界越近。 傳統(tǒng)的評價方法 算法收斂性、收斂速度 傳統(tǒng)優(yōu)化方法 引言 智能計算 待解決的問題 離散性、不確定性、大規(guī)模 現(xiàn)代的優(yōu)化方法 啟發(fā)式算法（