數(shù)學(xué)建模組合優(yōu)化問題和計(jì)算復(fù)雜性第1頁，課件共57頁，創(chuàng)作于2023年2月§1.1組合優(yōu)化問題與算法DEF共有3!=6種可能得到分配矩陣：如何嫁娶，使獲得的禮品最多？Example1婚姻問題

(matchingproblem)女兒ABC追求者EDF3271510426287第2頁，課件共57頁，創(chuàng)作于2023年2月§1.1組合優(yōu)化問題與算法婚姻問題的數(shù)學(xué)模型：設(shè)：第3頁，課件共57頁，創(chuàng)作于2023年2月§1.1組合優(yōu)化問題與算法貪婪（Greedy)解一般不會(huì)產(chǎn)生最差解；在某些模型中,貪婪算法能得到最優(yōu)解；3.可以使用窮舉法，但是以時(shí)間為代價(jià)貪婪解的結(jié)果：28+5+1=34最優(yōu)解的結(jié)果：

27+4+26=57Note：最差解的結(jié)果：3+10+7=20第4頁，課件共57頁，創(chuàng)作于2023年2月§1.1組合優(yōu)化問題與算法Example2

背包問題（KP，KnapsackProblem）

假設(shè)有人要出發(fā)旅行,他考慮要帶

7種物品（每件物品的重量與價(jià)值如表）現(xiàn)在假設(shè)他最多帶35kg物品，問：該帶哪幾件物品總價(jià)值最大？設(shè)：共有27種可能第5頁，課件共57頁，創(chuàng)作于2023年2月§1.1組合優(yōu)化問題與算法Example

3旅行商問題（TSP,TravellingSalesmanProblem)

一個(gè)商人要到n座城市去做生意，設(shè)兩個(gè)城市i和j之間的距離為dij.如何選擇一條道路使得商人每個(gè)城市走一遍后回到起點(diǎn)且所走路程最短TSP可分為：對(duì)稱（dij=dji)和非對(duì)稱(dij≠dji)距離兩種共有（n-1)!種可能City1City2City5City4City3第6頁，課件共57頁，創(chuàng)作于2023年2月§1.1組合優(yōu)化問題與算法設(shè)：TSP問題的數(shù)學(xué)模型：為了減少變量個(gè)數(shù)作用是什么共有多少變量？25n(n-1)第7頁，課件共57頁，創(chuàng)作于2023年2月§1.1組合優(yōu)化問題與算法若|s|=n

則由n個(gè)點(diǎn)構(gòu)成的一個(gè)回路是可行方案。因?yàn)橛汕懊鎯蓚€(gè)約束條件的限制，不可能由n-1個(gè)點(diǎn)構(gòu)成回路而留一個(gè)點(diǎn)在外面。Note：條件(1)，(2)表示每個(gè)城市經(jīng)過一次，但不能保證它可行，要求局部不構(gòu)成圈，條件(3)就是為了約束這一點(diǎn)。為什么？第8頁，課件共57頁，創(chuàng)作于2023年2月§1.1組合優(yōu)化問題與算法共同特點(diǎn)：可行方案是有限的

——組合優(yōu)化問題

Definition1

組合優(yōu)化問題π是一個(gè)極小化（或極大化）的問題，它是由以下三部分組成：（1）實(shí)例集合；（2）對(duì)每個(gè)實(shí)例I，有一個(gè)有窮的可行解集合S（I）(3)目標(biāo)函數(shù)f，它對(duì)于每個(gè)實(shí)例I和每個(gè)可行解σ∈S（I），賦以一個(gè)有理數(shù)f(I,σ).則實(shí)例I的最優(yōu)解為這樣一個(gè)可行解

σ*∈

S(I),它使得對(duì)于所有σ∈S（I），都有

f(I,σ*)≤f(I,σ)（f(I,σ*)≥f(I,σ)）。

第9頁，課件共57頁，創(chuàng)作于2023年2月§1.1組合優(yōu)化問題與算法組合優(yōu)化的數(shù)學(xué)模型：

Minf(x)s.t.g(x)≥0x∈D其中x為決策變量

f(x)為目標(biāo)函數(shù)g(x)為約束函數(shù)D為決策變量的定義域，D為有限集合。F={x|x∈D,g(x)≥0}——可行域所以，可由（D，F(xiàn)，f

