第十三章 分支限界法

1、 第五部分第五部分 克服困難性克服困難性 第十三章第十三章 回溯法和分支限界法回溯法和分支限界法 (二二) 第十三章第十三章 回溯法和分支限界法回溯法和分支限界法( (二二) ) 13.4 13.4 分支限界法分支限界法 1313. .5 5 分支限界法的應(yīng)用分支限界法的應(yīng)用 1313. .5.1 5.1 單源最短路徑問題單源最短路徑問題 13. 13.5.2 0/15.2 0/1背包問題背包問題 13. 13.5.3 5.3 旅行商問題旅行商問題 13.5.4 13.5.4 指派問題指派問題 13.5.5 13.5.5 批處理作業(yè)問題批處理作業(yè)問題 本章采用知識發(fā)明的第一條線，即方本章采用知

2、識發(fā)明的第一條線，即方法法應(yīng)用為主線安排內(nèi)容。應(yīng)用為主線安排內(nèi)容。13.4 分支限界法分支限界法1. 分支限界法與回溯法的不同分支限界法與回溯法的不同 a. 搜索策略的不同：回溯法以深度優(yōu)先的方搜索策略的不同：回溯法以深度優(yōu)先的方式搜索解空間樹；式搜索解空間樹； 回溯法采用深度優(yōu)先的方式，朝縱深方向搜回溯法采用深度優(yōu)先的方式，朝縱深方向搜索，直至達(dá)到問題的一個(gè)可行解，或經(jīng)判斷沿此索，直至達(dá)到問題的一個(gè)可行解，或經(jīng)判斷沿此路徑不會達(dá)到問題的可行解或最優(yōu)解時(shí)，停止向路徑不會達(dá)到問題的可行解或最優(yōu)解時(shí)，停止向前搜索，并沿原路返回到該路徑上最后一個(gè)還可前搜索，并沿原路返回到該路徑上最后一個(gè)還可擴(kuò)展的結(jié)

3、點(diǎn)。從該結(jié)點(diǎn)出發(fā)朝新的方向縱深搜索。擴(kuò)展的結(jié)點(diǎn)。從該結(jié)點(diǎn)出發(fā)朝新的方向縱深搜索。 分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹，將活結(jié)點(diǎn)存放在一個(gè)特殊的方式搜索解空間樹，將活結(jié)點(diǎn)存放在一個(gè)特殊的表中。其策略是：在擴(kuò)展結(jié)點(diǎn)處，先生成其所的表中。其策略是：在擴(kuò)展結(jié)點(diǎn)處，先生成其所有的兒子結(jié)點(diǎn)有的兒子結(jié)點(diǎn), ,將那些導(dǎo)致不可行解或?qū)е路亲顚⒛切?dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子舍棄，其余兒子加入活結(jié)點(diǎn)表中。此優(yōu)解的兒子舍棄，其余兒子加入活結(jié)點(diǎn)表中。此后，從活結(jié)點(diǎn)表中按照一定的規(guī)則取出一個(gè)結(jié)點(diǎn)后，從活結(jié)點(diǎn)表中按照一定的規(guī)則取出一個(gè)結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)。并

4、重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。作為當(dāng)前擴(kuò)展結(jié)點(diǎn)。并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。 b. 分支限界法不僅通過分支限界法不僅通過約束條件約束條件, 而且可通而且可通過過目標(biāo)函數(shù)的限界目標(biāo)函數(shù)的限界來減少無效搜索。來減少無效搜索。2. 分支限界法的基本思想分支限界法的基本思想 分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問題的解空間樹。大效益）優(yōu)先的方式搜索問題的解空間樹。 在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會成為擴(kuò)展結(jié)點(diǎn)?；罱Y(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就會成為擴(kuò)展結(jié)點(diǎn)?；罱Y(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這

5、些兒子結(jié)點(diǎn)中，一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。 此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。這個(gè)過程一展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。這個(gè)過程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。3. 常見的兩種分支限界法常見的兩種分支限界法 隊(duì)列式隊(duì)列式(FIFO)分支限界法分支限界法 按照隊(duì)列先進(jìn)先出（按照隊(duì)列先進(jìn)先出（FIFO）原則選取

6、下一個(gè)原則選取下一個(gè)節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)。節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)。 優(yōu)先隊(duì)列式分支限界法優(yōu)先隊(duì)列式分支限界法 按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級選取優(yōu)先級最按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。 隊(duì)列式分支限界法隊(duì)列式分支限界法的搜索解空間樹的方式的搜索解空間樹的方式類似于解空間樹的寬度優(yōu)先搜索，不同的是隊(duì)列類似于解空間樹的寬度優(yōu)先搜索，不同的是隊(duì)列式分支限界法不搜索已不可行結(jié)點(diǎn)（已經(jīng)被判定式分支限界法不搜索已不可行結(jié)點(diǎn)（已經(jīng)被判定不能導(dǎo)致可行解或不能導(dǎo)致最優(yōu)解的結(jié)點(diǎn)）為根不能導(dǎo)致可行解或不能導(dǎo)致最優(yōu)解的結(jié)點(diǎn)）為根的子樹。按照規(guī)則，這樣的結(jié)點(diǎn)不被列入活結(jié)點(diǎn)的子樹。

7、按照規(guī)則，這樣的結(jié)點(diǎn)不被列入活結(jié)點(diǎn)表。表。 優(yōu)先隊(duì)列式分支限界法優(yōu)先隊(duì)列式分支限界法的搜索方式是根據(jù)的搜索方式是根據(jù)活結(jié)點(diǎn)的優(yōu)先級確定下一個(gè)擴(kuò)展結(jié)點(diǎn)。結(jié)點(diǎn)的優(yōu)活結(jié)點(diǎn)的優(yōu)先級確定下一個(gè)擴(kuò)展結(jié)點(diǎn)。結(jié)點(diǎn)的優(yōu)先級常用一個(gè)與該結(jié)點(diǎn)有關(guān)的先級常用一個(gè)與該結(jié)點(diǎn)有關(guān)的限界函數(shù)值限界函數(shù)值p來表來表示。示。 最大優(yōu)先隊(duì)列規(guī)定最大優(yōu)先隊(duì)列規(guī)定p值較大的結(jié)點(diǎn)的優(yōu)先級值較大的結(jié)點(diǎn)的優(yōu)先級較高。在算法實(shí)現(xiàn)時(shí)通常用一個(gè)較高。在算法實(shí)現(xiàn)時(shí)通常用一個(gè)最大堆最大堆來實(shí)現(xiàn)最來實(shí)現(xiàn)最大優(yōu)先隊(duì)列，體現(xiàn)大優(yōu)先隊(duì)列，體現(xiàn)最大效益優(yōu)先最大效益優(yōu)先的原則。的原則。 最小優(yōu)先隊(duì)列規(guī)定最小優(yōu)先隊(duì)列規(guī)定p值較小的結(jié)點(diǎn)的優(yōu)先級值較小的結(jié)點(diǎn)的優(yōu)先級較

