1、分支限界法,任課教師：何婧 Email: ,Chapter 8,Outline,分支限界法與回溯法的不同 分支限界法的基本思想 15迷問(wèn)題(15-puzzle) 旅行商問(wèn)題（貨郎擔(dān)問(wèn)題）,8.1 分支限界法與回溯法的不同,回溯法只能淘汰不能達(dá)到解的分支，而不能選擇最有利于達(dá)到解的分支。 而分支限界法一般要設(shè)計(jì)一種判定函數(shù)，精確的判定函數(shù)很難給出，所以通常是估值函數(shù)，對(duì)每個(gè)活結(jié)點(diǎn)，均可計(jì)算判定函數(shù)的值，比較這些值即可選擇擴(kuò)展結(jié)點(diǎn)，使之能更好地朝著狀態(tài)空間樹(shù)上有最佳解的分支推進(jìn)，以便盡快找出一個(gè)最佳解。,8.1 分支限界法與回溯法的不同,分支限界法在搜索過(guò)程中可以采用FIFO（先進(jìn)先出）或LIFO

2、（后進(jìn)先出），所以分支界限法的活結(jié)點(diǎn)表不一定是棧，而回溯法則采用了棧LIFO； 回溯法的擴(kuò)展結(jié)點(diǎn)每次生成一個(gè)孩子結(jié)點(diǎn)；分支限界法擴(kuò)展結(jié)點(diǎn)則是一次生成完所有的孩子（一旦生成了孩子結(jié)點(diǎn)，該結(jié)點(diǎn)就變?yōu)樗澜Y(jié)點(diǎn)，不再進(jìn)入活結(jié)點(diǎn)表，只有其孩子結(jié)點(diǎn)才能進(jìn)入活結(jié)點(diǎn)表）。,8.2 分支限界法的基本思想（1）,判定函數(shù)：可以根據(jù)從一個(gè)活節(jié)點(diǎn)出發(fā)，直到到達(dá)一個(gè)回答狀態(tài)所需的計(jì)算量來(lái)給定。 在找到回答節(jié)點(diǎn)以前，以活節(jié)點(diǎn)X為根的子樹(shù)上必須產(chǎn)生的節(jié)點(diǎn)總數(shù)做判定函數(shù)，“生成節(jié)點(diǎn)最少”問(wèn)題 從活節(jié)點(diǎn)X到最近一個(gè)回答節(jié)點(diǎn)的路徑的長(zhǎng)度 估值函數(shù)：判定函數(shù)的估計(jì)值。,分支限界法的基本思想（2）,在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次

