算法设计与分析_10.ppt

Last Section 贪心算法 主要思想(可行、局部最优、不可取消) 分数背包问题 最短路径问题 Dijkstra’s Algorithm Prim’s Kruskal’s Huffman 算法与决策树(最小加权路径长度) 回溯 回溯法的主要思想 有组织的穷尽有哪些信誉好的足球投注网站 3 着色问题 8皇后问题 哈密尔顿回路 一般回溯算法 分支定界 主要的分支定界法相关概念: Feasible （solution）, Infeasible （solution）, Partial Solution, Optimal Solution, Branch, Bound (tight), Traverse, Backtracking, Prune, DFS, BFS, Frontier Search, Initial solution, Relax 分支定界法的主要思想 分支定界法解整数规划问题 背包问题 TSP 有向图的TSP 分配（指派）问题 匈牙利法 一些说明 分支定界法的主要思想 最优化问题是根据某些约束寻求目标函数的最大或最小值。 可以利用回溯的思想。 且回溯的思想得到进一步的强化。 和回溯法相比，分支定界法需要两个额外的条件： ? 对于一棵状态空间树的每一个节点所代表的部分解，我们要提供一种方法，计算出通过这个部分解繁衍出的任何解在目标函数上的最佳值边界。 ? 目前求得的最佳解的值。 分支定界法的主要思想 若能得到1，2两信息，即可拿某个阶段的边界值和目前求得的最佳解值比较： 如果边界值不能超越（也就是说，在最小化问题中不小于，在最大化问题中不大于）目前的最佳解，这个节点就是一个没有希望的节点，需要立即关闭（剪枝），因为从这个节点生成的解，没有一个能比目前已经得到的解更好。 这就是分支界限技术的主要思想。 Upper Bound and Lower Bound Upper Bound and Lower Bound 分支定界法的主要思想 一般来说，对于一个分支定界算法的状态空间树来说，只要符合下面任一条件，我们就会中止它的在当前节点上的查找路径： 该节点的边界值不优于目前最佳解的值。 该节点无法代表任何可行解， 因为它已经违反了问题的约束。 该节点代表的可行解的子集只包含一个单独的点（因此无法给出更多的选择）。在这种情况下，我们拿这个可行解在目标函数上的值和目前求得的最佳解进行比较，如果新的解更好一些的话，就用前者替换后者。 TSP 如果能定义下界，即可使用分支定界算法。 通过把城市距离矩阵D 的最小元素乘以城市数量n， 我们可以得到一个非常简单的下届。 例，见图 稍紧一些的下届：最小的n个元素的和 好的下界 发现一个好的边界函数常常不是一件简单的任务。一方面，我们希望这个函数容易计算。但另一方面又不能过于简单(可能过松)。 任何旅行长度l的下届：对于每一个城市i， 1≤i≤n,求出从城市i到最近的两个城市的距离之和si；计算出这n个数字的和s，并把结果除以2；而且，如果所有的距离都是整数，还可将这个结果向上取整（更紧）： 更紧的下界 此外，如果一个给定图的任何旅程子集都必须包含某些特定的边，例如，如果在图中，要求图的所有哈密顿回路都必须包含边（a,d），我们可以分别把a,d 两个顶点附带的两条最短边，和要求附带的边（a,d）和（d,a）相加，以得到下面这个下界： 求解例题 背包问题 背包的承重量W 等于10 背包问题 背包的承重量W 等于10 一种计算上界的方法是把已选物品的总价值v，加上背包剩余重量与剩下物品的最佳单位回报的积： 有向图的TSP Matrix reduction 每一个完整的tour,包含且仅包含每一行上的一个值和每一列上的一个值 若某行（列）减去一个值w,则总的解值就减少w Matrix reduction：每行、列减去其最小值，使每行、列都至少有一个0，被减值的和就是一个界 图例 分配（指派）问题 有n项任务要完成，恰好有n个人可以分别去完成其中每一项，但由于任务性质和个人专长不同，每个人去完成不同的任务的效率（或所费时间）就有差别，由此提出下述问题：应当指派哪个人去完成哪项任务使总的效率为最高（或花费的总时间为最小）？ 分配（指派）问题 一个指派问题给出系数矩阵，或称效率矩阵，矩阵的元素cij(0) (i, j=1, 2,…, n)表示指派第i人去完成第j向任务的效率（或时间，成本等）。解题时，我们引入0-1变量xij，令 xij=1，当指派第i人去完成第j项任务时， =0,当不指派第i人去完成第j项任务时。 分配（指派）问题 极小化问题的数学模型是： ① ② ③