運(yùn)籌學(xué)基礎(chǔ) 課件 第2章VIP

第2章樸素優(yōu)化范式2.1生成測(cè)試范例2.2

枚舉法2.3深度優(yōu)先搜索2.4廣度優(yōu)先搜索2.5貪婪算法2.6啟發(fā)式算法2.7拓展應(yīng)用:玻璃球硬度測(cè)試實(shí)驗(yàn)設(shè)計(jì)問(wèn)題

2.1生成測(cè)試范例

在最直觀的決策模式中,我們會(huì)構(gòu)造一個(gè)解決方案并檢測(cè)是否滿足約束條件,如果不滿足約束條件,就再構(gòu)造一個(gè)解決方案,直到找到一個(gè)滿足約束條件的解決方案為止,這樣的為問(wèn)題找到解決方案的決策思路稱為生成測(cè)試范例。這適合于尋找可行解的問(wèn)題,可行解之間無(wú)優(yōu)劣之分。

例2-2(八皇后問(wèn)題)在國(guó)際象棋8×8的棋盤(pán)上,要擺放8個(gè)皇后,但是要保證沒(méi)有任意兩個(gè)皇后可以相互攻擊,也即要求沒(méi)有任意兩個(gè)皇后處在相同的行、列或?qū)蔷€上。如圖2-1所示,如果深色方格代表為皇后選擇的位置,則圖2-1(a)所示的為一個(gè)可行的方案,而圖2-1(b)所示的是不可行的方案,因?yàn)椴环先我鈨蓚€(gè)皇后都不能處在同一對(duì)角線上的約束。

圖2-1八皇后問(wèn)題的生成測(cè)試范例

對(duì)于八皇后問(wèn)題來(lái)講,基本的解決范式就是生成測(cè)試范例,也就是生成一個(gè)解決方案,判斷是否可行,如果可行,算法結(jié)束,否則再生成另外一個(gè)解決方案。不同的解決方案之間并無(wú)優(yōu)劣之分,問(wèn)題的目標(biāo)只是要找到一個(gè)滿足條件的解決方案。

2.2

枚舉法

枚舉法就是檢測(cè)決策對(duì)應(yīng)的每一種可能的解決方案,并比較它們的優(yōu)劣,從中選擇出最好的方案。枚舉法的好處是能夠確切無(wú)誤地找到問(wèn)題的最優(yōu)解,并且實(shí)現(xiàn)起來(lái)簡(jiǎn)單易行,但是顯然不適合連續(xù)變量?jī)?yōu)化問(wèn)題以及可能解決方案數(shù)量過(guò)于龐大的問(wèn)題。

例2-3(人民幣組合問(wèn)題)假設(shè)我們有8種不同面值的人民幣{1,5,10,50,100,200,500,1000},單位為分,用這些面值的人民幣組合構(gòu)成一個(gè)給定的數(shù)值n。例如,n=3000,問(wèn)總共有多少種可能的組合方式?

如果假設(shè)8種人民幣的數(shù)量分別為xi(i=1,…,8),則可以確定各個(gè)變量的取值范圍如表2-1所示。

使用枚舉的方法需要搜索的狀態(tài)空間中包含的解的數(shù)量為各個(gè)維度狀態(tài)數(shù)量的乘積,也即4.5991e+14,這樣的狀態(tài)空間規(guī)模使用一般的計(jì)算機(jī)尚可在忍受的時(shí)間范圍內(nèi)完成。

例如,在處理器為Intel(R)Core(TM)i77500UCPU@2.70GHz,內(nèi)存為8GB的聯(lián)想筆記本電腦上,使用Matlab計(jì)算n=30000的人民幣組合問(wèn)題,花費(fèi)時(shí)間為2285.5秒,代碼如下:

然而對(duì)于很多實(shí)際問(wèn)題的搜索狀態(tài)空間,枚舉法多數(shù)是不可忍受的。當(dāng)然,枚舉法在很多情況下計(jì)算時(shí)間的不可忍受也是可被利用的,否則,密碼可被暴力破解,網(wǎng)上銀行和保密通信就有麻煩了。