）

定義一個(gè)組合優(yōu)化問題。組合優(yōu)化的描述方法：1°數(shù)學(xué)模型（規(guī)劃模型）2°文字語言敘述第10頁，課件共57頁，創(chuàng)作于2023年2月§1.1組合優(yōu)化問題與算法一類實(shí)際問題的數(shù)學(xué)模型的總稱，如TSP、LPetc.

（一個(gè)問題中總包含了若干個(gè)參數(shù)）對(duì)問題給定一組參數(shù)所得到的例子。

一個(gè)科學(xué)的計(jì)算過程，指一步步求解問題的通用程序，它是解決問題的程序步驟的一個(gè)清晰描述。算法是相對(duì)問題而言的，不單單是針對(duì)問題的某個(gè)實(shí)例。如果算法從前一步到后一步的運(yùn)行是由當(dāng)時(shí)狀態(tài)唯一確定的如：單純形法，表上作業(yè)法。遺傳算法是隨機(jī)性算法。問題：實(shí)例：算法：Note：確定性算法：第11頁，課件共57頁，創(chuàng)作于2023年2月§1.1組合優(yōu)化問題與算法

對(duì)于一個(gè)極小化（極大化）優(yōu)化問題π，如果給定任意一個(gè)實(shí)例I，算法A總能找到一個(gè)可行解σ*∈

S(I)。使得

f(I,σ*)≤f(I,σ)（f(I,σ*)≥f(I,σ)）啟發(fā)式算法（近似算法，在§1.3節(jié)中介紹）

組合優(yōu)化總存在最優(yōu)算法，但它以時(shí)間為代價(jià)最優(yōu)算法：返回第12頁，課件共57頁，創(chuàng)作于2023年2月§1.2計(jì)算復(fù)雜性問題

在廣泛的意義下，執(zhí)行算法的效率是用執(zhí)行算法所用的全部計(jì)算資源的多少來衡量(時(shí)間、空間),但通常用時(shí)間作為衡量標(biāo)準(zhǔn)，這就是計(jì)算(時(shí)間)復(fù)雜性問題.

設(shè)有n個(gè)城市(有向圖)則有(n-1)！種可能方案。以計(jì)算機(jī)1秒可以完成24個(gè)城市所有路徑枚舉為單位，則討論TSP問題城市數(shù)2425262728293031計(jì)算時(shí)間1s24s10min4.3h4.9d

136.5d10.8y

325y第13頁，課件共57頁，創(chuàng)作于2023年2月§1.2計(jì)算復(fù)雜性問題一、如何計(jì)算時(shí)間

1°與實(shí)例的輸入規(guī)模有關(guān)，是輸入規(guī)模的函數(shù)（輸入規(guī)模指的是：一個(gè)問題的實(shí)例所有參數(shù)的二進(jìn)制表示的長度的總和?？珊喕癁闆Q策變量的個(gè)數(shù)n，或者頂點(diǎn)的個(gè)數(shù)m.）f(n),g(m)etc.

用初等運(yùn)算——算術(shù)運(yùn)算、比較、轉(zhuǎn)移等指令的次數(shù)，來表示一個(gè)算法在假設(shè)的計(jì)算機(jī)上執(zhí)行時(shí)所需的時(shí)間。相關(guān)因素:第14頁，課件共57頁，創(chuàng)作于2023年2月§1.2計(jì)算復(fù)雜性問題

2°與實(shí)例的參數(shù)有關(guān)，如LP

問題：

maxz=c’xs.t.Ax≤bx≥0,c≤0,b≥0

算法的時(shí)間復(fù)雜性是關(guān)于實(shí)例輸入長度的函數(shù)，用來表示算法的時(shí)間需求。對(duì)于每一個(gè)可能的輸入長度，它是該算法解此輸入長度的最壞可能的實(shí)例所需的時(shí)間（基本運(yùn)算步驟）。相關(guān)因素:Definition2

第15頁，課件共57頁，創(chuàng)作于2023年2月§1.2計(jì)算復(fù)雜性問題

研究計(jì)算復(fù)雜性問題主要是針對(duì)n很大的情形1°9n2與2n2——O(n2)

2°f(n)=12n4-8n3+5n2+2n-80f(n)=O(n4)

當(dāng)n無限增大時(shí)，Lnn,nα(α>0),an