8、高。在算法實(shí)現(xiàn)時(shí)，常用一個(gè)較高。在算法實(shí)現(xiàn)時(shí)，常用一個(gè)最小堆最小堆來實(shí)現(xiàn)，來實(shí)現(xiàn)，體現(xiàn)體現(xiàn)最小優(yōu)先最小優(yōu)先的原則。的原則。 采用優(yōu)先隊(duì)列式分支限界算法解決具體問題采用優(yōu)先隊(duì)列式分支限界算法解決具體問題時(shí)，應(yīng)根據(jù)問題的特點(diǎn)選用最大優(yōu)先或最小優(yōu)先時(shí)，應(yīng)根據(jù)問題的特點(diǎn)選用最大優(yōu)先或最小優(yōu)先隊(duì)列，確定各個(gè)結(jié)點(diǎn)的隊(duì)列，確定各個(gè)結(jié)點(diǎn)的p值。值。 4. 限界函數(shù)的構(gòu)造限界函數(shù)的構(gòu)造n限界函數(shù)要能夠提供一個(gè)評定候選擴(kuò)展結(jié)點(diǎn)的限界函數(shù)要能夠提供一個(gè)評定候選擴(kuò)展結(jié)點(diǎn)的方法，以便確定哪個(gè)結(jié)點(diǎn)最有可能在通往目標(biāo)方法，以便確定哪個(gè)結(jié)點(diǎn)最有可能在通往目標(biāo)的最佳路徑上。的最佳路徑上。n一個(gè)限界函數(shù)一個(gè)限界函數(shù)f(d)通?？?/p>

9、以由兩個(gè)部分構(gòu)成：通?？梢杂蓛蓚€(gè)部分構(gòu)成：從開始結(jié)點(diǎn)到結(jié)點(diǎn)從開始結(jié)點(diǎn)到結(jié)點(diǎn)d的已有耗損值的已有耗損值g(d)；再；再從結(jié)點(diǎn)從結(jié)點(diǎn)d到達(dá)目標(biāo)的期望耗損值到達(dá)目標(biāo)的期望耗損值h(d)。即：。即：f(d) = g(d) + h(d)n通常通常g(d)的構(gòu)造較易，的構(gòu)造較易，h(d)的構(gòu)造較難。的構(gòu)造較難。5. 優(yōu)先隊(duì)列分支限界算法的設(shè)計(jì)思想優(yōu)先隊(duì)列分支限界算法的設(shè)計(jì)思想(模式模式)n首先，確定一個(gè)合理的首先，確定一個(gè)合理的限界函數(shù)限界函數(shù)，并根據(jù)限界函數(shù)，并根據(jù)限界函數(shù)確定問題的目標(biāo)函數(shù)的界確定問題的目標(biāo)函數(shù)的界down, up；n然后，按照廣度優(yōu)先策略遍歷問題的解空間樹：然后，按照廣度優(yōu)先策略遍歷

10、問題的解空間樹： 當(dāng)搜索到達(dá)一個(gè)擴(kuò)展結(jié)點(diǎn)時(shí)，一次性擴(kuò)展它的所有孩當(dāng)搜索到達(dá)一個(gè)擴(kuò)展結(jié)點(diǎn)時(shí)，一次性擴(kuò)展它的所有孩子，估算子，估算每一個(gè)每一個(gè)孩子結(jié)點(diǎn)的孩子結(jié)點(diǎn)的目標(biāo)函數(shù)的上目標(biāo)函數(shù)的上(下下)界值界值(又又稱為稱為耗費(fèi)函數(shù)值耗費(fèi)函數(shù)值)； 將那些滿足約束條件且將那些滿足約束條件且耗費(fèi)函數(shù)值耗費(fèi)函數(shù)值不超過不超過目標(biāo)函數(shù)的目標(biāo)函數(shù)的界界的孩子，插入的孩子，插入活結(jié)點(diǎn)表活結(jié)點(diǎn)表H中，再從中，再從H表中取耗費(fèi)函表中取耗費(fèi)函數(shù)值極大數(shù)值極大(小小)的下一結(jié)點(diǎn)同樣擴(kuò)展；的下一結(jié)點(diǎn)同樣擴(kuò)展； 直到找到所需的解或直到找到所需的解或H表為空為止。表為空為止。 對于對于H中的中的葉子結(jié)點(diǎn)葉子結(jié)點(diǎn) 其其耗費(fèi)函數(shù)值是

11、極值耗費(fèi)函數(shù)值是極值(極大或極小極大或極小)，則該葉子結(jié)點(diǎn)對應(yīng)的解就，則該葉子結(jié)點(diǎn)對應(yīng)的解就是問題的最優(yōu)解；是問題的最優(yōu)解； 否則否則，調(diào)整問題的目標(biāo)函數(shù)的界為該葉子結(jié)點(diǎn)的耗費(fèi)函數(shù)值，調(diào)整問題的目標(biāo)函數(shù)的界為該葉子結(jié)點(diǎn)的耗費(fèi)函數(shù)值，然后丟棄然后丟棄H表中超出目標(biāo)函數(shù)界的結(jié)點(diǎn)，再次選取結(jié)點(diǎn)繼續(xù)擴(kuò)表中超出目標(biāo)函數(shù)界的結(jié)點(diǎn)，再次選取結(jié)點(diǎn)繼續(xù)擴(kuò)展。展。13.5.1 單源最短路徑問題單源最短路徑問題 1. 1. 問題描述問題描述 下面以一個(gè)例子來說明單源最短路徑問題：在下面以一個(gè)例子來說明單源最短路徑問題：在下圖所給的有向圖下圖所給的有向圖G中，每一邊都有一個(gè)非負(fù)中，每一邊都有一個(gè)非負(fù)邊權(quán)。要求圖邊權(quán)。