例2-4(n皇后問(wèn)題)針對(duì)例2-2的八皇后問(wèn)題,將其一般化后就是n皇后問(wèn)題,在一個(gè)n×n的棋盤(pán)上擺放n個(gè)皇后保證相互沒(méi)有攻擊可能。請(qǐng)問(wèn)n皇后問(wèn)題有多少種可行的方案?

對(duì)于n皇后問(wèn)題,需要檢查的組合數(shù)量為n!。對(duì)于八皇后問(wèn)題,可以使用枚舉的辦法統(tǒng)計(jì)可行方案的數(shù)量。但是對(duì)于數(shù)量越大的n皇后問(wèn)題,枚舉法就越不可行,因?yàn)樾枰杜e的方案的數(shù)量呈指數(shù)級(jí)增長(zhǎng)。例如,n=20,需要檢查的組合數(shù)量為20!=2.433×1018,使用枚舉法來(lái)檢查已經(jīng)不現(xiàn)實(shí)了。

2.3深度優(yōu)先搜索

深度優(yōu)先搜索(Deep-FirstSearch,DFS)是一種基于圖數(shù)據(jù)結(jié)構(gòu)的枚舉法?？梢赃@樣理解,圖中的節(jié)點(diǎn)都有一定的層次關(guān)系,所有的從同一個(gè)點(diǎn)a出發(fā)通過(guò)弧能夠直接一步到達(dá)的點(diǎn)bi∈B是同級(jí)的,這是廣度上的衡量,而a稱為bi的上級(jí),bi稱作a的下級(jí),如圖2-2所示。所謂深度優(yōu)先,就是當(dāng)前點(diǎn)往下走的時(shí)候,優(yōu)先選擇第一個(gè)未走過(guò)的下級(jí)節(jié)點(diǎn),不優(yōu)先到達(dá)一個(gè)未走過(guò)的同級(jí)節(jié)點(diǎn)。

圖2-2-節(jié)點(diǎn)的層次結(jié)構(gòu)及深度和廣度衡量

例2-5(拼圖問(wèn)題)對(duì)于一個(gè)2×2拼圖問(wèn)題來(lái)講,給定初始排列和目標(biāo)排列如圖23所示,要想從初始排列達(dá)到目標(biāo)排列,請(qǐng)問(wèn)要進(jìn)行怎樣的操作才可以達(dá)到目的?

為了描述問(wèn)題更加方便,將拼圖的一個(gè)排列稱為拼圖的一個(gè)狀態(tài),對(duì)拼圖的操作抽象為四種操作:空格上移、空格下移、空格右移、空格左移。

圖2-3拼圖問(wèn)題的初始排列和目標(biāo)排列

步驟1:初始狀態(tài)為s0,按照順序通過(guò)操作集中的某種操作后,狀態(tài)轉(zhuǎn)移關(guān)系如圖2-4所示,因此狀態(tài)s0的下級(jí)節(jié)點(diǎn)有2個(gè)。圖2-4拼圖問(wèn)題步驟1

步驟2:按照深度優(yōu)先搜索的規(guī)則,當(dāng)前狀態(tài)點(diǎn)s0往下走的時(shí)候,優(yōu)先選擇第一個(gè)未走過(guò)的下級(jí)節(jié)點(diǎn)s11,也就是如

圖2-5所示的狀態(tài)轉(zhuǎn)移關(guān)系。圖2-5拼圖問(wèn)題步驟2

步驟3:當(dāng)前狀態(tài)s11與目標(biāo)狀態(tài)不同,則按照操作集判

斷下一個(gè)階段狀態(tài),如圖2-6所示。圖2-6拼圖問(wèn)題步驟3

步驟4:按照深度優(yōu)先搜索的規(guī)則,當(dāng)前狀態(tài)點(diǎn)s11往下走的時(shí)候,優(yōu)先選擇第一個(gè)未走過(guò)的下級(jí)節(jié)點(diǎn)s21,也就是如圖2-7所示的狀態(tài)轉(zhuǎn)移關(guān)系。

圖2-7拼圖問(wèn)題步驟4

以此類推,直到算法停止,搜索過(guò)程如圖2-8所示。

圖2-8深度優(yōu)先搜索用于拼圖問(wèn)題的搜索序列

2.4廣度優(yōu)先搜索