（a>1）趨向于無窮大的速度如何？Note：問：第16頁，課件共57頁，創(chuàng)作于2023年2月§1.2計(jì)算復(fù)雜性問題二、如何評(píng)價(jià)算法的好壞（從計(jì)算復(fù)雜性角度）復(fù)雜性分析的一個(gè)研究方向：對(duì)算法進(jìn)行評(píng)價(jià)

給定n個(gè)整數(shù)x1，x2，……xn，要求將他們從小到大重新排列

取出x1，x2，…xn中的最小者（需比較n-1次）令其為b1（需n賦值次），從x1，x2，…xn中去掉b1，在余下的n-1個(gè)數(shù)中選出最小者，令其為b2，…直到得到b1,b2,……bn，易知其算法共做了n(n-1)/2次比較，至多n(n+1)/2次賦值，計(jì)算復(fù)雜性為，O(n2).Example

4

整序問題：比較交換法：第17頁，課件共57頁，創(chuàng)作于2023年2月§1.2計(jì)算復(fù)雜性問題

先將兩個(gè)單調(diào)不減的數(shù)列{u1，u2…um}與{v1，v2…vm}合并為一個(gè)單調(diào)不減的數(shù)列{w1，w2…w2m}方法為u1與v1比較,若u1≥

v1，w1:=v1。再對(duì)u1與v2進(jìn)行比較，依次對(duì)w2，w3…w2m賦值，計(jì)算量為O(m)。快速算法：

將{x1，x2，……xn}從小到大重新排列（設(shè)：n=2p+1如果n不是2的冪次可補(bǔ)充若干個(gè)很大的數(shù)字使之成為2的冪次）。確定一個(gè)wj需要一次比較一次賦值，共需要（2m-1）次比較，2m次賦值。第18頁，課件共57頁，創(chuàng)作于2023年2月§1.2計(jì)算復(fù)雜性問題將2p+1個(gè)數(shù)分成2p個(gè)單調(diào)不減的2元組,計(jì)算量為O(2p)O(2p)=2p-1O(2)計(jì)算量為O（2p）綜上，算法總工作量為：(p+1)*O(2p)=O(nlogn)81967532(81)(96)(75)(32)18695723(1869)(5723)1689235712356789將2元組兩兩合并成2p-1個(gè)單調(diào)不減的4元組，計(jì)算量為O(2p)依次類推，最后將兩個(gè)2p元組合并成為一個(gè)單調(diào)不減的2p+1元組2p+1=n第19頁，課件共57頁，創(chuàng)作于2023年2月§1.2計(jì)算復(fù)雜性問題設(shè)機(jī)器速度100萬次/秒快速算法O(nlogn)……需20秒設(shè)計(jì)算機(jī)速度為M次/秒

問題D

算法A……計(jì)算復(fù)雜性

n2算法B……計(jì)算復(fù)雜性2n給定1秒的機(jī)器時(shí)間

算法A………可解規(guī)模算法B………可解規(guī)模n=100萬比較交換法O(n2)……需5.8天M=n2第20頁，課件共57頁，創(chuàng)作于2023年2月§1.2計(jì)算復(fù)雜性問題設(shè)機(jī)器速度100萬次/秒給定1秒的機(jī)器時(shí)間

算法A…………可解規(guī)模n=算法B…………可解規(guī)模n=給定1秒的機(jī)器時(shí)間

算法A…………可解規(guī)模n=1000算法B…………可解規(guī)模n=20設(shè)機(jī)器速度提高100倍為1億次/秒給定1秒的機(jī)器時(shí)間算法A……可解規(guī)模n=1000×10算法B……可解規(guī)模

n=20+log2100Log2100<7提供好的算法比提高機(jī)器效率更重要第21頁，課件共57頁，創(chuàng)作于2023年2月§1.2計(jì)算復(fù)雜性問題Definition3

設(shè)A是解某一問題D的算法，對(duì)D

的任一規(guī)模為n

的實(shí)例，可在n的多項(xiàng)式時(shí)間內(nèi)求解（即計(jì)算復(fù)雜性為O（nα））,則稱算法A

為一個(gè)解問題D

的多項(xiàng)式時(shí)間算法。（簡稱多項(xiàng)式算法）

不能這樣限制時(shí)間復(fù)雜性函數(shù)的算法稱為指數(shù)時(shí)間算法。

