《5.1 几个重要算法的计算复杂度讨论》由会员分享，可在线阅读，更多相关《5.1 几个重要算法的计算复杂度讨论（5页珍藏版）》请在金锄头文库上搜索。
1、 1第五章第五章 组合优化问题的有效算法组合优化问题的有效算法 5.1 几个重要算法的计算复杂度讨论几个重要算法的计算复杂度讨论 一、线性规划问题的单纯形算法不是多项式时间算法一、线性规划问题的单纯形算法不是多项式时间算法 Klee 和 Minty 1972 给出了第一这样的例子。 首先要有一个有界多面体，它有指数个顶点。例如，一个立方体： 3 , 2 , 1, 10=jxj 有238个顶点。 d维立方体： djxj, 2 , 1, 10L= 有d2个顶点。 每一个顶点对应于,21dxxxL的一个子集， 使得该子集中的元素等于1，其余为0。 1x 2x 3x1 , 1 , 01 , 1 , 1
2、1 , 0 , 00 , 0 , 1 0 , 1 , 1 0 , 1 , 00 , 0 , 01 , 0 , 1 2对于210d，存在线性规划问题，它有d2个约束方程，d3个变量，并且它的系数的绝对值为不超过4的整数。 当用单纯形算法解这个线性规划问题时，其迭代步数可以为12 d步。 对单纯形算法的进一步讨论： 1单纯形算法的变形可以改变选入或退出规则（转轴规则）以避免经过每一个顶点。但是，对于不同的变形的算法，可以找到不同的反例。这使得我们相信单纯形算法及其变形都不是多项式算法。 2这种怀的例子在真实问题中很少发生。过去几十年的观察表明，对于中等规模的实际问题，单纯形算法需要m4至m6的迭代
3、步数来完成两阶段的计算。据推测，当n相对于m来说较大时，迭代次数预计为m，其中 +mne2log2类似的结果已经用人工产生的概率分布的蒙特卡洛实验给予了证实。因此，单纯形算法可以期望的计算量为 O(nm2)。 二、组合优化问题原始对偶算法的计算复杂度二、组合优化问题原始对偶算法的计算复杂度 1. 最短路问题的原始对偶算法Dijkstra标号算法实现 多项式算法，计算复杂度为)(2nO。 2. 最短路问题的Floyd-Washall算法 不是原始对偶算法，是多项式算法，计算复杂度为)(3nO。 3. 最大流问题的原始对偶算法Ford-Fulkerson标号算法实现 4流网络),(bAVtsN=的
4、Ford-Fulkerson标号算法可能永远不停止。设所有弧的容量为整数，那么必有限步终止： (1) 每次迭代所需要的计算复杂度为|)(| AO：需要对节点进行检查和标号，),(bAVtsN=的每一条弧),(vu最多检查两次，一次检查v，另一次检查u，因此一次标号所需要的算术运算步数为|)(| AO；另一方面， 标号返回需)(pO步完成， 其中p是发现增广路的长度 （弧的条数） 。由于增广路上的节点不会重复出现，所以|Vp，所以每次迭代所需要的计算量为|)(|)|(|AOAVO=+。 (2) 算法的迭代步数)(SO，其中S为流的增广次数：由于所有弧的容量为整数以及算法每次迭代所得到的流也是整数
5、，所以每次迭代流的值至少增加1。所以，若最大流的值为v，则vS。不能用问题的解值去估计算法的计算复杂度，而必须用例子的输入来表示。因此，我们用 Ayxyxb),(),(来代替v，这是因为 Ayxyxbv),(),(。 (3) 整个算法的计算复杂度为 |),(),(AyxbOAyx。 因此因此 Ford-Fulkerson 标号算法不是多项式算法，是拟（伪）多项式算法。标号算法不是多项式算法，是拟（伪）多项式算法。因为算法的迭代步数S可能会达到最大流的值v，而最大流的值v可以是例子输入的指数倍。 例如： s uvt1000 1000 1000 1000 1 5最大流值为2000。从0流开始，应用
6、标号算法： 第1次迭代，得到增广路),(tvus，流增加1，流值变为1； 第2次迭代，得到增广路),(tuvs，流增加1，流值变为2； 第3次迭代，得到增广路),(tvus，流增加1，流值变为3； 第4次迭代，得到增广路),(tuvs，流增加1，流值变为4； 第2000次迭代，得到增广路),(tuvs，流增加1，流值变为2000； 算法经过2000次迭代后终止。若将1000改为M，则Ford-Fulkerson标号算法的迭代步数为M2。所以，在最坏情况下，Ford-Fulkerson标号算法所需要的迭代步数是指数的。 4. 考虑Hitchcock问题的算法的计算复杂度。 三、其它一些常见组合优化问题的有效算法三、其它一些常见组合优化问题的有效算法 ? 最小生成树问题算法 ? 匹配问题的算法 ? .