12、要求圖G的從源頂點(diǎn)的從源頂點(diǎn)s到目標(biāo)頂點(diǎn)到目標(biāo)頂點(diǎn)t之間之間的最短路徑。的最短路徑。o o234372922153242222413.5 分支限界法的應(yīng)用分支限界法的應(yīng)用n單源最短路徑問題的限界函數(shù)的構(gòu)造：單源最短路徑問題的限界函數(shù)的構(gòu)造：n f(d)=g(d)+h(d)ng(d)定義為從源定義為從源s到結(jié)點(diǎn)到結(jié)點(diǎn)d所走的路徑長度：所走的路徑長度：g(d) = g(p) + Cpd這里這里p為為d的前驅(qū)結(jié)點(diǎn)，的前驅(qū)結(jié)點(diǎn)，Cpd為為p到到d的距離。的距離。nh(d)定義為定義為0。于是。于是f(d) = g(d)。n源源s的評價(jià)函數(shù)的評價(jià)函數(shù)f(s) = 0。 n限界函數(shù)的下界為限界函數(shù)的下界為

13、0；上界初始時(shí)為；上界初始時(shí)為，以后不斷，以后不斷用取得的更短路徑的長度來替代。用取得的更短路徑的長度來替代。2. 算法思想算法思想 單源最短路徑問題為極小優(yōu)化問題，因此可用一個(gè)單源最短路徑問題為極小優(yōu)化問題，因此可用一個(gè)極小堆極小堆來存儲活結(jié)點(diǎn)表。來存儲活結(jié)點(diǎn)表。Input：有向圖：有向圖G；Output：從源點(diǎn)：從源點(diǎn)s到終點(diǎn)到終點(diǎn)t的最短路徑長度。的最短路徑長度。n1. 設(shè)定目標(biāo)函數(shù)的限界設(shè)定目標(biāo)函數(shù)的限界down=0，up=n2. 計(jì)算初始結(jié)點(diǎn)計(jì)算初始結(jié)點(diǎn)1的的f(1)=0，將初始結(jié)點(diǎn)插入最小堆，將初始結(jié)點(diǎn)插入最小堆H;n3. while (H ) n4. n5. 從從H中做中做DEL

14、ETEMIN的操作，用的操作，用p帶回相應(yīng)結(jié)點(diǎn)帶回相應(yīng)結(jié)點(diǎn);n6. 產(chǎn)生產(chǎn)生p的所有滿足約束條件的后繼結(jié)點(diǎn)的所有滿足約束條件的后繼結(jié)點(diǎn)d并計(jì)算并計(jì)算f(d)；n7. while 對每個(gè)結(jié)點(diǎn)對每個(gè)結(jié)點(diǎn)dn8. if f(d)down then 10. if f(d)down then 11. 11. 將將d d結(jié)點(diǎn)插入最大堆結(jié)點(diǎn)插入最大堆H H中；中；12. if d12. if d是葉子結(jié)點(diǎn)是葉子結(jié)點(diǎn) then then 13. down=f(d);13. down=f(d);14. 14. 刪除活結(jié)點(diǎn)表刪除活結(jié)點(diǎn)表( (最大堆最大堆H)H)中函數(shù)值小于中函數(shù)值小于downdown值的結(jié)點(diǎn)；值

15、的結(jié)點(diǎn)；15. 15. 16. 16. 17. 17. 18. 18. 算法算法13.5.2 旅行商問題旅行商問題201042056105304630算法思路算法思路:設(shè)周游路線從結(jié)點(diǎn)設(shè)周游路線從結(jié)點(diǎn)1開始開始,解為元組解為元組X=(1,x2,.xn) xi 2,.,n. 則解空間樹為排列樹，在樹中做廣度優(yōu)先搜則解空間樹為排列樹，在樹中做廣度優(yōu)先搜索。索。 約束條件約束條件: xi xj ,i j;目標(biāo)函數(shù)目標(biāo)函數(shù):解向量對應(yīng)的邊權(quán)之和解向量對應(yīng)的邊權(quán)之和Cijn限界函數(shù)：限界函數(shù)：n f(d)=g(d)+h(d)ng(d)定義為從結(jié)點(diǎn)定義為從結(jié)點(diǎn)1到結(jié)點(diǎn)到結(jié)點(diǎn)d所走的路徑長度；所走的路徑長度

16、；nh(d)定義為定義為0。于是。于是f(d) = g(d)。n限界函數(shù)的下界為限界函數(shù)的下界為0；上界初始時(shí)為；上界初始時(shí)為。 旅行商問題為極小優(yōu)化問題，因此可用一個(gè)旅行商問題為極小優(yōu)化問題，因此可用一個(gè)極小堆極小堆來存儲活結(jié)點(diǎn)表。來存儲活結(jié)點(diǎn)表。1. 旅行商問題的隊(duì)列分支限界法旅行商問題的隊(duì)列分支限界法111130306 64 42525595926262525141424242. 旅行商問題的優(yōu)先隊(duì)列分支限界法旅行商問題的優(yōu)先隊(duì)列分支限界法分支限界法求分支限界法求TSP的搜索的搜索 25 40 31 27 5 17 30 2519 15 6 1 9 50 24 622 8 7 10 10

17、2253404315272342455550523533443742813555473249440235246542873614290找到了第一條周游路找到了第一條周游路線線153421，其長度為其長度為95。這不是最短周游路線，需要修改上界后繼續(xù)搜索。這不是最短周游路線，需要修改上界后繼續(xù)搜索。算法算法Input：圖：圖G=(V,E),頂點(diǎn)編號為頂點(diǎn)編號為1到到n；Output：從：從1頂點(diǎn)出發(fā)的最短巡回旅行路線。頂點(diǎn)出發(fā)的最短巡回旅行路線。n1. 設(shè)定目標(biāo)函數(shù)的限界設(shè)定目標(biāo)函數(shù)的限界down=0，up=n2. 計(jì)算初始結(jié)點(diǎn)計(jì)算初始結(jié)點(diǎn)1的的f(1)=0，將初始結(jié)點(diǎn)插入最小堆，將初始結(jié)點(diǎn)插入