若存在一個(gè)常數(shù)

C，使得對(duì)所有n≥1,都有︱f(n)︱≤C︱g(n)︱,則稱函數(shù)f(n)是O(g(n))。多項(xiàng)式時(shí)間算法:指數(shù)時(shí)間算法:O(nlogn)、O(n2.8)、O(n2)O(n!)、O(3n)第22頁，課件共57頁，創(chuàng)作于2023年2月§1.2計(jì)算復(fù)雜性問題多項(xiàng)式時(shí)間算法好算法有效算法指數(shù)時(shí)間算法壞算法惡劣算法Note:A

算法的計(jì)算復(fù)雜性為O(n80)，A

是好算法嗎？與O(2n)比較問題D是否有多項(xiàng)式時(shí)間算法是問題的固有性質(zhì).第23頁，課件共57頁，創(chuàng)作于2023年2月§1.2計(jì)算復(fù)雜性問題三、P類、NP類、NP—完全問題、NP—難問題復(fù)雜性分析的另一個(gè)研究方向：對(duì)組合優(yōu)化問題歸類

對(duì)組合優(yōu)化問題π，如果存在一個(gè)求解該問題的多項(xiàng)式時(shí)間算法，則稱π是多項(xiàng)式時(shí)間可解問題。所有多項(xiàng)式時(shí)間可解問題構(gòu)成的集合，稱為

P類問題記為P。π∈PP類問題:（Polynomial）第24頁，課件共57頁，創(chuàng)作于2023年2月§1.2計(jì)算復(fù)雜性問題

如果一個(gè)問題π的輸出（即答案）為YesorNo，則稱問題π為判定問題。判定問題：Example

5

適定性問題（SATisfiability）

已知一組邏輯變量的一個(gè)布爾表達(dá)式，其中每個(gè)邏輯變量的取值為1（真）或0（假）。問是否存在該組邏輯變量的取值，使得布爾表達(dá)式取值為真？第25頁，課件共57頁，創(chuàng)作于2023年2月§1.2計(jì)算復(fù)雜性問題Example

6

（TSP）已知完全圖G上每一條邊（vi,vj）的權(quán)wij，及常數(shù)h。問是否存在一個(gè)H-圈C，使得Example

7

（LP）給定常數(shù)z

，是否有

顯然，判定問題不比原優(yōu)化問題更難。可以證明兩個(gè)問題在計(jì)算復(fù)雜性意義下是等價(jià)的。第26頁，課件共57頁，創(chuàng)作于2023年2月§1.2計(jì)算復(fù)雜性問題NP

類問題：（NondeterministicPolynomial）

給定一個(gè)判定問題D

，如果存在一個(gè)算法，對(duì)

D的任何一個(gè)答案為“是”的實(shí)例，它給出的回答均可經(jīng)多項(xiàng)式時(shí)間界的運(yùn)算加以檢驗(yàn)，則稱

D

為一個(gè)NP問題。

由全體NP

問題構(gòu)成的集合，稱為NP

類問題。記為

NP

SAT、TSP、LP∈NP第27頁，課件共57頁，創(chuàng)作于2023年2月§1.2計(jì)算復(fù)雜性問題

P但是，多項(xiàng)式時(shí)間可驗(yàn)證性不能保證多項(xiàng)式時(shí)間可解性TSPNPP世界難題問：P=NP?

可以這樣說嗎？顯然不行！第28頁，課件共57頁，創(chuàng)作于2023年2月§1.2計(jì)算復(fù)雜性問題在對(duì)P=NP

的研究中，?

1972年加拿大數(shù)學(xué)家

Cook

提供了一個(gè)漂亮的理論，把前人的失敗歸結(jié)為一個(gè)深刻的數(shù)學(xué)猜想，提出了存在一類稱之為NP–complete

類的問題。Definition4

設(shè)D1，D2

為兩個(gè)判定問題，若求解D2的算法

A2

可多項(xiàng)式次地調(diào)用求解D1的算法A1而實(shí)現(xiàn)，則稱問題D2可以多項(xiàng)式時(shí)間歸約為D1。簡記：

D2D1

第29頁，課件共57頁，創(chuàng)作于2023年2月§1.2計(jì)算復(fù)雜性問題Theorem

1D1∈P，則

D2

∈P

