1

1.1引言

1.1.1優(yōu)化問題

1.1.2傳統(tǒng)優(yōu)化方法

1.1.3現(xiàn)代優(yōu)化方法

1.2最優(yōu)化問題及其分類

1.2.1函數(shù)優(yōu)化問題

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

1.3啟發(fā)式算法

1.3.1啟發(fā)式算法的定義

1.3.2啟發(fā)式算法的分類

1.3.3啟發(fā)式算法的性能分析

1.4計算復雜性與NP完全問題

1.4.1計算復雜性的基本概念

1.4.2P,NP,NP-C和NP-hard

智能優(yōu)化計算2

1.1引言

智能優(yōu)化計算優(yōu)化技術？以數(shù)學為基礎，解決各種工程問題優(yōu)化解優(yōu)化技術的用途系統(tǒng)控制人工智能模式識別生產(chǎn)調(diào)度

……

1.1.1優(yōu)化問題

3

1.1引言

智能優(yōu)化計算最優(yōu)化問題的描述

最優(yōu)化問題的數(shù)學模型的一般描述：

1.1.1優(yōu)化問題

4

1.1引言

智能優(yōu)化計算待解決的問題

連續(xù)性問題，以微積分為基礎，規(guī)模較小、多峰多谷傳統(tǒng)的優(yōu)化方法

理論上的準確與完美，主要方法：線性與非線性規(guī)劃、動態(tài)規(guī)劃、多目標規(guī)劃、整數(shù)規(guī)劃等；排隊論、庫存論、對策論、決策論等。

傳統(tǒng)的評價方法

算法收斂性、收斂速度

1.1.2傳統(tǒng)優(yōu)化方法

5

1.1引言

智能優(yōu)化計算待解決的問題

離散性、不確定性、大規(guī)模現(xiàn)代的優(yōu)化方法啟發(fā)式算法（heuristicalgorithm）追求滿意（近似解）實用性強（解決實際工程問題）現(xiàn)代的評價方法算法復雜性

1.1.3現(xiàn)代優(yōu)化方法

6

1.2最優(yōu)化問題及其分類（函數(shù)優(yōu)化和組合優(yōu)化）智能優(yōu)化計算數(shù)學表述

難點高維多峰值

1.2.1函數(shù)優(yōu)化問題

7

1.2.2常見求解方法

1.一維函數(shù)優(yōu)化

優(yōu)選法：黃金分割法、分數(shù)法、正交實驗設計特點：只能解決單峰函數(shù)的最優(yōu)值問題搜索法：按照某種方向（如最速下降方向、梯度方向）選取步長搜索（是一種迭代技術）2.多維函數(shù)優(yōu)化

特點：迭代+搜索選取初始點、按照某個方向（如最速下降方向、梯度方向）選取步長搜索最速下降法、梯度與共軛梯度法、Newton法（擬Newton法）等等一般只能解決單峰函數(shù)的最優(yōu)化問題（why?)8

測試函數(shù)（8）GeneralizedSchwefel’sProblem2.26(multimodal)典型的多峰、多谷函數(shù)，確定性算法求解很可能導致局部最優(yōu)9

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算（1）SphereModel(unimodal)

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題

10

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)（2）Schwefel’sProblem2.22(unimodal)

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題11

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)（3）Schwefel’sProblem1.2

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題12

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)（4）Schwefel’sProblem2.21

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題13

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)（5）GeneralizedRosenbrock’sFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題14

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)（6）StepFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題15

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)（6）StepFunction

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題16

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)（7）QuarticFunctioni.e.Niose

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題17

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)（8）GeneralizedSchwefel’sProblem2.26

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題18

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)（8）GeneralizedSchwefel’sProblem2.26(multimodal)

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題19

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)（9）GeneralizedRastrigin’sFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題20

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)（10）Ackley’sFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題21

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)（10）Ackley’sFunction

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題22

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)（11）GeneralizedGriewankFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題23

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)（11）GeneralizedGriewankFunction

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題24

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)（12）GeneralizedPenalizedFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題25

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)其中，

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題26

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)（13）GeneralizedPenalizedFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題27

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)（14）Shekel’sFoxholesFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題28

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)其中，

1.2.3函數(shù)優(yōu)化之常見的

Benchmark問題29

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)（15）Kowalik’sFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題30

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)其中，

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題31

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)（16）Six-HumpCamel-BackFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題32

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)（17）BraninFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的

Benchmark問題33

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)（18）Goldstein-PriceFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題34

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)（19）Hartman’sFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題35

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)（20）Hartman’sFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題36

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)（21）Shekel’sFamily