18、最小堆H;n3. while (H ) n4. n5. 從從H中做中做DELETEMIN的操作，用的操作，用p帶回相應(yīng)結(jié)點(diǎn)帶回相應(yīng)結(jié)點(diǎn);n6. 產(chǎn)生產(chǎn)生p的所有滿足約束條件的后繼結(jié)點(diǎn)的所有滿足約束條件的后繼結(jié)點(diǎn)d并計(jì)算并計(jì)算f(d)；n7. while 對每個(gè)結(jié)點(diǎn)對每個(gè)結(jié)點(diǎn)dn8. if f(d)up then n9. if d是葉子結(jié)點(diǎn)是葉子結(jié)點(diǎn) thenn10. up=f(p);n11. 刪除活結(jié)點(diǎn)表刪除活結(jié)點(diǎn)表(最小堆最小堆H)中函數(shù)值大于中函數(shù)值大于up值的結(jié)點(diǎn)；值的結(jié)點(diǎn)；n12. if (H=) then n13. 從葉子結(jié)點(diǎn)沿從葉子結(jié)點(diǎn)沿parent指針輸出解，退出；指針輸出解，退

19、出；n14. n15. else 將將d結(jié)點(diǎn)插入最小堆結(jié)點(diǎn)插入最小堆H中；中；n16. n17. n18. 歸約矩陣以及約數(shù)歸約矩陣以及約數(shù)n前面的搜索的效率不高，幾乎要搜索全部的狀態(tài)空間。前面的搜索的效率不高，幾乎要搜索全部的狀態(tài)空間。其原因是評價(jià)函數(shù)以及上下界的估計(jì)太低。為了設(shè)計(jì)其原因是評價(jià)函數(shù)以及上下界的估計(jì)太低。為了設(shè)計(jì)求解求解TSP問題的更好的評價(jià)函數(shù)，先定義其代價(jià)矩陣問題的更好的評價(jià)函數(shù)，先定義其代價(jià)矩陣的歸約矩陣和約數(shù)。的歸約矩陣和約數(shù)。n給定代價(jià)矩陣給定代價(jià)矩陣C，從，從C的任何行的任何行i(或列或列j)的各元素中減的各元素中減去此行去此行(或此列或此列)的最小元素的值的最小元

20、素的值r(i)(或或r(j)，稱為對，稱為對i行行(或或j列列)的歸約。將的歸約。將C的各行和各列都?xì)w約后的矩陣的各行和各列都?xì)w約后的矩陣稱為稱為C的歸約矩陣。和數(shù)的歸約矩陣。和數(shù)r = in r(i) + in r(j) 稱為稱為C的約數(shù)。的約數(shù)。歸約矩陣和約數(shù)舉例歸約矩陣和約數(shù)舉例n計(jì)算下面例子中的歸約矩陣及其約數(shù)如下：計(jì)算下面例子中的歸約矩陣及其約數(shù)如下： 25 40 31 27 5 17 30 2519 15 6 1 9 50 24 622 8 7 10 先做行歸約：r(1)=25 0 15 6 2r(2)=5 0 12 25 20r(3)=118 14 5 0r(4)=6 3 44

21、21 0r(5)=715 1 0 3 再做列歸約：再做列歸約：r(1)=r(2)=r(3)=r(5)=0 r(4)=33222 0n約數(shù)約數(shù) r = 47。約數(shù)是周游路線長度的下界約數(shù)是周游路線長度的下界n定理：設(shè)定理：設(shè)C是圖是圖G的代價(jià)矩陣，的代價(jià)矩陣，P是周游路線，是周游路線，則則P的代價(jià)，即的代價(jià)，即P cij = r + P cij ， 式中式中C = cij是是C的歸約矩陣，的歸約矩陣，r為約數(shù)。為約數(shù)。n證明：由歸約矩陣的構(gòu)造可知：證明：由歸約矩陣的構(gòu)造可知：cij = cij r(i) r(j) 即即cij = cij + r(i) + r(j)。n 任何周游路線包含任何周游路

