成本函数Costfunction-天津大学计算机科学与技术学院.PPT

* * * * * When inserting a node into the queue, one needs to judge whether it is a feasible solution or not Extend to bound function? * * * * * * * * * * * * * * * * * * * 分枝-限界(Branch Bound) 宫秀军 天津大学计算机科学与技术学院 gongxj@tju.edu.cn 主要内容 引论 主要思想 求解步骤 应用 作业调度问题(Job Scheduling) 旅行商问题(TSP) 算法思路(1) 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树 在分支限界法中，每一个活结点只有一次机会成为扩展结点 活结点一旦成为扩展结点，就一次性产生其所有儿子结点。 在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止 活节点选取规则 FIFO LIFO Max Profit（MP） Least Cost (LC) 算法思路(2) 分支限界法与回溯法的不同 求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 迷宫问题：问题描述 问题描述：内有障碍物的长方形格子，含有一个入口和一个出口，找到一个从入口到出口，能绕过所有障碍物的路径 矩阵表示 0 0 0 0 1 1 0 0 0 迷宫问题：FIFO Search 1,1 1,2 1,3 2,1 2,2 2,3 3,1 3,2 3,3 扩展节点 活节点队列 解空间按宽度优先搜索 活结点列表存储于队列中 (1,1) (1,2) (2,1) (3,1) (3,3) (1,3) (3,2) 0/1Knapsack FIFO Search Nodes are expended in a breadth-first manner Live nodes are stored in a queue Max-profit search Nodes are expended in a max-profit manner Live nodes are stored in a max heap 0/1Knapsack:status of SP n=3，c= 30 w= [ 20 , 15 , 15 ] p= [ 40 , 25 , 25 ] TSP FIFO search Least-cost search（min-heap） 应用问题 作业调度问题(Job Scheduling) 旅行商问题(TSP) Least Cost Search (Bounding function) 成本函数(Cost function) 设Cost(x)为可行解的成本，(最小)优化问题要求找有最小成本的可行解 定义状态空间树上任一结点x的成本函数 c(x)如下: 如x为可行叶结点则 c(x)=cost(x); 如x为非叶结点 c(x)=状态空间树上以x为根的子树中可行解成本的最小值 如其子树中无可行解则c(x)=∞ LC-检索过程 每次从活节点表中取出最小成本节点作为E-节点并展开其全部子节点 但在展开前不知道c(x)的值 以c(x)的下界估值?(x)做LC-检索-启发式 要求?(x)满足: ?(x)=Cost(x),当x为可行叶节点时 LC-限界 令U为当前最优成本值 对当前的选取的扩展节点E，当?(E)≥U时算法结束。因为，这时活节点表中其它节点的下界估计也≥U， 展开这些活节点不能产生更好的解 对正在展开的子节点x， 如?(x)≥U，则停止产生子节点x， 即不将其放入活节点表 这种限界方法也可用于FIFO活结点表上，称为FIFO分枝-限界。U初始为∞ ，其后用新得到的可行解值加以修改 带截止期的作业调度问题（1） n个作业，1台处理机，每个作业i对应一个三元组(pi,di,ti) pi－罚款额 di－截止期 ti －需要的处理机时间 求可行的作业子集J，使得罚款额Σpj最小,其中j为不在J中的作业 定长元组表示可行作业子集:(x(1),┅,x(n)) 设X=(x(1),…x(k))为状态空间树的节点 下界?(x)可估计为已确知的罚款额: Σ(1-x(j))pj ,求和范围为1≤j≤k 带截止期的作业