算法分析与设计AlgoD&ALectureNotesW10章节

1、Last Section,回溯,回溯法的主要思想 有组织的穷尽搜索 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 分配（指派）问题 匈牙利法 一些说明,Upper Bound and Lower Bound,Upper bound,Lower bound,Objective function value,Inc,Dec,Existing solution,Minimization,Lower bound for pruning,Optimal Solution,Upper Bound and Lower Bound,Upp

2、er bound,Lower bound,Objective function value,Inc,Dec,Existing solution,Maximization,Upper bound for pruning,分支定界,主要的分支定界法相关概念: Feasible （solution）, Infeasible （solution）, Partial Solution, Optimal Solution, Branch, Bound (tight), Traverse, Backtracking, Prune, DFS, BFS, Frontier Search, Initial solution, Relax 分支定界法的主要思想 背包问题 TSP 有向图的TSP 分配（指派）问题 匈牙利法 一些说明,有向图的TSP,Matrix reduction 每一个完整的tour,包含且仅包含每一行上的一个值和每一列上的一个值 若某行（列）减去一个值w,则总的解值就减少w Matrix reduction：每行、列减去其最小值，使每行、列都至少有一个0，被减值的和就是一个界 图例,分配

3、（指派）问题,有n项任务要完成，恰好有n个人可以分别去完成其中每一项，但由于任务性质和个人专长不同，因此个人去完成不同的任务的效率（或所费时间）就有差别，由此提出下述问题：应当指派哪个人哪项任务使总的效率为最高（或花费的总时间为最小）？,分配（指派）问题,一个指派问题给出系数矩阵，或称效率矩阵，矩阵的元素cij(0) (i, j=1, 2, n)表示指派第i人去完成第j向任务的效率（或时间，成本等）。解题时，我们引入0-1变量xij，令 xij=1，当指派第i人去完成第j项任务时， =0,当不指派第i人去完成第j项任务时。,分配（指派）问题,极小化问题的数学模型是： xij = 0 或1 约束条件说明第j项任务只能由1个人来完成；约束条件说明第i人只能完成1项任务。合于约束条件的可行解也可写成表格或矩阵形式。,分配（指派）问题,任何解都不会小于每行中最小元素的和。 适用于部分解,匈牙利法,匈牙利法的根据是 指派问题最优解的性质：如果从系数矩阵（cij）的一行（列）各元素分别减去该行（列）的最小元素，得到新矩阵（bij） 。那么，以（bij）为系数矩阵的指派问题的最优解（xij）和原问题

4、的最优解相同。 这个性质成立的理由是，解（xij）的一行（列）元素中只有一个是1，如果从（cij）的第i行(列)元素各减一常数k，那么使目标函数z也减去k，而z和z-k的最优解（xij）当然是相同的。,匈牙利法,第一步：使系数矩阵出现0元素； 从系数矩阵的每行元素减去各该行的最小元素； 再从所得矩阵的各列减去各该列的最小元素。 如果某行某列已有0元素，则不处理。,匈牙利法,第二步：试求最优解。 经过第一步变换后，矩阵的每行每列都有了0元素，但我们希望能找出n个位于不同行不同列的0元素。如果能找到，我们就以这样的元素对应xij=1，令其余的xij=0，这样的解代入目标函数zb=0，它一定是极小，这就得到了（bij）问题的最优解（xij），根据上述性质，它也是原问题的最优解。 由有0元素最少的行开始，圈出一个0元素，用表示，然后划去同行同列的其它0元素，用表示。这样依次做完各行，已划去的不能再圈。如果这样能得到n个， 就完成了求解最优的过程。 否则：,匈牙利法,第三步：作能覆盖所有0元素的最少数目的直线集合： 对没有的行打号； 对打行上的所有0元素的列打号； 再对打号的列上有的行打号； 重

5、复（2）（3）直到得不出新的打号的行列为止； 对没有打号的行画横线，所有打号的列画纵线，这就是能覆盖所有0元素的最少数直线集合。,匈牙利法,第四步：变换矩阵使0元素移动，以达到每行都有元素的目的。 为此，在没被直线复盖的部分中找出最小元素： 对没画直线的行的各元素都减去这最小元素； 对画直线的列的各元素都加这最小元素，使行（未画直线）与列（画线）交叉处的0不变，这样得到新系数矩阵（它的最优解当然和原问题的相同）。 如已有n个不同行不同列的0元素，则求解过程已完成； 如还没得到n个，则回到第三步重复进行。,匈牙利法,例,匈牙利法,上述匈牙利法为解最小化问题的方法。 对于最大化问题： 可作一新矩阵 B = (bij) 使 bij = M - cij 其中M是足够大的常数（例如，取cij中最大的元素即可），这时bij0合于匈牙利法的条件。 所得的极小解（xij）就是原问题的极大解 。,匈牙利法,所以当 取得极小时，必使 取得极大。,一些说明,分支界限法类似于回溯法， 也是一种在问题的解空间树T上搜索问题解的算法。 但在一般情况下，分支界限法与回溯法的求解目标不同。回溯法的求解目标是找出T中满

6、足约束条件的所有解，而分支界限法的求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解。,一些说明,由于求解目标不同，导致分支界限法与回溯法在解空间树T上的搜索方式也不相同。 回溯法以深度优先的方式搜索解空间树T，而分支界限法则以广度优先或以最小耗费优先的方式搜索解空间树T。 分支界限法的搜索策略是，在扩展结点处，先生成其所有儿子的结点(分枝)， 然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（界限）， 并根据这些已计算出的函数值， 从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分枝推进，以便尽快地找出一个最优解。,一些说明,从活结点表中选择下一扩展结点的不同方式导致不同的分支界限法。最常见的有以下两种方式： 队列式（FIFO）分支界限法 队列式分支界限法将活结点表组成一个队列，并按队列的先进先出原则选取下一个结点为当前扩展结点。 2. 优先队列式分支界限法 优先队列式的分支界限法将活结点表组织成一个优先队列，并按优先队列中规定的结点

7、优先级选取优先级最高的下一个结点成为当前扩展结点。,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 a

8、nd 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

9、的最小生成树，同时满足所有的流量要求，而且每条边(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 an arc or not.,A Binary Search Tree,Define an m-stage binary search tree for problem with n nodes, where, for complete graph problem, m equals the number of pairs of nodes. Give each of the arcs an arc number, from 1 to m, as identification. The bran

《算法分析与设计AlgoD&ALectureNotesW10章节》由会员E****分享，可在线阅读，更多相关《算法分析与设计AlgoD&ALectureNotesW10章节》请在金锄头文库上搜索。