。多項(xiàng)式的四則運(yùn)算及復(fù)合，仍是多項(xiàng)式定理1說明如果

D2D1，則D1不會(huì)比

D2易解（在計(jì)算復(fù)雜性意義下）。Definition5

一個(gè)判定問題Q

被稱為是NP-c問題，如果1、Q∈NP2、任何NP問題均可多項(xiàng)式時(shí)間歸約為Q。如果

D2D1，第30頁，課件共57頁，創(chuàng)作于2023年2月§1.2計(jì)算復(fù)雜性問題

SAT∈NP-c這是Cook首先的證明結(jié)果TSP、IP∈NP-c已證有4000余個(gè)問題NP-c

類問題有如下十分有趣的性質(zhì)：1、任何NP-c

問題都不能用任何已知的多項(xiàng)式時(shí)間算法求解；

2、任何一個(gè)NP-c問題有多項(xiàng)式時(shí)間算法，則一切NP-c問題都有多項(xiàng)式時(shí)間算法。

第31頁，課件共57頁，創(chuàng)作于2023年2月§1.2計(jì)算復(fù)雜性問題

對(duì)一個(gè)新的組合優(yōu)化問題E

，在找不到解它的有效算法時(shí)，可去證明E

∈NP-c.主要證明NP-c

某一問題可多項(xiàng)式時(shí)間歸約為E如果成立，則有如下常用方法：1、尋找盡可能快的算法求解；(如：分枝定界法、單純形法)2、在給定假設(shè)下，對(duì)具體問題提出解的有效算法；3、提出啟發(fā)式算法（最好是近似算法），快速地得到滿意解。（如：貪婪算法、遺傳算法）第32頁，課件共57頁，創(chuàng)作于2023年2月§1.2計(jì)算復(fù)雜性問題LP

∈P

若任何NP問題均可多項(xiàng)式時(shí)間歸約為判定問題D

，則稱D為NP-hard（難）問題.NP-hard問題：NP-c

問題與NP-h

問題的區(qū)別是

NP-h

問題無須判斷D是否屬于

NP.?單純形法是否是有效算法？1972年，美國數(shù)學(xué)家Klee和Minty

構(gòu)造了一個(gè)著名例子，證明了單純形算法不是多項(xiàng)式時(shí)間算法，而是指數(shù)時(shí)間算法.不是第33頁，課件共57頁，創(chuàng)作于2023年2月§1.2計(jì)算復(fù)雜性問題

1979年，蘇聯(lián)數(shù)學(xué)家Khachiyan提出了一個(gè)多項(xiàng)式時(shí)間算法——橢球算法。證明了LP∈P。1984年，美國貝爾實(shí)驗(yàn)室28歲的印度人提出了以他自己名字命名的Karmarkar

算法Note返回計(jì)算復(fù)雜性是以最壞的實(shí)例來評(píng)價(jià)一個(gè)算法。通過概率分析方法，發(fā)現(xiàn)單純形法的平均迭代次數(shù)為O(n

1.5~n2).所以，它的實(shí)用和有效在LP的計(jì)算和應(yīng)用中，幾乎占據(jù)了絕對(duì)優(yōu)勢(shì)。第34頁，課件共57頁，創(chuàng)作于2023年2月§1.3啟發(fā)式算法

在光滑函數(shù)極值的數(shù)值求解中，鄰域是一個(gè)非常重要的概念。函數(shù)的下降或上升都是在一點(diǎn)的鄰域中尋求變化方向，組合優(yōu)化中，距離的概念通常不再使用，但是在一點(diǎn)附近搜索另一個(gè)下降的點(diǎn)仍然是組合優(yōu)化數(shù)值求解的基本思想。一、鄰域第35頁，課件共57頁，創(chuàng)作于2023年2月§1.3啟發(fā)式算法

D上的一個(gè)映射N：

N：s∈DDefinition6對(duì)于組合優(yōu)化問題（D，F(xiàn)，f

），稱為一個(gè)鄰域映射，其中2D表示D的所有子集組成的集合（冪集），N(s)稱為s的鄰域，s’∈

N（s）稱為s的一個(gè)鄰居。N(s)∈2D第36頁，課件共57頁，創(chuàng)作于2023年2月§1.3啟發(fā)式算法對(duì)TSP,