22、線包含n條邊并且對應(yīng)在條邊并且對應(yīng)在C中的中的每行每列有且僅有一條邊。于是每行每列有且僅有一條邊。于是P cij = P(cij + r(i) + r(j)。r + P cij 。 定義期望函數(shù)定義期望函數(shù)h(d)n對開始結(jié)點(diǎn)對開始結(jié)點(diǎn)1，令，令g(1) = 0，h(1) = r，f(1) = r。n若從結(jié)點(diǎn)若從結(jié)點(diǎn)1選擇了一條邊，不妨設(shè)邊選擇了一條邊，不妨設(shè)邊，則，則令令g(2) = f(1)+從從1到到2的距離的距離l ，顯然，顯然l應(yīng)該是應(yīng)該是c12，而不應(yīng)該再是而不應(yīng)該再是c12了。了。 n那么那么h(2) = ？n自然可以想到自然可以想到h(2)可以是從可以是從2開始的路線的下界開始

23、的路線的下界r2。是否也可用類似求。是否也可用類似求r一樣去求新的約數(shù)一樣去求新的約數(shù)r2呢？呢？n可以，但在此之前應(yīng)將邊可以，但在此之前應(yīng)將邊和所有邊和所有邊和邊和邊都刪去，即置都刪去，即置c12、c1k和和ck2為為。n設(shè)設(shè)Cp為某路線上結(jié)點(diǎn)為某路線上結(jié)點(diǎn)p的歸約矩陣。從的歸約矩陣。從p選擇選擇邊邊所得到結(jié)點(diǎn)所得到結(jié)點(diǎn)d的歸約矩陣的歸約矩陣Cd和約數(shù)和約數(shù)rd為：為：n(1)將將Cp中的中的ccdpdp， cpk和和ckd置為置為，1kn；n(2)依照求歸約矩陣依照求歸約矩陣C的方法對的方法對Cp進(jìn)行行歸約進(jìn)行行歸約和列歸約，便得到了和列歸約，便得到了Cd和和rd 。n令令f(1) = g

24、(1) + h(1)，其中，其中g(shù)(1) = 0，h(1) = r。n對任意路線上的結(jié)點(diǎn)對任意路線上的結(jié)點(diǎn)d，設(shè)，設(shè)p是其前驅(qū)結(jié)點(diǎn)，則是其前驅(qū)結(jié)點(diǎn)，則f(d) = g(d) + h(d)， 其中，其中，g(d) = f(p) + Cppd， h(d) = rd。用新的評價(jià)函數(shù)求用新的評價(jià)函數(shù)求TSPn下面用新的評價(jià)函數(shù)求前面的例子，我們已經(jīng)求下面用新的評價(jià)函數(shù)求前面的例子，我們已經(jīng)求得了它的歸約矩陣得了它的歸約矩陣C和約數(shù)和約數(shù)r = 47。 0 15 3 2 0 12 22 2018 14 2 0 3 44 18 015 1 0 0 1472g(2) = 47 + 0 = 47 0 1080

25、1512h(2) = 12 + 3 = 15f(2) = 47 +15 = 62623 0 15 3 2 0 12 22 2018 14 2 0 3 44 18 015 1 0 0 g(3) = 47 + 15 = 62 04313h(3) = 1f(3) = 63634類似地可求出 f(4) = 51。515類似地可求出 f(5) = 50。50下面優(yōu)先擴(kuò)展的是結(jié)點(diǎn)5。2此時(shí)C2是在C5的基礎(chǔ)上進(jìn)行。右邊就是C5。 0 12 22 18 14 2 3 44 18 0 0 0 g(2) = 50 + 0 = 50 01601503h(2) = 17f(2) = 67673類似地計(jì)算出f(3)

26、= 68684類似地計(jì)算出f(4) = 8181下面擴(kuò)展f(4) = 51的結(jié)點(diǎn)4。并用同樣方法計(jì)算它們的評價(jià)函數(shù)值。2121369464154 下面要擴(kuò)展的結(jié)點(diǎn) 是f(2)= 62的結(jié)點(diǎn)2。 右邊是其對應(yīng)的歸 約矩陣C2。2 0 10 815 2 0 0 18 012 0 0 3g(3) = 62 + 0 = 62；對C2進(jìn)行歸約， 得h(3) = 0；于是f(3) = 62。62對結(jié)點(diǎn)2的另外兩個(gè)兒子進(jìn)行同樣的計(jì)算，得：f(4) = 84，f(5) = 72。484572下面對f(3) = 62的結(jié)點(diǎn)3進(jìn)行擴(kuò)展。它有兩個(gè)后繼結(jié)點(diǎn)。345對結(jié)點(diǎn)4，g(4) = 62 + 2 = 64。0h(

27、4) = 12 ，于是f(4) = 64 + 12 = 7676對結(jié)點(diǎn)5，g(5) = 62 + 0 = 62。 15 2 0 0 012 0 h(5) = 0，于是f(5) = 62 + 0 = 6262對結(jié)點(diǎn)5(f(5) = 62)再進(jìn)行擴(kuò)展。54g(4) = 62 + 0 = 62，h(4) = 0，f(4) = 62。62結(jié)點(diǎn)4是目標(biāo)結(jié)點(diǎn)，找到了第一條路線。4 這條路線的長度為62，以其為上界。其余未擴(kuò)展的結(jié)點(diǎn)的評價(jià)函數(shù)值均超過上界，因而不再需要擴(kuò)展了。于是找到了一條最短的周于是找到了一條最短的周游路線：游路線：123541。算法算法Input：圖：圖G=(V,E),頂點(diǎn)編號為頂點(diǎn)編號

28、為1到到n；Output：從：從1頂點(diǎn)出發(fā)的最短巡回旅行路線。頂點(diǎn)出發(fā)的最短巡回旅行路線。n1. 設(shè)定目標(biāo)函數(shù)的限界設(shè)定目標(biāo)函數(shù)的限界down=r，up=？n2. 計(jì)算初始結(jié)點(diǎn)計(jì)算初始結(jié)點(diǎn)1的的f(1)=0，將初始結(jié)點(diǎn)插入最小堆，將初始結(jié)點(diǎn)插入最小堆H;n3. while (H ) n4. n5. 從從H中做中做DELETEMIN的操作，用的操作，用p帶回相應(yīng)結(jié)點(diǎn)帶回相應(yīng)結(jié)點(diǎn);n6. 產(chǎn)生產(chǎn)生p的所有滿足約束條件的后繼結(jié)點(diǎn)的所有滿足約束條件的后繼結(jié)點(diǎn)d并計(jì)算并計(jì)算f(d)；n7. while 對每個(gè)結(jié)點(diǎn)對每個(gè)結(jié)點(diǎn)dn8. if f(d)up then n9. if d是葉子結(jié)點(diǎn)是葉子結(jié)點(diǎn) th

29、enn10. up=f(p);n11. 刪除活結(jié)點(diǎn)表刪除活結(jié)點(diǎn)表(最小堆最小堆H)中函數(shù)值大于中函數(shù)值大于up值的結(jié)點(diǎn)；值的結(jié)點(diǎn)；n12. if (H=) then n13. 從葉子結(jié)點(diǎn)沿從葉子結(jié)點(diǎn)沿parent指針輸出解，退出；指針輸出解，退出；n14. n15. else 將將d結(jié)點(diǎn)插入最小堆結(jié)點(diǎn)插入最小堆H中；中；n16. n17. n18. 分支邊與二叉樹分支邊與二叉樹n在構(gòu)造求在構(gòu)造求TSP的搜索樹時(shí)，還有另外一種算法的搜索樹時(shí)，還有另外一種算法稍有點(diǎn)不同，就是將搜索樹構(gòu)造成二叉樹。稍有點(diǎn)不同，就是將搜索樹構(gòu)造成二叉樹。n給定一條最短周游路線給定一條最短周游路線P，對于任一條邊，對于

30、任一條邊只有兩種情況，即只有兩種情況，即 P或者或者 P。n這就可以表示成右邊的二叉樹：這就可以表示成右邊的二叉樹：kmn_n其中其中_表示表示 P。n這樣的邊稱為分支邊。這樣的邊稱為分支邊。用二叉樹求用二叉樹求TSP1250 _3 622453 _5 684664 _7 653862 _9 748 1062 _ 117010 1262 _ 136612 1462 _ 156614 1662 _ 17結(jié)點(diǎn)結(jié)點(diǎn)16給出了一條給出了一條最短周游路線：最短周游路線：12354113.5.4 指派問題指派問題 設(shè)有設(shè)有4個(gè)雇員和個(gè)雇員和4件工作，用下面的矩陣表示件工作，用下面的矩陣表示耗費(fèi)函數(shù)，矩陣中

31、，行耗費(fèi)函數(shù)，矩陣中，行i對應(yīng)于第對應(yīng)于第i個(gè)雇員，第個(gè)雇員，第j列列對應(yīng)于第對應(yīng)于第j件工作。找出一種工作指派使得總耗件工作。找出一種工作指派使得總耗費(fèi)最小。費(fèi)最小。6473458573356425 有一批共有一批共n個(gè)集裝箱要裝上個(gè)集裝箱要裝上2艘載重量分別為艘載重量分別為C1和和C2的輪船，其中集裝箱的輪船，其中集裝箱i的重量為的重量為Wi，且且裝載問題裝載問題211ccwnii裝載問題要求確定是否有一個(gè)合理的裝載方案裝載問題要求確定是否有一個(gè)合理的裝載方案可將這個(gè)集裝箱裝上這可將這個(gè)集裝箱裝上這2 2艘輪船。如果有，找出艘輪船。如果有，找出一種裝載方案。一種裝載方案。容易證明：如果一個(gè)

32、給定裝載問題有解，則采用容易證明：如果一個(gè)給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案。下面的策略可得到最優(yōu)裝載方案。 (1)首先將第一艘輪船盡可能裝滿；首先將第一艘輪船盡可能裝滿； (2)將剩余的集裝箱裝上第二艘輪船。將剩余的集裝箱裝上第二艘輪船。舉例舉例 c1=c2=50, n=3, w=10, 40, 40。 w=20, 40, 40。 1. 隊(duì)列式分支限界法隊(duì)列式分支限界法 2. 優(yōu)先級分支限界法優(yōu)先級分支限界法 無論哪種分支限界法，策略都是盡可能裝滿無論哪種分支限界法，策略都是盡可能裝滿第一艘輪船，剩下的集裝箱能夠裝入第二艘輪船第一艘輪船，剩下的集裝箱能夠裝入第二艘輪船即可。

33、即可。 狀態(tài)空間樹是完全二叉樹，每個(gè)節(jié)點(diǎn)代表當(dāng)狀態(tài)空間樹是完全二叉樹，每個(gè)節(jié)點(diǎn)代表當(dāng)前集裝箱裝入第一艘輪船，或者不裝入第一艘前集裝箱裝入第一艘輪船，或者不裝入第一艘輪輪船船；優(yōu)先級選擇當(dāng)前已裝入的箱子的重量加上剩；優(yōu)先級選擇當(dāng)前已裝入的箱子的重量加上剩下箱子的重量之和。下箱子的重量之和。舉例舉例 ： c1=c2=45, n=4, w=10, 20, 25, 30。 設(shè)設(shè)J1, J2, J3, J4是四項(xiàng)待處理的作業(yè)，它們的工是四項(xiàng)待處理的作業(yè)，它們的工序一樣，即先在序一樣，即先在m1上處理，然后在上處理，然后在m2上處理，上處理，最后在最后在m3上處理，加工時(shí)間矩陣為：上處理，加工時(shí)間矩陣為：

34、批處理作業(yè)問題批處理作業(yè)問題34,)(10875992510975jitTJ1J2J3J4m1m2m3找一種最佳的處理順序，使完成作業(yè)的總時(shí)間找一種最佳的處理順序，使完成作業(yè)的總時(shí)間達(dá)到最短。達(dá)到最短。優(yōu)先級的確定與優(yōu)先級的確定與LC檢索檢索 對于優(yōu)先隊(duì)列式分支限界法，結(jié)點(diǎn)優(yōu)先級的對于優(yōu)先隊(duì)列式分支限界法，結(jié)點(diǎn)優(yōu)先級的確定直接影響著算法性能。我們當(dāng)然希望這樣的確定直接影響著算法性能。我們當(dāng)然希望這樣的活結(jié)點(diǎn)活結(jié)點(diǎn)X成為當(dāng)前擴(kuò)展結(jié)點(diǎn)：成為當(dāng)前擴(kuò)展結(jié)點(diǎn)：1) 以以X為根的子樹中含有問題的答案結(jié)點(diǎn)；為根的子樹中含有問題的答案結(jié)點(diǎn)；2) 在所有滿足條件在所有滿足條件1)的活結(jié)點(diǎn)中，的活結(jié)點(diǎn)中，X距離答