m分別取5，7和10，其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題37

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)（22）J.D.Schaffer

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題38

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算測試函數(shù)（22）J.D.Schaffer

此函數(shù)在距全局最優(yōu)點大約3.14范圍內(nèi)存在無窮多個局部極小將其包圍，并且函數(shù)強烈振蕩。

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題39

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算有約束的函數(shù)優(yōu)化常用受約束測試函數(shù)；影響因素：（1）曲面拓撲性質(zhì)，線性或凸函數(shù)比無規(guī)律的函數(shù)更容易求解；（2）可行區(qū)域的疏密程度，通常以可行區(qū)域占整個搜索空間的比值來度量；

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題40

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算有約束的函數(shù)優(yōu)化常用受約束測試函數(shù)；影響因素：（3）整個搜索空間中整體最優(yōu)解與可行區(qū)域最優(yōu)解之比，特別當整體最憂解離可行區(qū)域很近時將使其對懲罰項非常敏感；（4）在最優(yōu)解處活躍約束的數(shù)目，活躍約束數(shù)目越多則最優(yōu)解離可行區(qū)域的邊界越近。

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題41

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算數(shù)學表述所屬范疇涉及離散事件的最優(yōu)編排、分類、次序篩選等問題，是運籌學的一個重要分支。

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

42

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算典型問題——旅行商問題（Travelingsalesmanproblem,TSP）給定n個城市和兩兩城市之間的距離，要求確定一條經(jīng)過各城市當且僅當一次的最短路線。

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

12341218103243TSP問題實例10城市TSP問題20城市TSP問題44TSP問題實例230城市TSP問題48城市TSP問題45

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算典型問題——旅行商問題（Travelingsalesmanproblem,TSP）計算復雜度：指數(shù)災難

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

城市數(shù)2425262728293031計算時間1sec24sec10min4.3hour4.9day136.5day10.8year325year46

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算典型問題——加工調(diào)度問題（Schedulingproblem,如Flow-shop,Job-shop）

Job-shop：n個工件在m臺機器上加工，Oij：第i個工件在第j臺機器上的操作，Tij：相應的操作時間已知。事先給定各工件在各機器上的加工次序（技術約束條件），要求確定與技術約束條件相容的各機器上所有工件的加工順序，使得加工性能指標達到最優(yōu)。若各工件技術約束條件相同，轉化為Flow-shop。

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

47

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算典型問題——加工調(diào)度問題（Schedulingproblem,如Flow-shop,Job-shop）計算復雜性：可能的排列方式有（n！）m

多目標優(yōu)化動態(tài)性狀態(tài)相依

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

48

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算典型問題——0－1背包問題（Knapsackproblem）對于n個體積為ai、價值分別為ci的物品，如何將它們裝入總體積為b的背包中，使得所選物品的總價值最大。

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

背包問題的貪婪算法49

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算典型問題——裝箱問題（Binpackingproblem）有n個尺寸不超過1的物品，有數(shù)個尺寸為1的箱子，如何將這些物品裝入箱子，使得所需箱子的個數(shù)最少。

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

50

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算典型問題——圖著色問題（Graphcoloringproblem）對于n個頂點的無環(huán)圖G，要求對其各個頂點進行著色，使得任意兩個相鄰的頂點都有不同的顏色，且所用顏色種類最少。

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

C1：第一種顏色C2：第二種顏色C3：第三種顏色C1C1C2C3C2ABDCE51

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算典型問題——聚類問題（Clusteringproblem）

m維空間上的n個模式{Xi|i=1,2,…,n}，要求聚成k類，使得各類本身內(nèi)的點最相近，如要求其中Rp為第p類的中心，即

其中，p=1,2,…,k，np為第p類中的點數(shù)。

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

52

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算典型問題——任務分配問題（TaskAssignmentProblemTAP）

TAP是把一個應用程序（application)的任務（Tasks）分配到分布式計算系統(tǒng)中的計算機上，目標是優(yōu)化某個或某幾個性能指標。

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

53

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算典型問題——任務分配問題（TAP）

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

54

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算

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

典型問題——任務分配問題（TAP）

應用程序用任務交互圖（TaskInteractionGraphTIG）G(V,ET)表示，其中V=(1,2,…m)表示任務集合，ET表示邊的集合，每條邊表示任務之間的交互（通信）。55

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算

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

典型問題——任務分配問題（TaskAssignmentProblemTAP）

分布式計算系統(tǒng)用處理機交互圖（ProcessorsInteractionGraphPIG）G(P,ET)表示，其中P=(1,2,…n)表示系統(tǒng)中處理機的集合，ET表示通信鏈路的集合，每條邊表示一條通信鏈路。56

