Smoothed Analysisはアカデミア以外で使用されていますか？

Question

やった 平滑化された分析 アルゴリズムのメインストリーム分析への道を見つけますか？アルゴリズム設計者がアルゴリズムにスムーズな分析を適用することは一般的ですか？

Answer 1

私は間違っているかもしれませんが、私はスムーズな分析を 説明 理論的保証が悪い（シンプレックス、k-meanなど）を持つアルゴリズムの実践的な動作。それが何を意味するのかわかりません 使用する 実際のスムーズな分析は、悪い最悪のパフォーマンスを備えた特定のヒューリスティックの使用を正当化することを除きます（「私のヒューリスティックには何とか最悪の場合の動作がありますが、スムーズな分析は、実際にはうまくいくことを示しています」）

Answer 2

現実世界のアルゴリズムを人々が分析する方法は、学界とは大きく異なります。アカデミアでは、目標は実行時間で証明された補正上限を見つけることです。実生活では、目標はアルゴリズムがどのように機能するか、そしてどの微調整が実行時間を改善できるかを理解することです。学界では禁止されているが、実際には使用されている2つの主要な方法があります。

• 近似の方法。ここでは、多くの単純化された仮定を使用して、アルゴリズムの実行時間を予測しようとします。理論物理学者（以前）がすることと同様。
• 実験。アルゴリズムを実行し、いくつかの統計を測定します - 各パートにどれだけの時間がかかったか、各関数が呼び出された回数、各ブランチが実行される頻度など。この情報は、アルゴリズムを最適化するために使用できます。実験は、アルゴリズムの動作中に実際に機能するかどうかを確認するためにも使用されます。

とはいえ、関連するアカデミック出版物にフィラーテキストを追加する以外に、実際にアルゴリズムを分析することは非常に一般的ではないと思います。焦点は、主題に応じて、ソフトウェアエンジニアリングまたは低レベルの最適化にあります。

最後に、Smoothed Analysisは、最悪の場合よりもアルゴリズムが実際に機能する理由を説明するために使用できるヒューリスティックです。つまり、いくつかの入力はある意味で「ランダム」であるためです。このヒューリスティックは、近似の方法を使用している場合、アルゴリズムの動作を近似するために使用できます。