35、案距離答案結(jié)點(diǎn)結(jié)點(diǎn)“最近最近”。 但是，要給可能導(dǎo)致答案結(jié)點(diǎn)的活結(jié)點(diǎn)附但是，要給可能導(dǎo)致答案結(jié)點(diǎn)的活結(jié)點(diǎn)附以優(yōu)先級，必須要附加若干計(jì)算工作，即要付以優(yōu)先級，必須要附加若干計(jì)算工作，即要付出代價(jià)。出代價(jià)。 對于任一結(jié)點(diǎn)，要付出的代價(jià)可以使用兩種標(biāo)對于任一結(jié)點(diǎn)，要付出的代價(jià)可以使用兩種標(biāo)準(zhǔn)來度量：準(zhǔn)來度量：1. 在生成一個(gè)答案結(jié)點(diǎn)之前，子樹在生成一個(gè)答案結(jié)點(diǎn)之前，子樹X需要生成需要生成的結(jié)點(diǎn)數(shù)；的結(jié)點(diǎn)數(shù)；2. 在子樹在子樹X中離中離X最近的那個(gè)答案結(jié)點(diǎn)到最近的那個(gè)答案結(jié)點(diǎn)到X的的路徑長度。路徑長度。 如果使用度量如果使用度量1，在對于每一種分枝限界算法，在對于每一種分枝限界算法，總是生成最小數(shù)目的

