2015分支限界法问题.ppt

分支限界法旅行售货员问题（TSP） 小燕子 6.1 分支限界法的基本思想 1. 分支限界法与回溯法的不同 （1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 （2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 6.1 分支限界法的基本思想 2. 分支限界法基本思想 分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 6.1 分支限界法的基本思想 3. 常见的两种分支限界法 （1）队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 最大优先队列：使用最大堆，体现最大效益优先 最小优先队列：使用最小堆，体现最小费用优先 旅行售货员问题（TSP） 某售货员要到若干城市去推销商品，一直各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到住地的路线，使总的路程最短。 该问题是一个NP完全问题， 有(n-1)!条可选路线 。 路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。 TSP问题 问题陈述: 旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。 即： 设G(V,E)是一带权有向图,V={1,2,…n },其耗费矩阵C=(ci,j)，当(i,j)? E时, 记 ci,j= ?且ci,j=? .问如何选择周游路线使耗费最小？ 优先队列式分支限界法用极小堆存储活结点表 {}； B{E,D,C}； E{D, J,K, C}； D{H,J,K,I,C}； H{J,K,I,C}；J{K,I,C}；K{I,C}；I{C}；C{}. 面试题1 有一根27厘米长的细木杆，在第3厘米，7厘米，11厘米，17厘米，23厘米这五个位置上各有一只蚂蚁，木杆很细，不能同时通过两只蚂蚁，开始时，蚂蚁的头朝向左还是右是任意的，他们只会朝前走或掉头，但不会后退，当两只蚂蚁相遇后，蚂蚁会同时掉头朝反方向走，假设蚂蚁们每秒钟可以走1厘米的距离. 求所有蚂蚁都离开木杆的最小时间和最大时间。 问题分析： 1.最小时间肯定是各自朝最近的一端跑，27-11=14，1114，所以中间的蚂蚁会朝11cm那端跑，最适时短时间11。 2. 最长时间呢，肯定两端的蚂蚁都往中间跑，具体怎么跑好像有点儿想不清楚，那试算之，假设3cm处的和7cm处的相对而行，碰面后会怎样？如果你眼神不好， 你会发现你分不出来哪个是哪个，因为3cm的转头后就相当于7cm的一直在走。到这里，一切就已经没有刚开始那样想不清楚了，事情很清楚：蚂蚁碰头可以用 等量代换的思想，在这种情况下，任何蚂蚁都是自由地向它面向的一端直接爬过去。那最长时间就清楚了：27-3=24，27-23=4 2423，所以最长时间是24。 算法： 1.找出中间的蚂蚁离两端的距离中较小的。 a[2]=11 a[2]=27-11=14, 因为a[2]a[2]，所以最小距离是11，时间11/1=11 2.找出两端的蚂蚁距两端的距离中较大的。 a[0]=3 a[0]=27-3=24 a[4]=23 a[4]=27-23=4 这四个数中最大的是24 3.所以，最大时间24，最小时间11 程序： public class Ant { private static int LONG = 27; private int[] a = { 3, 7, 11, 17, 23 }; private int min = 0, max = 0; public void gogogo() { for (int