3、機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)?；罱Y(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。 此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過(guò)程。此過(guò)程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。,8.3 15迷問(wèn)題（1）,問(wèn)題描述：所謂15迷(15-puzzle)問(wèn)題是在一個(gè) 4X4的方格棋盤(pán)上,將數(shù)字1，2，3，14，15以任意順序置入棋盤(pán)的各個(gè)方格中，空出一格。問(wèn)題是希望通過(guò)有限次的移動(dòng)，把一個(gè)給定的初態(tài)（下頁(yè)圖a）變成目標(biāo)狀態(tài)（下頁(yè)圖b） 。移動(dòng)規(guī)則是：每次只能在空格相臨的數(shù)字中任選一個(gè)移入空格。,

4、15迷問(wèn)題（2）,定義l(i)是棋盤(pán)上第i+1格到第16格中，比第i格中的棋子號(hào)碼小 的棋子個(gè)數(shù)。 例如： 圖a中 l(1)0; l(6)10; l(11)3 圖b中，一切l(wèi)(i)0,對(duì)于任何一個(gè)給定的初態(tài)，通過(guò)各種可能的移動(dòng)，最多可產(chǎn)生16！種不同的狀態(tài),哪些初態(tài)可以變換成目標(biāo)狀態(tài)？,15迷問(wèn)題（3）,定理8.1 對(duì)一個(gè)給定的初態(tài)，如果空格位于（j，k），如果 是偶數(shù)，則這個(gè)初態(tài)可以變換成目標(biāo)狀態(tài)，否則，其它任何初態(tài)都不可能變換成目標(biāo)狀態(tài)。其中L(i)是棋盤(pán)上第i+1格到第16格中，較i格中的棋子號(hào)碼小的棋子個(gè)數(shù)。 在初始狀態(tài)下，如果空格在上頁(yè)圖c的陰影位置中的某一格處，則令x=1；否則令x

5、0，定理簡(jiǎn)化為判斷 是否為偶數(shù)。,15迷問(wèn)題（4）,給出一個(gè)便于計(jì)算成本估計(jì)值的函數(shù)c(x)，使搜索沿著達(dá)到目標(biāo)節(jié)點(diǎn)的道路前進(jìn)。 方法一：c(x)當(dāng)前狀態(tài)下，沒(méi)有達(dá)到目標(biāo)狀態(tài)下正確位置的數(shù)字個(gè)數(shù)。 方法二：c(x)=,15迷問(wèn)題（5）,初態(tài)：x=1; 判定函數(shù)：c(x)=4,上,右,下,左,判定函數(shù)c(x)=5,c(x)=5,c(x)=3,c(x)=5,15迷問(wèn)題（5）,初態(tài)：x=1; 判定函數(shù)：c(x)=4,上,右,下,左,c(x)=2,c(x)=4,c(x)=4,15迷問(wèn)題（5）,8.4 旅行商問(wèn)題,問(wèn)題描述：旅行商問(wèn)題（Traveling Salesman problem）起源于經(jīng)濟(jì)發(fā)達(dá)

6、的歐美。某推銷(xiāo)員要到若干城市推銷(xiāo)商品，已知各城市之間的路程，他要選擇一條從駐地出發(fā)，經(jīng)過(guò)每個(gè)城市一遍，然后回到駐地的路線，使總的路程最小。 形式化描述：設(shè)G=(V,E)是一個(gè)有向圖，圖中各條邊的耗費(fèi)Ci,j0,當(dāng)(i,j)不屬于E時(shí)，定義ci,j=,在G中找一條有最小耗費(fèi)的周游路線（每個(gè)頂點(diǎn)經(jīng)過(guò)一次）。,基本數(shù)據(jù)結(jié)構(gòu)圖,圖的定義：G=(V,E)，其中，V表示結(jié)點(diǎn)集，是一個(gè)有窮非空集合；E表示圖的邊，用結(jié)點(diǎn)對(duì)表示(v,w) 有向圖： (v,w) (w,v) 無(wú)向圖： (v,w) = (w,v) 出度、入度和度 相鄰：無(wú)向圖中如果(v,w) E，則v,w相鄰 通道：v0,e1,v1vn-1envn

7、 v0,v1vn-1vn稱(chēng)為v0-vn通道 如果v0= vn，閉通道；否則稱(chēng)為開(kāi)通道 如果一條通道中所有的邊都不相同稱(chēng)為“跡”；所有的結(jié)點(diǎn)不同，稱(chēng)為“道路”； n=3 的一條閉通道稱(chēng)為“圈”,基本數(shù)據(jù)結(jié)構(gòu)圖,如果一條通道中，所有的結(jié)點(diǎn)之間都至少有一條道路，則稱(chēng)為“連通圖”； 如果一個(gè)圖中存在一條通過(guò)每條邊正好一次的閉跡，稱(chēng)為“歐拉圖”； 一個(gè)圖中如果存在經(jīng)過(guò)每個(gè)結(jié)點(diǎn)一次的圈，則稱(chēng)為“哈密頓圖”,都是無(wú)向連通圖,是歐拉圖，也是哈密頓圖,哈密頓圖,歐拉圖,基本數(shù)據(jù)結(jié)構(gòu)圖,圖的表示方法鄰接矩陣 G=(V,E)的鄰接矩陣是一個(gè)VV矩陣。,缺點(diǎn)是需要O(V2)的時(shí)間和空間,基本數(shù)據(jù)結(jié)構(gòu)圖,圖的表示方法鄰

8、接表 G=(V,E)的鄰接矩陣是一個(gè)VV矩陣。,鄰接表的存儲(chǔ)空間正比于V+E，比鄰接矩陣好,8.4 旅行商問(wèn)題,旅行商問(wèn)題的一個(gè)實(shí)例：,5,1,4,2,3,每個(gè)完整的巡回旅行恰好包含每一行每一列的一條邊和該邊表示的耗費(fèi)。,歸約,使每行每列至少有一個(gè)值為0,總和為63，所以任何一次 巡回旅行的最小耗費(fèi)至少 是63,8.4 旅行商問(wèn)題,在nn耗費(fèi)矩陣中，令(r1,r2rn)和(c1,c2cn)分別表示各行各列減掉的量，則巡回旅行的最小耗費(fèi)y滿足： 任何完整的巡回旅行，按x1,x2,xn的順序訪問(wèn)各城市，則它的耗費(fèi)必須至少是y,8.4 旅行商問(wèn)題,y=63,(3,5),-(3,5),y=63,y=86,選擇(3,5)可以使右子樹(shù)的下界增加最多,選擇邊： (3,5),8.4 旅行商問(wèn)題,y=63,(1,3),-(1,3),y=67,y=73,(3,5),選擇邊： (3,5) (1,3),8.4 旅行商問(wèn)題,(4,2),y=67,-(4,2),y=67,y=73,(1,3),選擇邊： (3,5) (1,3) (4,2),8.4 旅行商問(wèn)題,(2,1),y=67,-(2,1),y=67,(1,3),solution,(5,4),y=67,y=6