36、結(jié)點(diǎn)；總是生成最小數(shù)目的結(jié)點(diǎn)； 如果采用度量如果采用度量2,則要成為擴(kuò)展結(jié)點(diǎn)的結(jié)點(diǎn)只則要成為擴(kuò)展結(jié)點(diǎn)的結(jié)點(diǎn)只是由根到最近的那個(gè)答案結(jié)點(diǎn)路徑上的那些結(jié)是由根到最近的那個(gè)答案結(jié)點(diǎn)路徑上的那些結(jié)點(diǎn)。點(diǎn)。 用用c()表示一個(gè)理想的優(yōu)先級函數(shù)，定義如下：表示一個(gè)理想的優(yōu)先級函數(shù)，定義如下： a) 如果如果X是答案結(jié)點(diǎn)，則是答案結(jié)點(diǎn)，則c(X)是解空間樹中，是解空間樹中，由根結(jié)點(diǎn)到由根結(jié)點(diǎn)到X的成本的成本(即所用的代價(jià)，如級數(shù)、即所用的代價(jià)，如級數(shù)、計(jì)算復(fù)雜度等計(jì)算復(fù)雜度等)； b) 如果如果X不是答案結(jié)點(diǎn)，而且以不是答案結(jié)點(diǎn)，而且以X為根的子樹為根的子樹中不含答案結(jié)點(diǎn)，則中不含答案結(jié)點(diǎn)，則c(X)定義為

37、定義為 ； c) 如果如果X不是答案結(jié)點(diǎn)，但是以不是答案結(jié)點(diǎn)，但是以X為根的子樹為根的子樹中含答案結(jié)點(diǎn)，則中含答案結(jié)點(diǎn)，則c(X)是具有最小成本的答案是具有最小成本的答案結(jié)點(diǎn)的成本。結(jié)點(diǎn)的成本。 如果能夠獲得這樣的優(yōu)先級函數(shù)，則優(yōu)先如果能夠獲得這樣的優(yōu)先級函數(shù)，則優(yōu)先隊(duì)列式分支限界法將以最少的搜索時(shí)間找到問隊(duì)列式分支限界法將以最少的搜索時(shí)間找到問題的解。題的解。 (找這樣的優(yōu)先級函數(shù)是非常困難的找這樣的優(yōu)先級函數(shù)是非常困難的) 實(shí)際問題中都是采用一個(gè)估計(jì)函數(shù)實(shí)際問題中都是采用一個(gè)估計(jì)函數(shù)e，它由它由兩部分決定：解空間樹的根結(jié)點(diǎn)到兩部分決定：解空間樹的根結(jié)點(diǎn)到X的成本的成本f(X)和和X到答案結(jié)

38、點(diǎn)的估計(jì)成本到答案結(jié)點(diǎn)的估計(jì)成本g(X)。 即即 e(X)= f(X)+g(X)。 稱為成本估計(jì)函數(shù)。稱為成本估計(jì)函數(shù)。 根據(jù)成本估計(jì)函數(shù)選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)的策根據(jù)成本估計(jì)函數(shù)選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)的策略總是選取略總是選取e()值最小的活結(jié)點(diǎn)作為下一個(gè)擴(kuò)展值最小的活結(jié)點(diǎn)作為下一個(gè)擴(kuò)展結(jié)點(diǎn)。這種搜索策略稱為最小成本檢索（結(jié)點(diǎn)。這種搜索策略稱為最小成本檢索（Least Cost search），），簡稱簡稱LC-檢索。檢索。如前所講過的如前所講過的裝載問題的成本估計(jì)函數(shù)裝載問題的成本估計(jì)函數(shù)的確定。的確定。 如果取如果取g=0, f(X)等于等于X在解空間樹中的級；在解空間樹中的級； 如果如果f=0，

39、且且g滿足：滿足： Y是是X的兒子的兒子 g(Y) g(X) (13. 1)以后提到的成本函數(shù)以后提到的成本函數(shù)e中中, 函數(shù)函數(shù)g都滿足都滿足(13.1)式。式。 在一個(gè)分成在一個(gè)分成44的棋盤上排列的棋盤上排列15塊號牌塊號牌, 如圖如圖(a)。其中會出現(xiàn)一個(gè)空格。棋盤上號牌的一次合其中會出現(xiàn)一個(gè)空格。棋盤上號牌的一次合法移動(dòng)是指將位于空格上、下、左、右的一塊號法移動(dòng)是指將位于空格上、下、左、右的一塊號牌移入空格。要求通過一系列合法移動(dòng)，將號牌牌移入空格。要求通過一系列合法移動(dòng)，將號牌的初始排列轉(zhuǎn)換成自然排列，如圖的初始排列轉(zhuǎn)換成自然排列，如圖(b)。 1 2 3 45 6 7 89 10

40、 11 1213 14 15(a)1 2 3 45 6 7 89 10 11 1213 14 15(b)例例 15迷問題迷問題 不是任意的初始狀態(tài)都可能達(dá)到目標(biāo)狀態(tài)！不是任意的初始狀態(tài)都可能達(dá)到目標(biāo)狀態(tài)！ 先給棋盤的方格編上先給棋盤的方格編上1-16的號碼。位置的號碼。位置 i 是是在圖在圖(b)所示的目標(biāo)排列中放所示的目標(biāo)排列中放 i 號牌的方格位置，號牌的方格位置，位置位置16是空格的位置。假設(shè)是空格的位置。假設(shè) POSITION( i )是編是編號為號為 i 的那塊牌在初始狀態(tài)下的編號，的那塊牌在初始狀態(tài)下的編號，1=i POSITION( i )的數(shù)目的數(shù)目（j 為任意滿足條件的數(shù)，為

