回溯分支限界.ppt

Last Section 回溯 回溯法的主要思想 有组织的穷尽搜索 3 着色问题 8皇后问题 哈密尔顿回路 一般回溯算法 一般回溯算法可以作为一种系统的搜索方法应用到一类搜索问题当中，这类问题的解由满足事先定义好的某个约束的向量（x1, x2, …, xi）组成。 如下的PARTITION问题中的一个变形。给定一个n个整数的集合X = {x1, x2, …, xn}和整数y，找出和等于y的X的子集Y。比如说，如果 X ={10,20,30,40,50,60} 和y=60 则有三种不同长度的解，它们分别是 {10，20，30}，{20，40} 和{60} 用另一种方法明确表达，使得解是一种明显的长度为n的布尔向量，以上三个解可用布尔向量表示为 {1，1，1，0，0，0}，{0，1，0，1，0，0} 和{0，0，0，0，0，1} 一般回溯算法 假定算法已经找到部分解为（x1, x2, …, xj）, 然后再考虑向量v=（x1, x2, …, xj ,xj+1）, 有下面的情况： （解向量中每个xi都属于一个有限的线序集Xi） 如果v表示问题的最后解，算法记录下它作为一个解，在仅希望获得一个解时终止，或者继续去找出其他解。 （向前步骤）。如果v表示一个部分解，算法通过选择集合Xj+2中的第一个元素向前。 如果v既不是最终的解，也不是部分解，则有两种子情况。 如果从集合Xj+1中还有其他的元素可选择，算法将xj+1置为Xj+1中的下一个元素。 (回溯步骤)。如果从集合Xj+1中没有更多的元素可选择，算法通过将xj置为Xj中的下一个元素回溯；如果从集合Xj中仍然没有其他的元素可以选择，算法通过将xj-1置为Xj-1中的下一个元素回溯，依次类推。 一般回溯算法 算法 BACKTRACKREC 输入：集合X1，X2，…, Xn 的清楚的或隐含的描述。 输出：解向量v=（x1, x2, …, xi）, i≤n。 v←Φ flag←false backrec(1) if flag then output v else output “no solution” procedure backrec (k) for 每个x∈Xk xk←x;将xk加入v if v 为最终解then set flag←true and exit else if v 是部分解then backrec (k+1) end for 一般回溯算法 算法BACKTRACKITER 输入：集合X1，X2，…, Xn 的清楚的或隐含的描述。 输出：解向量v=（x1, x2, …, xi）, i≤n。 v←Φ flag←false k←1 while k≥1 while Xk 没有被穷举 xk←Xk 中的下一个元素；将xk加入v if v 为最终解then set flag←true, 且从两个while循环退出 else if v 是部分解then k←k+1 {前进} end while 重置Xk， 使得排在第一位的元素为下一个元素 k←k-1 {回溯} end while if flag then output v else output “no solution” 分支定界 一般着色问题 整数规划 主要的分支定界法相关概念: Feasible （solution）, Infeasible （solution）, Partial Solution, Optimal Solution, Branch, Bound (tight), Traverse, Backtracking, Prune, DFS, BFS, Frontier Search, Initial solution, Relax 分支定界法的主要思想 背包问题 TSP 有向图的TSP 分配（指派）问题 匈牙利法 一些说明 Upper Bound vs. Lower Bound Upper Bound and Lower Bound Upper Bound and Lower Bound Branch and Bound Minimum Cost Network Flow Problem 问题描述 该类设计问题的目标是，在一组节点之间设计一最小耗费的网络以满足所有的流量需求。 描述该问题所需的信息： 每个源节点和目的节点对(O-D)之间的流量需求 在每条边(i,j)上负载流量的价值函数 Cij=f(tij) The Problem let G be the set of all undirected graphs on n nodes with G a member of this set. G is repre