平滑分析（Smoothed Analysis）

平滑分析是一种衡量算法性能的分析范式,由斯皮尔曼和滕尚华于二零零一年提出,并因此获得哥德尔奖和内万林纳奖。它对每个输入实例施加一个小幅度的随机扰动,然后考察扰动后运行时间的期望,以此在最坏情况与平均情况之间取得平衡。

概述

传统的最坏情况分析常对精心构造的病态输入给出悲观结论,而平均情况分析又依赖于往往不真实的输入分布假设。平滑分析假设真实输入是一个对抗者选定的实例再受到自然噪声的轻微干扰,更贴近工程现实。

核心原理

• 取任意实例,对其数值加上一个方差由扰动参数控制的随机噪声。
• 运行时间被定义为在所有实例上取最坏、再在噪声上取期望的量。
• 当扰动趋于零时结果退化为最坏情况分析,当扰动很大时接近平均情况分析。
• 若平滑复杂度是输入规模和扰动倒数的多项式,则称算法具有多项式平滑复杂度。

应用场景

平滑分析最著名的成功是解释单纯形法。该线性规划算法在最坏情况下可能指数步,但在实践中几乎总是很快,平滑分析证明其平滑复杂度是多项式的。此外它还被用于分析k均值聚类、局部搜索、若干整数规划启发式以及某些数值算法,为它们在现实中的良好表现提供了理论依据。

常见问题

问:平滑分析和平均情况分析有何不同?答:平均情况在整个随机分布上取期望,而平滑分析先让对抗者挑最坏实例再叠加噪声,因此结论对所有实例邻域都成立,比平均情况更稳健。

问:它能否证明单纯形法是多项式时间算法?答:不能直接得出这一结论。平滑分析证明的是加了噪声后期望步数为多项式,而在无扰动的严格最坏情况下单纯形法仍可能指数步。