1分支限定法.ppt

1分支限界法分支限界法 2 ?学****要点?理解分支限界法的剪枝搜索策略。?应用范例: 旅行售货员问题?见材料, P225 3分支限界法的基本思想分支限界法与回溯法(1)求解目标: 回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。(2)搜索方式的不同: 回溯法以深度优先的方式搜索解空间树, 而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 4分支限界法的基本思想分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。 5旅行售货员(旅行商)问题 1. 问题描述某售货员要到若干城市去推销商品,已知各城市之间的路程(或旅费)。他要选定一条从驻地出发,经过每个城市一次,最后回到驻地的路线,使总的路程(或总旅费)最小。路线是一个带权图。图中各边的费用(权)为正数。图的一条周游路线是包括 V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。旅行售货员问题的解空间可以组织成一棵树,从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。 6旅行售货员问题: ?是本世纪人类要解决的 25 个问题之一(详细信息见) ,量子计算机,