Algorithms Chapter 10 迭代改进.pptVIP

* * * * * * * 二分图的最大匹配 在二分图中，所有顶点都可以分为不相交的两个集合，每条边都连接两个集合中的各一个顶点。 二分图的最大匹配就是找到一个二分图G=V,U,E最多匹配边。 二分图的最大匹配 已有匹配(4-8,5-9) 增加1-6，匹配扩大为(4-8,5-9,1-6) 已有匹配(4-8,5-9,1-6) 增加2-6,1-7,删除1-6后,匹配扩大为 (4-8,5-9,1-7,2-6) 二分图的最大匹配 原有匹配(4-8,5-9,1-7,2-6) 增益路径3-8-4-9-5-10中，把原匹配的边去掉后 二分图的最大匹配 二分图最大匹配算法（见教材P279） 二分图最大匹配算法效率 迭代总数不超过[n/2]+1，其中n=|U|+|V| 每次迭代花的时间是O(m+n)，m=|E| 算法的时间效率属于O(n(m+n)) Hopcroft和Karp可以把效率提高到O(n1/2(m+n)) 稳定婚姻问题 一个婚姻匹配M是一个包含n个(m,w)对的集合，每一对成员都按照一对一的模式从两个不相交的n元素集合Y和X中选出。 匹配受阻对，稳定，稳定 Ann是Jim第三选择，Jim是Ann的第一选择 稳定婚姻问题 * 稳定婚姻问题 缺陷：性别取向（男士最优）。可以换成女士最优。 * 课程小结 迭代改进技术用来求最优问题的解，它生成一系列使问题目标函数值不断改进的可行解。 单纯形法是求解一般线性规划问题的经典方法。思路是：生成问题可行区域的一系列邻接极点，使得目标函数值不断改进。 最大流量问题要求找出一个网络中可能存在的最大流量，网络是包含一个源点和汇点的加权有向图。 * * * * * * * * * * * * * * * * * * * * * * Deng Xin Design and Analysis of Algorithms Deng Xin The Design and Analysis of Computer Algorithms Deng Xin Design and Analysis of Algorithms Deng Xin Design and Analysis of Algorithms Deng Xin Design and Analysis of Algorithms * 迭代改进 Iterative Improvement 迭代改进(Iterative Improvement) 教学内容 迭代改进基本思想 单纯形法(The simplex method) 最大流量问题(Maximum-flow ) 二分图的最大匹配 稳定婚姻问题 要求 掌握迭代改进的基本思想，了解单纯形法，理解最大流量问题及稳定婚姻问题。 * 迭代改进(Iterative Improvement) 另一种最优问题的解决方案。 从某些可行解开始，通过重复使用一些简单的步骤来不断改进它，最终使目标函数最优。 几个问题： 需要一个初始可行解； 可行解改变后是否最优； 如何改进是局部解或全局解最优。 * 单纯形法(the simplex method) 线性规划的几何解释 x+y≤4 x+3y ≤6 x≥0,y ≥0 求3x+5y的最大值 * 单纯形法(the simplex method) 线性规划的几何解释 x+y≤4 x+3y ≤6 x≥0,y ≥0 求3x+5y的最大值 ? School of Computer Science and Technology, SWUST * / 单纯形法(the simplex method) 可行区域无界 单纯形法(the simplex method) 极点定理 可行区域非空的任意线性规划问题有最优解，而且，最优解总是能够在其可行区域的一个极点上找到。 单纯形法 只需检测可行区域极点中的一小部分就能找到最优点。 先在可行区域中找一个极点， 然后检查是否能在邻接极点处取得更佳， 如果不是，当前极点就是最优值； 如果是，继续往下处理。 单纯形法(the simp