例2-6(拼圖問(wèn)題)同樣,對(duì)于一個(gè)2×2拼圖問(wèn)題來(lái)講,給定初始狀態(tài)和目標(biāo)狀態(tài)如圖2-9所示,要想從初始狀態(tài)達(dá)到目標(biāo)狀態(tài),也可以使用廣度優(yōu)先搜索的辦法尋找解決方案。

圖2-92×2拼圖問(wèn)題的初始狀態(tài)和目標(biāo)狀態(tài)

步驟1:初始狀態(tài)為s0,按照順序通過(guò)操作集中的某種操作后,狀態(tài)轉(zhuǎn)移關(guān)系如圖2-10所示,因此狀態(tài)s0的下級(jí)節(jié)點(diǎn)有2個(gè)。圖2-102×2拼圖問(wèn)題的步驟1

步驟2:初始狀態(tài)點(diǎn)s0的下級(jí)狀態(tài)節(jié)點(diǎn)包括s11和s12,按照廣度優(yōu)先搜索的規(guī)則,優(yōu)先搜索同級(jí)的狀態(tài)節(jié)點(diǎn),也就是如圖2-11所示的狀態(tài)轉(zhuǎn)移關(guān)系。圖2-112×2拼圖問(wèn)題的步驟2

步驟3:從狀態(tài)s11開(kāi)始,按照操作集判斷下一個(gè)階段狀態(tài),如圖2-12所示,因此當(dāng)前狀態(tài)s11的下級(jí)節(jié)點(diǎn)只有s21。圖2-12-2×2拼圖問(wèn)題的步驟3

步驟4:從狀態(tài)s12開(kāi)始,按照操作集判斷下一個(gè)階段狀態(tài),如圖2-13所示,因此當(dāng)前狀態(tài)的下級(jí)節(jié)點(diǎn)只有s22。圖2-132×2拼圖問(wèn)題的步驟4

步驟5:按照廣度優(yōu)先搜索的規(guī)則,搜索的狀態(tài)轉(zhuǎn)移如圖2-14所示(從上往下、從左至右的生成順序)。圖2-142×2拼圖問(wèn)題的步驟5

步驟6:以此類推,直到搜索到的某個(gè)狀態(tài)和目標(biāo)狀態(tài)相同,算法停止,搜索過(guò)程如圖2-15所示。

圖2-15廣度優(yōu)先搜索用于2×2拼圖還原的搜索序列

2.5貪婪算法

貪婪算法是指,在對(duì)問(wèn)題求解的每個(gè)子階段或者步驟中,總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō),不從整體最優(yōu)上加以考慮,所做出的是在某種意義上的局部最優(yōu)解。

例2-7有三種物品A、B、C,單位物品的重量分別為1、2、3,單位物品的價(jià)值分別為3、2、1,背包的最大載重為4,請(qǐng)問(wèn)可裝入背包的物品的最大價(jià)值是多少?

例2-8有三種物品A、B、C,單位物品的重量分別為1、2、3,單位物品的價(jià)值分別為15、33、50,背包的最大載重為4,請(qǐng)問(wèn)可裝入背包的物品的最大價(jià)值是多少?

按照貪婪算法的思想,要想裝入物品的總價(jià)值最高,那么單位價(jià)值應(yīng)該也比較高,因此,計(jì)算三種物品的單位價(jià)值分別為

因此,貪婪算法不一定能保證得到最優(yōu)解。關(guān)于背包問(wèn)題,可以建立線性規(guī)劃模型求解,也可以利用動(dòng)態(tài)規(guī)劃求解(參見(jiàn)5.4節(jié))。

貪婪算法看起來(lái)有點(diǎn)只顧眼前不顧長(zhǎng)遠(yuǎn),甚至有人形容其為“飲鴆止渴”。但是在許多情況下,貪婪算法簡(jiǎn)單直接并且好用,很多問(wèn)題使用貪婪算法可以得到令人滿意的解。如果再進(jìn)一步優(yōu)化,往往要花費(fèi)較大的建設(shè)成本和付出艱辛的努力,并且個(gè)體的努力還依賴于整體信息化計(jì)算環(huán)境的支持。因此,在現(xiàn)實(shí)中,貪婪算法非常好用,在許多粗放式管理與

