概述與組合優(yōu)化概念續(xù).ppt

-張宗祥 電子商務教研室P,NP,NPC,NP-hard 啟發(fā)式算法 算法基礎 問題、實例與輸入規(guī)模 問題復雜性概念：復雜性的研究是從區(qū)分“問題”和“ 實例”并定義實例的“輸入規(guī)?！遍_始的。 對于一個給定的組合優(yōu)化問題，當問題中的參數賦 予具體值時，稱為問題的一個實例如表1。這些具 體值稱為數據，這些數據輸入計算機所占的空間稱 為實例的輸入長度或輸入規(guī)模如表2。 表1 問題實例 TSPTSP例題中各參數為：100個城市，城市間距離 已知 背包問題 背包例題中各參數為：4個物品，大小分別為4,3,2,2，價值分 別為8,7,5,7，包的大小為6. 整數線性規(guī)劃 整數規(guī)劃例題中n，A,b，c已知。 表2 數據二進制編碼輸入長度 111 2102 1010104 641 000 0007 k2 一個實例完全由它的數據決定，給定一個問題的數 據，即給定一個實例，我們可以用一種已知的計算 機上的方法去求解。這種計算機上的求解方法稱為 算法。算法不僅僅局限于每一個實例，而是求解問 題的統(tǒng)一程序。評價算法的一個主要指標是計算所 耗用的時間。 迄今為止，許多的組合優(yōu)化問題都沒有找到求最優(yōu) 解的多項式時間算法。 比多項式問題類可能更廣泛的一個問題類是非確定 多項式時間（nondeterministic polynomial，NP ）問題，NP的概念是由判斷問題引入的。 如果一個問題的每一個實例只有“是”或“否”兩種答 案，則稱這個問題為判斷問題。稱有肯定答案的實 例為“是”實例，稱答案為“否”的實例為“否”實例或非 “是”實例。 優(yōu)化問題與判定問題 在研究組合優(yōu)化問題復雜性時，處理的方法是對 給定的一類優(yōu)化問題，將其轉化為判定問題，使 對每一個實例只有“是”或“否”的回答。下面給出幾 個優(yōu)化問題對應的判定問題。 將LP（目標函數為求最小）轉化為LP判定問題 P類問題 給定每個問題的實例，我們有多項式時間算法得 出答案是是還是不是。 NP問題 如果X是判定問題的一個答案為“是”的實例，則 存在一個對X 的一個多項式時間為界驗證，使得 能在多項式時間內驗證這個證明的真實性； 定理： 即P是NP的子集。 多項式時間歸納法（轉換） 兩個判定問題 ，如果 多項式歸結到 ，則 當 有多項式算法時， 也有多項式時間算法。 所有的P類問題都是屬于NP問題. P是否等于NP?這個問題至今還未解決 NP問題不一定都是難解的問題，比如簡單的數組排 序問題是P類問題，但是P屬于NP，所以也是NP問 題. 現在還不知道是否有P=NP或者PNP，只不過現在還無 法證明。這類特殊的NP問題就是NP完全問題 NPComplete（NP完備類） 常見的NP完備問題 有成千上萬個NP完備問題，如：整數線性規(guī)劃、 團、貨郎擔問題、適定性問題、點覆蓋、獨立集、 哈密頓圈問題、01背包問題。事實上要證明一個 問題是NP完備的轉化為要證明： 1）該問題是NP的 2）有一個已知的NP完備問題可以多項式時間轉 化為該問題。 NP困難問題 P NP NPC NPH 一個問題的最優(yōu)算法求得該問題每個實例的最優(yōu)解 ，啟發(fā)式算法是對應最優(yōu)算法提出的。定義為：一 個基于直觀和經驗的短發(fā)，在可接受的花費下給出 待解決組合最優(yōu)化問題每一個實例的一個可行解， 改可行解與最優(yōu)解的偏離程度不一定事先可以預計 。 在某些情況下，特別是實際問題中，最優(yōu)算法的計 算時間使人無法忍受或因問題的難度事情計算時間 隨實例規(guī)模的增加以指數速度增加。如TSP枚舉算 法。 背包問題的貪婪算法 Step1 對物品以 從大到小排列，不妨把排列記成 1,2，,n, k=1. Step2 若 則 ，否則 k=k+1；當k=n+1時，停止；否則，重復 Step2 。 為貪婪算法的解，單位尺寸價值比越大越 先裝包。 的比值計算需要n次運算， 從小到大排列需 要 次運算。 （k=1,2，,n）對 于每一個k需要一次加法和一次比較 ，共2n次運算 ，這個貪婪算法的計算量為 ，是一個多項 式時間算法。 啟發(fā)式算法優(yōu)點： 1）數學模型本身是實際問題的簡化，或多或少地忽略 了一些因素；而且數據采集具有不確定性；參數估計估 計具有不準確性；這些因素可能造成最優(yōu)算法所得到的 解比啟發(fā)式算法更差。 2）有些難的組合優(yōu)化問題可能還沒找到最優(yōu)算法，由 算法復雜性理論，它們的計算時間也是不可接受的。 3）一些啟發(fā)式算法可以用在最優(yōu)算法中，比如分支定 界算法中，可以用啟發(fā)式算法估計上下界。 4）簡單易行，比較直觀，易被使用者接受。 5）速度快，這在實時管理中非常重要。 6）多數情況下，程序簡單，易于在計算機上實現和修 改. 啟發(fā)式算法缺點 1）不能保證求得最優(yōu)解 2）表現不穩(wěn)定，啟發(fā)式算法在同一問題的不同實 例計算機中會有不同的效果，有些很好，有些很差 。在實際應用中，這種不穩(wěn)定性造成計算結果不可 信，可能造成管理困難。 3）算法的好壞依賴于實際問題，算法設計者的經 驗和技術，這一點很難總結規(guī)律，同時使不同算法 之間難于比較。 啟發(fā)式算法分類： 1）簡單直觀的算法：如貪婪算法 2）數學規(guī)劃算法：拉格朗日松弛算法 3）現代優(yōu)化算法：遺傳算法，蟻群算法 啟發(fā)式算法性能分析 評價算法優(yōu)劣常用的三個主要指標：算法復雜性、 解的偏離程度、和算法的穩(wěn)健性，即同一算法對不 同實例、在不同時間、不同起點的計算效果的差異 大小。 評價