算法分析与设计AlgoDALectureNotesW10章节.pptVIP

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 and Lower Bound 分支定界 主要的分支定界法相关概念: 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，被减值的和就是一个界 图例 分配（指派）问题 有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）和原问题的最优解相同。 这个性质成立的理由是，解（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元素的列打∨号； 再对打∨号的列上有◎的行打∨号； 重复（2）（3）直到得不出新的打∨号的行列为止； 对没有打∨号的行画横线，所有打∨号的列画纵线，这就是能覆盖所有0元素的最少数直线集合。 匈牙利法 第四步：变换矩阵使0元素移动，以达到每行都有◎元素的目的。 为此，在没被直线复盖的部分中找出最小元素： 对没画直线的行的各元素都减去这最小元素； 对画直线的列的各