1.2最優(yōu)化問題及其分類

智能優(yōu)化計算

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

典型問題——任務分配問題（TaskAssignmentProblemTAP）

我們這里仿真局域網(wǎng)分布式計算系統(tǒng)。并假設處理機異構（Heterogeneous）,及每個任務在各個處理機上的執(zhí)行時間不同；網(wǎng)絡同構，即所有鏈路的通信速度相同。

57

智能優(yōu)化計算

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

典型問題——任務分配問題（TAP）

優(yōu)化目標1：最小化執(zhí)行代價與通信代價之和1.2最優(yōu)化問題及其分類任務執(zhí)行代價：處理機之間的通信代價：58

1.2最優(yōu)化問題及其分類智能優(yōu)化計算

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

典型問題——任務分配問題（TAP）

優(yōu)化目標1：最小化執(zhí)行代價與通信代價之和分配方案A總代價：TAP的目標是找到一種具有最小代價的分配方案：59

1.2最優(yōu)化問題及其分類智能優(yōu)化計算

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

典型問題——任務分配問題（TAP）也可描述為有約束的0-1二次整數(shù)規(guī)劃問題：其中r是任務數(shù)，n是處理機數(shù)，mi是任務i的存儲需求，pi是任務i的計算負載需求。60

智能優(yōu)化計算

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

典型問題——任務分配問題（TAP）

優(yōu)化目標2：最小化周轉時間（turnaroundtime)1.2最優(yōu)化問題及其分類分配到處理機k上的任務總的執(zhí)行代價：分配到處理機k上的任務與分配到其它處理機上的任務總的通信代價：61

智能優(yōu)化計算

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

典型問題——任務分配問題（TAP）

優(yōu)化目標2：最小化周轉時間（turnaroundtime)1.2最優(yōu)化問題及其分類對于某一給定的分配方案A，處理機k總的執(zhí)行代價：62

智能優(yōu)化計算

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

典型問題——任務分配問題（TAP）

優(yōu)化目標2：最小化周轉時間（turnaroundtime)1.2最優(yōu)化問題及其分類一個分配方案的最終代價（finalcost）由具有最大Ctotal(A)值的處理機,即由負載最重的處理機決定：此時，TAP的目標是找到一種具有最小代價的分配方案，即負載盡量均衡：63

1.3啟發(fā)式算法（Heuristic）

智能優(yōu)化計算最優(yōu)算法一個問題的最優(yōu)算法求得該問題每個實例的最優(yōu)解；啟發(fā)式算法一個基于直觀或經(jīng)驗構造的算法，在可接受的花費（計算時間、占用空間等）下給出待解決優(yōu)化問題每一個實例的一個可行解，該可行解與最優(yōu)解的偏離程度不一定事先可以預計。

1.3.1啟發(fā)式算法的定義

64

1.3啟發(fā)式算法

智能優(yōu)化計算啟發(fā)式算法的特點是一種技術；不能保證所得解的最優(yōu)性；啟發(fā)式算法的發(fā)展歷史

20世紀40年代——起步

20世紀60～70年代——被鄙視

20世紀70年代——觀點轉變

20世紀80年代至今——研究熱潮

1.3.1啟發(fā)式算法的定義

65

1.3啟發(fā)式算法

智能優(yōu)化計算例子——背包問題的貪婪算法（Greedyalgorithm）

貪婪算法：采用逐步構造最優(yōu)解的方法。在每個階段，都作出一個看上去最優(yōu)的決策（在一定的標準下）。決策一旦作出，就不可再更改。作出貪婪決策的依據(jù)稱為貪婪準則（greedycriterion）。

1.3.1啟發(fā)式算法的定義

66

1.3啟發(fā)式算法

智能優(yōu)化計算例子——背包問題的貪婪算法（Greedyalgorithm）STEP1STEP2

1.3.1啟發(fā)式算法的定義

67

1.3啟發(fā)式算法

智能優(yōu)化計算啟發(fā)式算法的優(yōu)點

1.模型誤差、數(shù)據(jù)不精確性、參數(shù)估計誤差等可能造成最優(yōu)算法的解比啟發(fā)式算法的解更差；

2.復雜問題無法求得最優(yōu)算法或最優(yōu)算法太復雜；

3.簡單易行，直觀，程序簡單。啟發(fā)式算法的缺點

1.不能保證最優(yōu)；

2.不穩(wěn)定；

3.依賴于實際問題、設計者經(jīng)驗。

