分枝定界算法

1、分枝定界回溯算法：在問題的整個狀態(tài)空間圖上搜索一個解或全部解，并不斷地使用約束函數(shù)（或約束條件）來控制搜索進(jìn)程，一旦發(fā)現(xiàn)以某個節(jié)點(diǎn)為根的子樹上不可能產(chǎn)生問題的解，就終止對這一子圖的搜索，從而避免了許多不必要的工作，提高了效率。分枝限界法：使用比回溯更為有效的約束函數(shù)來控制這種搜索進(jìn)程，使 之能更好的朝著狀態(tài)空間上有最佳解（即有最大目標(biāo)函數(shù)或極小目標(biāo)函數(shù)）的分支推進(jìn)，以盡快地找出一個最佳解。例：求四皇后問題的所有合法布局。* * * * * * * * * * * * * * * * * * * * * * * * *例例 旅行問題。旅行問題。設(shè)五個城市之間的旅費(fèi)由下表給出：設(shè)五個城市之間的旅費(fèi)

2、由下表給出： 123451max24341415219max2096379max684231022max752081120max即第I行第j列的數(shù)表示從Ci到Cj的旅費(fèi)。城市之間無旅費(fèi)用max表示。要求找出從每個城市出發(fā)，游歷每個城市一次，最后返回出發(fā)地，找出旅費(fèi)最少的路徑。 123451max24341415-14219max2096-6379max68-64231022max7-752081120Max-8-1-0-3-0-0123451max101701-14212max1130-6302max02-6415312max0-75110012Max-8-1-0-3-0-014+6+6+7+

3、8+1+0+3+0+0=45綜合數(shù)據(jù)庫typenode=record a:array1.5,1.5 of byte; b:byte;空格的坐標(biāo) pnt,dep:word;父節(jié)點(diǎn)和深度 end;Var data:array1.2600 of node; temp:node;產(chǎn)生式規(guī)則: 5條，即向CR（R=1，2，3，4，5）城市移動生成結(jié)點(diǎn)的條件：第一、 所求下界小于當(dāng)前的上界（已求路徑的費(fèi)用）第二、 到CR城市可行（即費(fèi)用不為max）。搜索策略（BFS） 框圖：初始head=0Tail=1初始化INIT;初始結(jié)點(diǎn)入隊(duì);DD max 結(jié)點(diǎn)出隊(duì)out(temp1);產(chǎn)生新結(jié)點(diǎn)；并求D值For r

4、:=1 to 5 do把新結(jié)點(diǎn)與未擴(kuò)展結(jié)點(diǎn)按D值從小到大排序dep=5ynDD DUntil head=tail保存該方案當(dāng)前結(jié)點(diǎn)D值DDynDDD分枝限界法的算法框架一、初始化1、定義和說明 type node=record 結(jié)點(diǎn)定義 ； statei界變量； ； var 變量說明 open，tailopen表的首尾指針 list:array0.max of node；建表 best符合目標(biāo)函數(shù)要求的解答 min下界；分枝限界法的算法框架一、初始化2、Procedure init;Begin 按輸入格式輸入初始狀態(tài)； 根據(jù)要求設(shè)置下界 min 的初始值； 初始化初始結(jié)點(diǎn)的各項(xiàng)值； 初始結(jié)點(diǎn)入隊(duì)；End；分枝限界法的算法框架二、搜索2、Procedure seach；Var delimiter:integer界變量； temp:node子結(jié)點(diǎn)；Begin 下續(xù)End；Repeat 結(jié)點(diǎn)出隊(duì)； for I:=1