[10]分支限界法策略

1、1分支限界法分支限界法2内内 容容1.宽度优先搜索2.代价树搜索3.启发函数与估价函数4.应用例子背包问题任务调度问题TSP问题3引言引言分枝限界法的基本思想代价树搜索 + 剪枝策略分枝限界法求解的问题类型以优化问题为主4分支限界算法的基本要素解空间的树形表示0/1背包问题：子集树旅行商问题：排列树n皇后问题：满n叉树剪枝操作约束剪枝，优化目标函数剪枝节点评估函数定义及计算（即定义结点的优先级别）决定挑下一个处理节点的优先级5设计分枝限界法的基本步骤1. 将解空间表示成一棵树T（解空间树）求解问题转化为在树T中搜索解对应的树结点2. 定义剪枝操作考虑约束条件和目标值优化两方面3. 定义每个节点

2、成本函数4.搜索算法宽度优先搜索代价树搜索最佳优先搜索（best-first search）61.宽度优先搜索宽度优先搜索宽度优先搜索结果ABCDEFGHIJK 算法框架？7算法: 宽度优先搜索 function width_first( x0 ) open= x0 /根节点放在open表中 while( openNULL) x=GetFromHead(open) VisitFun(x) /处理节点x CA=Expand(x) /扩展节点x，CA是节点x的子节点集合 if(CA=NULL) /CA为空，表示节点x不可扩展 countinue end if InsertToTail(open,C

3、A) end whileend function82.代价树（图）搜索代价树（图）搜索代价树概念代价数：在一棵树中，父节点到子节点之间有一个数值，这个数值，对不同的问题，表示不同的涵义。9代价的表示：用g(x)表示从根节点到任意节点“x”的代价C(x1,x2)表示从节点x1到x2的代价（边代价）则 x2的总代价为： g(x2)=g(x1)+C(x1,x2)例如对右图： g(1)=0 g(2)=g(1)+c(1,2)=5 g(3)=g(2)+c(2,3)=5+3=8 g(6)=g(2)+c(2,6)=5+4=9723210function cost_width_first( x0 ) open=

4、 x0 while( openNULL) x=SelecFromHead（open）/从open头部选择一个节点x，并从open表中删除该节点 closed=closed x /将节点x插入集合closed中 CA=expand(x) /扩展节点x，CA是节点x的子节点集合 if(CA=NULL) /A为空，表示节点x不可扩展 countinue end if foreach (n in CA) n.parent=x; / 或者 n.prev=x ,配置集合A中每个节点的指针 end for CA= CA-closed /从A中删除在closed表中已经出现过的节点 CA=calculateC

5、ost(CA) /计算A中每个节点的代价函数值 CI= CA open for(n in CI) s=find(open,n) if(s.costn.cost) s.cost=n.cost end for CA=CA-CI open=Insert(open,CA) /将子集合A插入open表中 open=sort(open) /对open表中每个节点按代价值进行升序排序 end whileend function113.启发式搜索启发式搜索启发式搜索：利用问题本身的特征信息，指导搜索朝着最有希望的进行搜索过程的关键：如何确定下一个要考察的节点！确定节点方法不同：形成不同的搜索策略在确定节点时充

6、分利用与问题有关的特性信息估计出节点的重要性；在搜索时选择重要性高有节点；这样有利于求得最优解。 12启发性信息 指与具体问题求解过程有关的，并可指导搜索过程朝着最有希望方向前进的控制信息。一般有三种：用于决定要扩展的下一节点，避免盲目扩展，去扩展最有希望的节点；在扩展一个节点的过程中，用于决定要生成哪一个或那几个后继节点，以免盲目同时生成所有可能的节点。常常用来决定应采用哪一个操作施加于给定的节点；用于决定某些应该从搜索树中抛弃或修剪得节点。剪枝技术。 13估价函数 估价函数的任务就是估计状态空间树中各节点的重要程度。 估价函数f（x）的定义为初始节点经过节点到达目标节点的所有路径中最小路径

7、代价的估计值。一般形式为：f(x)=g(x)+h(x) g(x) : 代价函数,是从初始节点S0到当前节点x的实际代价，h(x): 启发函数,是从当前节点x到目标节点sg的估计代价；这里的估价函数实际上也就是界限函数。这里的估价函数实际上也就是界限函数 14分支界限法主要用于求最优解，求最优解可分成两种情况：求最小解（对应代价树），求最大解（对应利益树）。对于最小化问题，其估价函数我们称为下界函数，对于最大化问题，其估价函数我们称为上界函数。后面我们以求最小值为主要讨论内容。 对于求最小值问题，假定问题的解有n个分量，解可以分逐步构造。 那么估价函数之间应该有下面的关系。)k1 ( ,1211

8、21nxxxxfxxxfkkk也就是说，第k-1层节点的估价函数值不可能大于第k层节点估价函数值。 15例例1：任务分配问题：任务分配问题把n项工作分配给n个人，每个人完成不同的工作有不同的代价，如下图所示的代介矩阵，要求每个分配一项任务，使得总的代价最小。16下面我们研究估价函数(界限函数)的定义如图所示定义状态空间树，每个节点表示给一个人的任务分配g(xk):(从根节点到当前节点k的代价之和，实际表示的是从第1个人到当前第k个所分配任务的总代价)。h(xk):（从第k到第n个人从剩余n-k项任务中每人按最小代价分配时的代价之和）例如：初始情况k=0,即还没有给任何人分配任务 g(0)=0;

9、 h(0)=2+3+1+4=10则：lb(0)=g(0)+h(0)=10;Lb(x)=f(x)=g(x)+h(x)17假定已经给A和B两个人分配了任务，假定A分配的任务是2，B分配的任务是3（对应节点6），那么： g(6)=2+3=5;(A分配2的代价为2，B分配3的代价为3) h(6)=5+4=9；（C分配任务1代价最小，为5，D分配任务4，代价为4）所以，lb(6)=g(6)+h(6)=14lb(6)=g(6)+h(6)=14 1819例例2：背包问题：背包问题给定n个重量为wi,价值为vi的物品（i=1,2,3,.,n）,以及一个承重量为T的背包，找出能装入背包中的最有价值的物品集。考虑

10、下面一个问题实例：物品重量(wi)价值(vi)价值/重量(pi=vi/wi)144010274263525543124背包承重量T1020分析：这个问题是一个求最大值问题，其“代价”函数对应于利益，当然是越大越好。g(x)=(已选择装入背包物品的价值之和)h(x)=(背包的剩余承重量)*(剩余物品的最大单位位价值)路径上所选径上所选物x根节节点到当前节 w(x)()(T()(11iiwvxwxh求最大值时，评估函数是上界函数=f(x)=g(x)+h(x)2122例例3：TSP问题问题TSP问题是指旅行家要旅行问题是指旅行家要旅行n个城市，要求各个城个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。所走的路程最短。23分析：求极小值问题定义启发函数（下界函数）lb(x)=g(x)+h(x)g(x)-从起