1.3.1啟發(fā)式算法的定義

68

1.3啟發(fā)式算法

智能優(yōu)化計算簡單直觀的算法

一步算法：不在兩個可行解之間比較，在未終止的迭代過程中，得到的中間解有可能不是可行解；例：背包問題的貪婪算法

改進算法：迭代過程是從一個可行解到另一個可行解變換，通過兩個解的比較而選擇好的解，直到滿足一定的要求為止；例：TSP問題的2－opt方法

1.3.2啟發(fā)式算法的分類

P1P6P2P5P3P42203122224434369

1.3啟發(fā)式算法

智能優(yōu)化計算

數(shù)學規(guī)劃算法用連續(xù)優(yōu)化（如線性規(guī)劃）的方法求解組合優(yōu)化問題（如整數(shù)線性規(guī)劃模型），其中包括一些啟發(fā)式規(guī)則。基于數(shù)學規(guī)劃的理論。

1.3.2啟發(fā)式算法的分類

70

1.3啟發(fā)式算法

智能優(yōu)化計算現(xiàn)代優(yōu)化算法禁忌搜索算法模擬退火算法遺傳算法人工神經(jīng)網(wǎng)絡蟻群算法粒子群算法混合算法

1.3.2啟發(fā)式算法的分類

特點：基于客觀世界中的一些自然現(xiàn)象；建立在計算機迭代計算的基礎上；具有普適性，可解決實際應用問題。71

1.3啟發(fā)式算法

智能優(yōu)化計算評價算法優(yōu)劣的指標算法的復雜性（計算效率）解的偏離程度（計算效果）算法的穩(wěn)健性（不同實例、不同時間、不同起點的差異）評價算法優(yōu)劣的手段最壞情況分析（純理論）概率分析（理論分析）計算模擬分析（統(tǒng)計特性）

1.3.3啟發(fā)式算法的性能分析

72

1.4計算復雜性與NP完全問題

智能優(yōu)化計算時間復雜性和空間復雜性概念

算法的時間復雜性：算法對時間的需要量（加、減、乘、除、比較、讀、寫等操作的總次數(shù)）；

算法的空間復雜性：算法對空間的需要量（存儲空間的大小，二進制位數(shù)）；

問題的時間復雜性：所有算法中時間復雜性最小的算法時間復雜性；

問題的空間復雜性：所有算法中空間復雜性最小的算法空間復雜性；

1.4.1計算復雜性的基本概念

73

1.4計算復雜性與NP完全問題

智能優(yōu)化計算復雜性問題分類

P類、NP類、NP完全類復雜性表示方法復雜性表示為問題規(guī)模n（如TSP的n）的函數(shù)，時間復雜性T(n)，關鍵操作的次數(shù)；空間復雜性S(n)，占用的存儲單元數(shù)量；

1.4.1計算復雜性的基本概念

74

1.4計算復雜性與NP完全問題

智能優(yōu)化計算復雜性表示方法若算法A的時間復雜性為TA(n)=O(p(n))，O(p(n))為復雜性函數(shù)p(n)主要項的階，且p(n)為n的多項式函數(shù)，則稱算法A為多項式(polynomial)算法。

當不存在多項式函數(shù)p(n)時，稱相應的算法為非多項式時間算法或指數(shù)時間算法；隨著變量的增加，多項式函數(shù)增長的速度比指數(shù)函數(shù)和非多項式函數(shù)增長的速度要慢得多。

1.4.1計算復雜性的基本概念

75

1.4計算復雜性與NP完全問題

智能優(yōu)化計算P類問題（deterministicpolynomial）

具有多項式時間求解算法的問題類迄今為止，許多組合優(yōu)化問題都沒有找到求最優(yōu)解的多項式時間算法。NP類問題(Nondeterministicpolynomial)

定義1實例是問題的特殊表現(xiàn)，所謂實例就是確定了描述問題特性的所有參數(shù)的問題，其中參數(shù)值稱為數(shù)據(jù)，這些數(shù)據(jù)占有計算機的空間稱為實例的輸入長度。

1.4.2P,NP,NP-C和NP-hard

76

1.4計算復雜性與NP完全問題

智能優(yōu)化計算NP類問題(Nondeterministicpolynomial)

定義2若一個問題的每個實例只有“是”或“否”兩種回答，則稱該問題為判定問題。例，TSP的判定問題：給定z，是否存在n個城市的一個排列W，使得f(W)≤z。滿足f(W)≤z的一個排列W稱為判定問題的“是”答案（可行解）。

1.4.2P,NP,NP-C和