41、任意滿足條件的數(shù)，1= j i）。）。 例如，對于圖例如，對于圖 7.2(a) 所示的狀態(tài)，有所示的狀態(tài)，有 LESS(1) = 0，LESS(16) = 2 。 在初始條件下，如果空格在圖在初始條件下，如果空格在圖(c)的陰影位的陰影位置中的某一格處，則令置中的某一格處，則令 X = 1；否則令；否則令 X = 0。于是有如下定理。于是有如下定理。 # # # # # #(c)161)(iXiLess定理：定理：當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) 是偶數(shù)，才可以從是偶數(shù)，才可以從初始狀態(tài)轉(zhuǎn)變到圖初始狀態(tài)轉(zhuǎn)變到圖(b)(b)所示的目標(biāo)狀態(tài)。所示的目標(biāo)狀態(tài)。 在處理實(shí)際問題中，一般是根據(jù)具體問在處理實(shí)際問題中，一

42、般是根據(jù)具體問題的特性，確定成本估計(jì)函數(shù)題的特性，確定成本估計(jì)函數(shù)e(X)= f(X)+g(X)中中的函數(shù)的函數(shù)f(X)和和g(X)。 在本例中，我們令在本例中，我們令f(x)是由根到結(jié)點(diǎn)是由根到結(jié)點(diǎn)X的的路徑的長度，路徑的長度，g(X)是以是以X為根的子樹中，由為根的子樹中，由X到到目標(biāo)狀態(tài)目標(biāo)狀態(tài)(自然排列自然排列)的一條最短路徑長度的估計(jì)的一條最短路徑長度的估計(jì)值。為此，值。為此，g(X)至少應(yīng)是把狀態(tài)至少應(yīng)是把狀態(tài)X轉(zhuǎn)換成目標(biāo)狀轉(zhuǎn)換成目標(biāo)狀態(tài)所需的最小移動(dòng)數(shù)。對它的一種可能的選擇態(tài)所需的最小移動(dòng)數(shù)。對它的一種可能的選擇是是 g(X)= 排列排列X的不在自然位置的牌的數(shù)目的不在自然位置的

43、牌的數(shù)目 關(guān)于關(guān)于15迷問題還有很多有效的算法，其中迷問題還有很多有效的算法，其中采用了一些啟發(fā)式的搜索策略進(jìn)行剪枝，比如采用了一些啟發(fā)式的搜索策略進(jìn)行剪枝，比如A*，B*算法等。算法等。博弈搜索博弈搜索n富有智能行為的競爭活動(dòng)，如下棋、打牌、戰(zhàn)富有智能行為的競爭活動(dòng)，如下棋、打牌、戰(zhàn)爭爭.n雙人完備信息博弈雙人完備信息博弈 兩位選手對壘，輪流走步，一方知道另一方已兩位選手對壘，輪流走步，一方知道另一方已經(jīng)走過的棋步，并能夠估計(jì)對方未來的走步。經(jīng)走過的棋步，并能夠估計(jì)對方未來的走步。對弈的結(jié)果是一方贏，另一方輸；或者雙方和對弈的結(jié)果是一方贏，另一方輸；或者雙方和局。實(shí)例有象棋、圍棋等。局。實(shí)例

44、有象棋、圍棋等。n機(jī)遇性博弈機(jī)遇性博弈 存在不可預(yù)測性的博弈，例如擲幣等。存在不可預(yù)測性的博弈，例如擲幣等。雙人完備信息博弈雙人完備信息博弈n在雙人完備信息博弈過程中，假設(shè)博弈的一方在雙人完備信息博弈過程中，假設(shè)博弈的一方為為MAX，另一方為另一方為MIN。可用博弈樹表示雙可用博弈樹表示雙方博弈過程。在博弈樹中，那些下一步該方博弈過程。在博弈樹中，那些下一步該MAX走步的節(jié)點(diǎn)稱為走步的節(jié)點(diǎn)稱為MAX節(jié)點(diǎn)節(jié)點(diǎn)，而下一步該，而下一步該MIN走步的節(jié)點(diǎn)稱為走步的節(jié)點(diǎn)稱為MIN節(jié)點(diǎn)節(jié)點(diǎn)。博弈樹例：分錢幣游戲博弈樹例：分錢幣游戲n 假設(shè)有假設(shè)有7枚硬幣，選手只能將已分好的一堆錢枚硬幣，選手只能將已分好的

45、一堆錢幣分成兩堆個(gè)數(shù)不等的硬幣。兩位選手輪流進(jìn)幣分成兩堆個(gè)數(shù)不等的硬幣。兩位選手輪流進(jìn)行，直到每一堆都只有一個(gè)或兩個(gè)硬幣，不能行，直到每一堆都只有一個(gè)或兩個(gè)硬幣，不能再分為止。哪位選手遇到不能再分的情況，則再分為止。哪位選手遇到不能再分的情況，則認(rèn)輸。認(rèn)輸。博弈狀態(tài)博弈狀態(tài)：( (K1,K2,.,KnK1,K2,.,Kn, , MIN or MAXMIN or MAX) )當(dāng)前各個(gè)錢堆中的錢幣數(shù)當(dāng)前各個(gè)錢堆中的錢幣數(shù)當(dāng)前走步方當(dāng)前走步方(7, MIN)(6,1, MAX)(5,2, MAX)(4,3, MAX)(5,1,1, MIN)(4,2,1, MIN)(3,2,2, MIN)(3,3,1, MIN)(4,1,1,1, MAX)(3,2,1,1, MAX)(2,2,2,1, MAX)(3,1,1,1,1, MIN)(2,2,1,1,1, MIN)(2,1,1,1,1,1, MAX)分錢幣博弈樹分錢幣博弈樹MAX必勝的策略？必勝的策略？極大極小搜索極大極小搜索n用當(dāng)前正在考察的節(jié)點(diǎn)生成一棵用當(dāng)前正在考察的節(jié)點(diǎn)生成一棵部分博弈樹部分博弈樹，利用利用估價(jià)函數(shù)估價(jià)函數(shù)f(n)對葉節(jié)點(diǎn)進(jìn)行靜態(tài)評估，對對葉節(jié)點(diǎn)進(jìn)行靜態(tài)評估，對MAX有利的節(jié)點(diǎn)其估價(jià)函數(shù)取正值，如為有利的節(jié)點(diǎn)其估價(jià)函數(shù)取正值，如為MAX獲勝節(jié)點(diǎn)，則取正無窮大；對獲勝節(jié)點(diǎn)，則取正無窮