{0,1}3:{(0,0,0),(0,0,1)(0,1,0),(0,1,1)(1,0,0),(1,0,1)(1,1,0),(1,1,1)}可以定義它的一種鄰域?yàn)椋簁為一個(gè)正整數(shù)。

這個(gè)鄰域定義使得x最多有k個(gè)位置的值可以發(fā)生變化，x的鄰居有1+C1n(n-1)+C2n(n-1)+…+Ckn(n-1)個(gè).Example

8第37頁，課件共57頁，創(chuàng)作于2023年2月§1.3啟發(fā)式算法

定義鄰域映射為2-opt

即s中的兩個(gè)元素進(jìn)行對(duì)換,N(s)中共包含s的C2n個(gè)鄰居。Example

9TSP問題解的另一種表示法為D=F={S=(i1,i2,…,in)|i1,i2,…,in

是1,2,…,n的一個(gè)排列}

如四個(gè)城市的TSP問題，當(dāng)s=(1,2,3,4)時(shí)，N(s)

={（2，1，3，4），（3，2，1，4），（4，2，3，1），（1，3，2，4），（1，4，3，2），（1，2，4，3）}第38頁，課件共57頁，創(chuàng)作于2023年2月§1.3啟發(fā)式算法Definition7若s*滿足

則稱s*為f在F上的局部（local）最?。ㄗ畲螅┙?f(s*)≤(≥)f(s),其中s∈N(s*)F

若s∈F，則稱s*為f在F上的全局(global)最小(最大)解。這其實(shí)也提供了一種啟發(fā)式算法（heuristicalgorithm）的思想，局部搜索（或鄰域搜索）算法。第39頁，課件共57頁，創(chuàng)作于2023年2月§1.3啟發(fā)式算法二、啟發(fā)式算法定義

一個(gè)基于直觀或經(jīng)驗(yàn)構(gòu)造的算法，在可接受的花費(fèi)（指計(jì)算時(shí)間、占用空間等）下，給出待解決組合優(yōu)化問題每一個(gè)實(shí)例的一個(gè)可行解，該可行解與最優(yōu)解的偏離程度不一定事先可以預(yù)計(jì).則稱該算法為啟發(fā)式算法.

啟發(fā)式算法是相對(duì)于最優(yōu)算法提出的，一個(gè)問題的最優(yōu)算法，求得該問題每個(gè)實(shí)例的最優(yōu)解,啟發(fā)式算法是一種技術(shù)。Definition8第40頁，課件共57頁，創(chuàng)作于2023年2月§1.3啟發(fā)式算法Definition9

設(shè)A是一個(gè)問題，記問題A的任何一個(gè)實(shí)例I的最優(yōu)解和啟發(fā)式算法H解的目標(biāo)值分別為Zopt(I)和ZH(I),于是對(duì)某個(gè)a>0,稱H是A的a-近似算法（a-approximationalgorithm）,當(dāng)且僅當(dāng)

|ZH(I)-Zopt(I)|≤a|Zopt(I)|

用啟發(fā)式概念定義的算法集合包含了近似算法概念定義的算法集合，近似算法強(qiáng)調(diào)給出算法最壞情況的誤差界限，而啟發(fā)式算法不需考慮偏差程度。

第41頁，課件共57頁，創(chuàng)作于2023年2月§1.3啟發(fā)式算法算法為:

step1

任選一個(gè)初始解so

∈

S；

step2

在N(so)中按某一規(guī)則選一s，若

f(s)<f(so)，則so:=s

返回step2；否則，N(so):=N(so)-s;若N(so)=ф，停止;否則，返回step2.Example

10簡單的鄰域搜索（localsearch）算法

給定組合優(yōu)化問題，假設(shè)其鄰域結(jié)構(gòu)已確定，設(shè)S為可行解集合，f為S上的費(fèi)用函數(shù)，N為鄰域結(jié)構(gòu)。第42頁，課件共57頁，創(chuàng)作于2023年2月§1.3啟發(fā)式算法簡單的鄰域搜索達(dá)到一個(gè)局部最優(yōu)點(diǎn)依賴于初始解選取、鄰域結(jié)構(gòu)、鄰域選點(diǎn)的規(guī)則啟發(fā)式算法的長處：1）數(shù)學(xué)模型是實(shí)際問題的簡化，有可能使最優(yōu)算法所得解比啟發(fā)式算法所得解產(chǎn)生更大誤差；

