【正文】 啟發(fā)式算法的解更差； 2. 復(fù)雜問題無法求得最優(yōu)算法或最優(yōu)算法太復(fù)雜； 3. 簡單易行，直觀，程序簡單。 啟發(fā)式算法的缺點 1. 不能保證最優(yōu)； 2. 不穩(wěn)定； 3. 依賴于實際問題、設(shè)計者經(jīng)驗。 啟發(fā)式算法的定義 啟發(fā)式算法 智能計算 簡單直觀的算法 一步算法 ：不在兩個可行解之間比較，在未終止的迭代過程中，得到的中間解有可能不是可行解； 例：背包問題的貪婪算法 改進算法 ：迭代過程是從一個可行解到另一個可行解變換，通過兩個解的比較而選擇好的解，直到滿足一定的要求為止； 例： TSP問題的 2－ opt方法 啟發(fā)式算法的分類 P1 P6 P2 P5 P3 P4 2 2 0 3 1 2 2 2 2 4 4 3 4 3 啟發(fā)式算法 智能計算 數(shù)學規(guī)劃算法 用連續(xù)優(yōu)化（如線性規(guī)劃）的方法求解組合優(yōu)化問題（如整數(shù)線性規(guī)劃模型），其中包括一些啟發(fā)式規(guī)則。 基于數(shù)學規(guī)劃的理論。 啟發(fā)式算法的分類 啟發(fā)式算法 智能計算 現(xiàn)代優(yōu)化算法 禁忌搜索算法 模擬退火算法 遺傳算法 人工神經(jīng)網(wǎng)絡(luò) 蟻群算法 粒子群算法 混合算法 啟發(fā)式算法的分類 特點： ? 基于客觀世界中的一些自然現(xiàn)象； ? 建立在計算機迭代計算的基礎(chǔ)上； ? 具有普適性，可解決實際應(yīng)用問題。 啟發(fā)式算法 智能計算 評價算法優(yōu)劣的指標 算法的復(fù)雜性（計算效率） 解的偏離程度（計算效果） 算法的穩(wěn)健性（不同實例、不同時間、不同起點的差異） 評價算法優(yōu)劣的手段 最壞情況分析（純理論） 概率分析（理論分析） 計算模擬分析（統(tǒng)計特性） 啟發(fā)式算法的性能分析 計算復(fù)雜性與 NP完全問題 智能計算 時間復(fù)雜性和空間復(fù)雜性概念 算法 的 時間 復(fù)雜性 ：算法對時間的需要量（加、減、乘、除、比較、讀、寫等操作的總次數(shù)）； 算法 的 空間 復(fù)雜性 ：算法對空間的需要量（存儲空間的大小，二進制位數(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ù) p(n)時，稱相應(yīng)的算法為非多項式時間算法或指數(shù)時間算法； 隨著變量的增加，多項式函數(shù)增長的速度比指數(shù)函數(shù)和非多項式函數(shù)增長的速度要慢得多。 計算復(fù)雜性的基本概念 計算復(fù)雜性與 NP完全問題 智能計算 P類問題（ deterministic polynomial ） 具有多項式時間求解算法的問題類 迄今為止，許多組合優(yōu)化問題都沒有找到求最優(yōu)解的多項式時間算法。 NP類問題 (Nondeterministic polynomial) 定義 1 實例 是問題的特殊表現(xiàn)，所謂實例就是確定了描述問題特性的所有參數(shù)的問題，其中參數(shù)值稱為 數(shù)據(jù) ，這些數(shù)據(jù)占有計算機的空間稱為 實例的輸入長度 。 P,NP,NPC和 NPhard 計算復(fù)雜性與 NP完全問題 智能計算 NP類問題 (Nondeterministic polynomial) 定義 2 若一個問題的每個實例只有 “ 是 ” 或 “ 否 ”兩種回答，則稱該問題為 判定問題 。 例， TSP的判定問題：給定 z，是否存在 n個城市的一個排列 W，使得 f(W)≤z。滿足 f(W)≤z的一個排列 W稱為判定問題的 “ 是 ” 答案（可行解）。 P,NP,NPC和 NPhard 計算復(fù)雜性與 NP完全問題 智能計算 NP類問題 (Nondeterministic polynomial) 若存在一個多項式 g(x) 和一個驗證算法 H ，對一類判定問題 A 的任何一個 “ 是 ” 的判定實例 I 都存在一個字符串 S 是 I 的 “ 是 ” 回答，滿足其輸入長度 d(S) 不超過 g(d(I)) （其中 d(I) 為 I 的輸入長度），且驗證算法驗證 S 為 I 的 “ 是 ” 回答的計算時間不超過 g(d(I))，則稱判定問題 A 為非多項式確定問題，簡稱 NP問題 。 NP類問題是比 P問題更為廣泛的問題類 。 P,NP,NPC和 NPhard 簡單地理解 如果計算工作量在計算數(shù)據(jù)規(guī)模 n的多項式（如 n，n2， n3等）的范圍內(nèi)，則計算花費的機時是可以接受的，該問題稱為 P問題； 有些問題尚未證實是否屬于 P類，又未找到有效算法，則稱 NP問題。 計算復(fù)雜性與 NP完全問題 智能計算 P,NP,NPC和 NPhard 計算復(fù)雜性與 NP完全問題 智能計算 NP－ C （ NPComplete）和 NP－ hard類問題 Cook在 1971年給出并證明了有一類問題具有下述性質(zhì) （ 1）這類問題中任何一個問題至今未找出多項式時間算法；（ 2）如果這類問題中的一個問題存在有多項式時間算法，那么這類問題都有多項式時間的算法，這類問題中的每一個問題稱為 NP完全問題，這個問題的集合簡記 NPC。 P,NP,NPC和 NPhard NP－ C（ NPComplete）和 NP－ hard類問題 定義： 稱判定問題 A∈ NPC，若 A∈ NP 且 NP中的任何一個問題可多項式規(guī)約為問題 A。稱判定問題 A為 NP－ hard，只要上述第二個條件成立。 計算復(fù)雜性與 NP完全問題 智能計算 P,NP,NPC和 NPhard 1 2 四類問題的關(guān)系 NPC問題具有重要的實際意義和工程背景 : 第一個 NP完全問題（ Cook定理 1971） 六個 NP完全問題（ Karp 1972) 更多的 NP完全問題 1979年： 300多個 1998年： 2022多個 TSP問題、背包問題、裝箱問題、 Jobshop和Flowshop問題、集合覆蓋問題等均是 NPC問題。 計算復(fù)雜性與 NP完全問題 智能計算 P,NP,NPC和 NPhard 第一章 結(jié)束 智能計算