運(yùn)用中,運(yùn)籌學(xué)的很多優(yōu)良的算法被束之高閣。

2.6啟發(fā)式算法

所謂啟發(fā)式算法,指的是受物理生物運(yùn)行進(jìn)化規(guī)律(如模擬退火算法、煙花算法、遺傳算法)、生物智能(如蟻群算法、蜂群算法、狼群算法等)、人類解決問(wèn)題的“經(jīng)驗(yàn)”“知識(shí)”的啟發(fā)(如旅行商問(wèn)題的最近鄰算法和插入算法等、運(yùn)輸問(wèn)題的最小元素法和伏格爾法等),通過(guò)模仿尋優(yōu)規(guī)則、模式而得出來(lái)的算法。啟發(fā)式算法一般能比較快速地找到滿意解,對(duì)于很多復(fù)雜問(wèn)題雖然不能保證給出最優(yōu)解,但是起碼能給出不錯(cuò)的解。其缺點(diǎn)是不能保證得到最優(yōu)解,甚至對(duì)解的質(zhì)量通常也很難做出判斷。

例2-9對(duì)于如圖2-16所示的迷宮問(wèn)題,請(qǐng)使用扶墻算法找到一條從入口到出口的路。所謂扶墻算法,就是從入口處開(kāi)始,假設(shè)人在行進(jìn)的過(guò)程中,始終要左手(或者右手)扶著墻不能離開(kāi)。扶墻算法就借鑒了人類的知識(shí)和經(jīng)驗(yàn):“順藤摸瓜”。

圖2-16迷宮問(wèn)題

例2-10對(duì)于如圖2-16所示的迷宮問(wèn)題,請(qǐng)使用隨機(jī)老鼠算法求解從入口到出口的路。所謂隨機(jī)老鼠算法,就是從入口處開(kāi)始往前走,每當(dāng)走到分岔口的時(shí)候,就隨機(jī)決定往哪個(gè)方向走。隨機(jī)老鼠算法模仿了自然界中的老鼠的行為,最終也能找到出口,但是一般花費(fèi)的時(shí)間相對(duì)較長(zhǎng)。

2.7拓展應(yīng)用:玻璃球硬度測(cè)試實(shí)驗(yàn)設(shè)計(jì)問(wèn)題

有一棟100層高的大樓,給你兩個(gè)完全相同的玻璃球。假設(shè)從某一層開(kāi)始往上,丟下玻璃球會(huì)摔碎,現(xiàn)在要測(cè)試這個(gè)臨界層數(shù),作為玻璃球硬度的度量。那么怎么利用手中的兩個(gè)球,用最少的測(cè)試次數(shù),測(cè)試玻璃球的硬度呢?假如只有一個(gè)球,那么很顯然,只有一個(gè)辦法:從第一層開(kāi)始投,如果沒(méi)碎再試第二層、第三層等,也就是只能使用枚舉法進(jìn)行實(shí)驗(yàn)。其實(shí)驗(yàn)次數(shù)的分布與玻璃球?qū)嶋H硬度之間的關(guān)系如圖2-17所示。

圖2-17枚舉法實(shí)驗(yàn)次數(shù)與實(shí)際硬度之間的關(guān)系

現(xiàn)在有兩個(gè)球,當(dāng)然也可以使用枚舉法,但是實(shí)驗(yàn)次數(shù)沒(méi)有降低。我們使用生成測(cè)試范例的辦法明顯可以找到一個(gè)實(shí)驗(yàn)次數(shù)更少的方案:第一個(gè)球在50層往下扔,如果碎了,說(shuō)明玻璃球的硬度小于50,無(wú)須再測(cè)試50以上的樓層,如果玻璃球沒(méi)碎,則只需要測(cè)試50以上的樓層,通過(guò)這樣簡(jiǎn)單的二分法可以降低有可能的實(shí)驗(yàn)次數(shù)。其最壞情況下實(shí)驗(yàn)次數(shù)的分布與玻璃球?qū)嶋H硬度之間的關(guān)系如圖2-18所示。

圖2-18二分法的實(shí)驗(yàn)次數(shù)與實(shí)際硬度之間的關(guān)系

為了使最壞