2）不少難的組合優(yōu)化問題可能還沒找到有效的最優(yōu)算法；

3）一些啟發(fā)式算法可以用在最優(yōu)算法中，如在分支定界算法中，可以用啟發(fā)式算法估界；

第43頁，課件共57頁，創(chuàng)作于2023年2月§1.3啟發(fā)式算法

4）簡單易行，比較直觀，易被使用者接受；

5）速度快，在適時(shí)管理中非常重要；

6）多數(shù)情況下，程序簡單，因此易于修改。

1）不能保證求得最優(yōu)解；

啟發(fā)式算法的不足：

2）表現(xiàn)不穩(wěn)定；3）算法的好壞依賴于實(shí)際問題、經(jīng)驗(yàn)和設(shè)計(jì)者的技術(shù)，使不同算法之間難以比較。

第44頁，課件共57頁，創(chuàng)作于2023年2月§1.3啟發(fā)式算法三、常見啟發(fā)式算法類型1、一步算法

該算法的特點(diǎn)是：不在兩個(gè)可行解之間選擇，在未終止的迭代中，有可能不是一個(gè)可行解，算法結(jié)束時(shí)得到一個(gè)可行解。

Example

11

最優(yōu)H-回路的路線搜索算法Step1Step2123451382352133

Z=15依賴于數(shù)據(jù)特征和初始點(diǎn)的選取，從2開始可得更好的解第45頁，課件共57頁，創(chuàng)作于2023年2月§1.3啟發(fā)式算法

該算法的特點(diǎn)是：從一個(gè)可行解到另一個(gè)可行解的選擇，通常通過兩個(gè)解的比較而選擇好的解，進(jìn)而作為新的起點(diǎn)進(jìn)行新的迭代，直到滿足一定的要求為止。2、改進(jìn)算法如簡單的鄰域搜索算法。

四個(gè)城市{1，2，3，4}的TSP問題，兩個(gè)城市i和j之間的距離dij構(gòu)成的距離矩陣為

Example

12

TSP中簡單的2-opt方法f(so)=d12+d23+d34+d41=5+7+6+12=30設(shè)初始點(diǎn)為so=(1,2,3,4)則第46頁，課件共57頁，創(chuàng)作于2023年2月§1.3啟發(fā)式算法

so的2-opt鄰域是對(duì)so的任兩個(gè)元素對(duì)換，如果固定第一個(gè)城市1，即

簡單的2-opt方法是比較鄰域中的所有點(diǎn)，選出最好解。比較可知N(so)中最好的解為s1

=(1,2,4,3),目標(biāo)值f(s1)=29,下一次迭代是以s1重復(fù)以上的計(jì)算過程，直到目標(biāo)值無法改進(jìn)為止。

N(so)={(1,3,2,4),(1,4,3,2),(1,2,4,3)}◆數(shù)學(xué)規(guī)劃算法、解空間松弛算法、現(xiàn)代優(yōu)化算法第47頁，課件共57頁，創(chuàng)作于2023年2月§1.3啟發(fā)式算法四．啟發(fā)式算法的性能分析

◆評(píng)價(jià)啟發(fā)式算法的性能有不同的角度，主要分為：（1）對(duì)算法復(fù)雜性的分析（2）對(duì)算法計(jì)算效能的分析對(duì)隨機(jī)算法還要考慮穩(wěn)定性◆性能分析的常用方法（1）最壞情形分析（2）概率分析（3）大規(guī)模計(jì)算分析

每個(gè)方法都可以從以上兩個(gè)角度進(jìn)行分析第48頁，課件共57頁，創(chuàng)作于2023年2月§1.3啟發(fā)式算法（1）最壞情形分析

從最壞情形分析評(píng)價(jià)一個(gè)算法的計(jì)算效果時(shí)，其評(píng)價(jià)的指標(biāo)是計(jì)算解的目標(biāo)值同最優(yōu)目標(biāo)值最壞情形時(shí)的差距，這個(gè)差距越小，說明算法越好。

Definition10

若D是一個(gè)極大化問題，實(shí)例I的最優(yōu)值為Zopt(I),啟發(fā)式算法H所得的解值為ZH(I)，記

則啟發(fā)式算法H的絕對(duì)性能比RH定義為{}rIRrRHIH3￡=)(1sup第