算法设计与分析_11.ppt

Last Section 分支定界 主要的分支定界法相关概念: Feasible （solution）, Infeasible （solution）, Partial Solution, Optimal Solution, Branch, Bound (tight), Traverse, Backtracking, Prune, DFS, BFS, Frontier Search, Initial solution, Relax 分支定界法的主要思想 分支定界法解整数规划问题 背包问题 TSP 有向图的TSP 分配（指派）问题 匈牙利法 一些说明 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 represented by its upper triangular node-node adjacency matrix B with elements bij. The problem is to find a G*∈G which minimizes the cost of transporting required origin-destination flows subject to specified arc and node capacity, node degree and chain hop limit constraints. 问题描述 设G表示在n个点上的所有无向图的集合，G是该集合中的一个元素。 G以节点的邻接矩阵B的上三角阵来表示，其元素为bij. 该问题就是要找到一个G *∈G，使得在满足给定的边容量限制的前提下，实现传输所有源节点到目的节点的流量需求所用的花费最小。 Next ? The Problem Formulation-1 Interpretation of the formulation Too complicated? Then what? Transform and conquer Problem transformation Constant arc costs Tree solution 给定一个连通的无向图G=(V,A,d,c)， 点集V={1,2,…,n}，边集A. V中的每个节点对i和j间，有一定的流量要求dij. cij表示建立A中的边(i,j)的花费。 每条边(i,j)上的负载不能超过一个给定值kij. 通过以上这些定义，该问题就是要找到一个可以扩展节点集V的最小生成树，同时满足所有的流量要求，而且每条边(i,j)都符合负载限制kij. 令fij表示经过边(i,j) 的总流量。定义 xij=1,当边(i,j)被选中在解中； xij=0,当边(i,j)没有被选中。 Problem II Formulation-2 Interpretation of the formulation Branch and Bound What is the first task? Branch and Bound What is the first task? Constructing a search tree How to construct the search tree? Branch and Bound What is the first task? Constructing a search tree How to construct the search tree? -- Innumerate ，Organize，Bound Branch and Bound The search tree a tree spanning n nodes must have exactly n-1 arcs consider the solution as a collection of n-1 arcs (for n-node problem) chosen from all candidate arcs introduce an arc-oriented branch and bound method, branching by using a