chapter 8 分支界限法-new.ppt

1、分支限界法,任课教师：何婧 Email: ,Chapter 8,Outline,分支限界法与回溯法的不同 分支限界法的基本思想 15迷问题(15-puzzle) 旅行商问题（货郎担问题）,8.1 分支限界法与回溯法的不同,回溯法只能淘汰不能达到解的分支，而不能选择最有利于达到解的分支。 而分支限界法一般要设计一种判定函数，精确的判定函数很难给出，所以通常是估值函数，对每个活结点，均可计算判定函数的值，比较这些值即可选择扩展结点，使之能更好地朝着状态空间树上有最佳解的分支推进，以便尽快找出一个最佳解。,8.1 分支限界法与回溯法的不同,分支限界法在搜索过程中可以采用FIFO（先进先出）或LIFO

2、（后进先出），所以分支界限法的活结点表不一定是栈，而回溯法则采用了栈LIFO； 回溯法的扩展结点每次生成一个孩子结点；分支限界法扩展结点则是一次生成完所有的孩子（一旦生成了孩子结点，该结点就变为死结点，不再进入活结点表，只有其孩子结点才能进入活结点表）。,8.2 分支限界法的基本思想（1）,判定函数：可以根据从一个活节点出发，直到到达一个回答状态所需的计算量来给定。 在找到回答节点以前，以活节点X为根的子树上必须产生的节点总数做判定函数，“生成节点最少”问题 从活节点X到最近一个回答节点的路径的长度 估值函数：判定函数的估计值。,分支限界法的基本思想（2）,在分支限界法中，每一个活结点只有一次

3、机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。此过程一直持续到找到所需的解或活结点表为空时为止。,8.3 15迷问题（1）,问题描述：所谓15迷(15-puzzle)问题是在一个 4X4的方格棋盘上,将数字1，2，3，14，15以任意顺序置入棋盘的各个方格中，空出一格。问题是希望通过有限次的移动，把一个给定的初态（下页图a）变成目标状态（下页图b） 。移动规则是：每次只能在空格相临的数字中任选一个移入空格。,

4、15迷问题（2）,定义l(i)是棋盘上第i+1格到第16格中，比第i格中的棋子号码小 的棋子个数。 例如： 图a中 l(1)0; l(6)10; l(11)3 图b中，一切l(i)0,对于任何一个给定的初态，通过各种可能的移动，最多可产生16！种不同的状态,哪些初态可以变换成目标状态？,15迷问题（3）,定理8.1 对一个给定的初态，如果空格位于（j，k），如果 是偶数，则这个初态可以变换成目标状态，否则，其它任何初态都不可能变换成目标状态。其中L(i)是棋盘上第i+1格到第16格中，较i格中的棋子号码小的棋子个数。 在初始状态下，如果空格在上页图c的阴影位置中的某一格处，则令x=1；否则令x

5、0，定理简化为判断 是否为偶数。,15迷问题（4）,给出一个便于计算成本估计值的函数c(x)，使搜索沿着达到目标节点的道路前进。 方法一：c(x)当前状态下，没有达到目标状态下正确位置的数字个数。 方法二：c(x)=,15迷问题（5）,初态：x=1; 判定函数：c(x)=4,上,右,下,左,判定函数c(x)=5,c(x)=5,c(x)=3,c(x)=5,15迷问题（5）,初态：x=1; 判定函数：c(x)=4,上,右,下,左,c(x)=2,c(x)=4,c(x)=4,15迷问题（5）,8.4 旅行商问题,问题描述：旅行商问题（Traveling Salesman problem）起源于经济发达

6、的欧美。某推销员要到若干城市推销商品，已知各城市之间的路程，他要选择一条从驻地出发，经过每个城市一遍，然后回到驻地的路线，使总的路程最小。 形式化描述：设G=(V,E)是一个有向图，图中各条边的耗费Ci,j0,当(i,j)不属于E时，定义ci,j=,在G中找一条有最小耗费的周游路线（每个顶点经过一次）。,基本数据结构图,图的定义：G=(V,E)，其中，V表示结点集，是一个有穷非空集合；E表示图的边，用结点对表示(v,w) 有向图： (v,w) (w,v) 无向图： (v,w) = (w,v) 出度、入度和度 相邻：无向图中如果(v,w) E，则v,w相邻 通道：v0,e1,v1vn-1envn

7、 v0,v1vn-1vn称为v0-vn通道 如果v0= vn，闭通道；否则称为开通道 如果一条通道中所有的边都不相同称为“迹”；所有的结点不同，称为“道路”； n=3 的一条闭通道称为“圈”,基本数据结构图,如果一条通道中，所有的结点之间都至少有一条道路，则称为“连通图”； 如果一个图中存在一条通过每条边正好一次的闭迹，称为“欧拉图”； 一个图中如果存在经过每个结点一次的圈，则称为“哈密顿图”,都是无向连通图,是欧拉图，也是哈密顿图,哈密顿图,欧拉图,基本数据结构图,图的表示方法邻接矩阵 G=(V,E)的邻接矩阵是一个VV矩阵。,缺点是需要O(V2)的时间和空间,基本数据结构图,图的表示方法邻

8、接表 G=(V,E)的邻接矩阵是一个VV矩阵。,邻接表的存储空间正比于V+E，比邻接矩阵好,8.4 旅行商问题,旅行商问题的一个实例：,5,1,4,2,3,每个完整的巡回旅行恰好包含每一行每一列的一条边和该边表示的耗费。,归约,使每行每列至少有一个值为0,总和为63，所以任何一次 巡回旅行的最小耗费至少 是63,8.4 旅行商问题,在nn耗费矩阵中，令(r1,r2rn)和(c1,c2cn)分别表示各行各列减掉的量，则巡回旅行的最小耗费y满足： 任何完整的巡回旅行，按x1,x2,xn的顺序访问各城市，则它的耗费必须至少是y,8.4 旅行商问题,y=63,(3,5),-(3,5),y=63,y=86,选择(3,5)可以使右子树的下界增加最多,选择边： (3,5),8.4 旅行商问题,y=63,(1,3),-(1,3),y=67,y=73,(3,5),选择边： (3,5) (1,3),8.4 旅行商问题,(4,2),y=67,-(4,2),y=67,y=73,(1,3),选择边： (3,5) (1,3) (4,2),8.4 旅行商问题,(2,1),y=67,-(2,1),y=67,(1,3),solution,(5,4),y=67,y=6