学生版 社会人版
JA EN

#approximation-algorithms

1 記事

01 ·計算量と評価·★ 会員·16分で読めます 近似アルゴリズム — 厳密を諦めて保証を取る 最適解を諦める代わりに「最悪でも◯倍以内」という値札を付ける技術。近似比の定義から、貪欲アルゴリズムの保証を最後まで証明する手つき、巡回セールスマンで三角不等式の有無が結論をひっくり返す理由までを前提知識ゼロで積み上げます。