概述與組合優(yōu)化概念續(xù)-預(yù)覽頁
【正文】 復(fù)雜性概念：復(fù)雜性的研究是從區(qū)分“問題”和“實(shí)例”并定義實(shí)例的“輸入規(guī)?！遍_始的。 表 1 問題 實(shí)例 TSP TSP例題中各參數(shù)為： 100個(gè)城市，城市間距離 已知 背包問題 背包例題中各參數(shù)為： 4個(gè)物品，大小分別為 4,3,2,2，價(jià)值分別為 8,7,5,7，包的大小為 6. 整數(shù)線性規(guī)劃 整數(shù)規(guī)劃例題中 n， A,b， c已知。評(píng)價(jià)算法的一個(gè)主要指標(biāo)是計(jì)算所耗用的時(shí)間。稱有肯定答案的實(shí)例為“是”實(shí)例，稱答案為“否”的實(shí)例為“否”實(shí)例或非“是”實(shí)例。 NP問題 ? 如果 X是判定問題的一個(gè)答案為“是”的實(shí)例，則存在一個(gè)對(duì) X 的一個(gè)多項(xiàng)式時(shí)間為界驗(yàn)證，使得能在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證這個(gè)證明的真實(shí)性； ? 定理： 即 P是 NP的子集。事實(shí)上要證明一個(gè)問題是 NP－完備的轉(zhuǎn)化為要證明： 1） 該問題是 NP的 2） 有一個(gè)已知的 NP－完備問題可以多項(xiàng)式時(shí)間轉(zhuǎn)化為該問題。如 TSP枚舉算法。 （ k=1,2， …,n ）對(duì)于每一個(gè) k需要一次加法和一次比較 ，共 2n次運(yùn)算，這個(gè)貪婪算法的計(jì)算量為 ，是一個(gè)多項(xiàng)式時(shí)間算法。 ? 4）簡(jiǎn)單易行，比較直觀，易被使用者接受。 ? 3）算法的好壞依賴于實(shí)際問題，算法設(shè)計(jì)者的經(jīng)驗(yàn)和技術(shù)，這一點(diǎn)很難總結(jié)規(guī)律，同時(shí)使不同算法之間難于
語文相關(guān)推薦
鄂ICP備17016276號(hào)-1