分枝定界算法

1、分枝定界回溯算法：在问题的整个状态空间图上搜索一个解或全部解，并不断地使用约束函数（或约束条件）来控制搜索进程，一旦发现以某个节点为根的子树上不可能产生问题的解，就终止对这一子图的搜索，从而避免了许多不必要的工作，提高了效率。分枝限界法：使用比回溯更为有效的约束函数来控制这种搜索进程，使 之能更好的朝着状态空间上有最佳解（即有最大目标函数或极小目标函数）的分支推进，以尽快地找出一个最佳解。例：求四皇后问题的所有合法布局。* * * * * * * * * * * * * * * * * * * * * * * * *例例 旅行问题。旅行问题。设五个城市之间的旅费由下表给出：设五个城市之间的旅费

2、由下表给出： 123451max24341415219max2096379max684231022max752081120max即第I行第j列的数表示从Ci到Cj的旅费。城市之间无旅费用max表示。要求找出从每个城市出发，游历每个城市一次，最后返回出发地，找出旅费最少的路径。 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综合数据库typenode=record a:array1.5,1.5 of byte; b:byte;空格的坐标 pnt,dep:word;父节点和深度 end;Var data:array1.2600 of node; temp:node;产生式规则: 5条，即向CR（R=1，2，3，4，5）城市移动生成结点的条件：第一、 所求下界小于当前的上界（已求路径的费用）第二、 到CR城市可行（即费用不为max）。搜索策略（BFS） 框图：初始head=0Tail=1初始化INIT;初始结点入队;DD max 结点出队out(temp1);产生新结点；并求D值For r

4、:=1 to 5 do把新结点与未扩展结点按D值从小到大排序dep=5ynDD DUntil head=tail保存该方案当前结点D值DDynDDD分枝限界法的算法框架一、初始化1、定义和说明 type node=record 结点定义 ； statei界变量； ； var 变量说明 open，tailopen表的首尾指针 list:array0.max of node；建表 best符合目标函数要求的解答 min下界；分枝限界法的算法框架一、初始化2、Procedure init;Begin 按输入格式输入初始状态； 根据要求设置下界 min 的初始值； 初始化初始结点的各项值； 初始结点入队；End；分枝限界法的算法框架二、搜索2、Procedure seach；Var delimiter:integer界变量； temp:node子结点；Begin 下续End；Repeat 结点出队； for I:=1