# アルゴリズム設計技法 ## 定義 アルゴリズム設計技法(algorithm design paradigms)とは、個別の問題を超えて再利用できる、アルゴリズムの構成様式である。分割統治・動的計画法・貪欲法・乱択化・近似・並列化がその代表であり、それぞれ「どういう条件を満たす問題に適用できるか」という適用条件と、「その条件が成り立つとき実行時間がどう評価できるか」という解析様式を対にして持つ。(Source: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 4 分割統治]], [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 15 動的計画法]], [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 16 貪欲アルゴリズム]]) 技法は独立ではなく階層をなす。動的計画法と貪欲法はいずれも部分構造最適性を要求するが、貪欲法はさらに強い貪欲選択性を要求するため適用範囲が狭い代わりに実行時間が小さい。0-1 ナップサック問題と分割可能ナップサック問題の対比が、この境界を最小の例で示している。乱択化は入力分布への仮定を置く確率的解析と区別され、最悪ケースの脆弱性を仮定なしに除く手段として使われる。 ## 適用条件による技法の分類 - **分割統治は「部分問題が独立に解ける」ことを要求し、その代償として同じ部分問題を重複して解く。** 部分問題が重複するときは動的計画法が同じ再帰式を表計算に変えて指数時間を多項式時間へ落とす。 - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 4 分割統治]] — 漸化式 $T(n)=aT(n/b)+f(n)$ を主定理の 3 ケースで解く枠組みを与える - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 15 動的計画法]] — 部分構造最適性と部分問題の重複という 2 条件、トップダウンのメモ化とボトムアップの表計算という 2 実装様式 - **貪欲法は部分構造最適性に加えて貪欲選択性を要求し、動的計画法の真部分集合として位置づく。** 分割可能ナップサック問題は貪欲選択性を持つが 0-1 ナップサック問題は持たない。 - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 16 貪欲アルゴリズム]] — 活動選択問題・ハフマン符号・マトロイド上の GREEDY - 関連: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 23 最小全域木]] — 安全な辺という不変式で貪欲法を正当化する定理 23.1 - **乱択化は入力の悪い並びに対する脆弱性を、入力への仮定を置かずに除く。** 確率的解析が入力分布を仮定するのに対し、乱択アルゴリズムはアルゴリズム自身が乱数を使うため、任意の入力に対して期待実行時間が保証される。 - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 5 確率的解析と乱択アルゴリズム]] — 雇用問題で両者を並置して区別を導入 - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 7 クイックソート]] — §7.2 が確率的解析、§7.3 が乱択化として同じ区別を実例化 - 関連: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 11 ハッシュ表]] — universal hashing が単純一様ハッシュの仮定を不要にする同型の構図 - **近似は NP 完全問題に対して最適性を諦め、近似比という保証に置き換える。** 保証の強さは定数近似・対数近似・FPTAS という階層をなす。 - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 35 近似アルゴリズム]] — 頂点被覆の 2 近似、集合被覆の調和数近似、部分和問題の FPTAS - 留保: 三角不等式を満たす TSP は 2 近似が可能だが、一般 TSP は $P \ne NP$ の下で定数近似が不可能である(定理 35.3) ## 実行時間の評価様式 - **ならし解析は確率を使わず、最悪の操作列に対する 1 操作あたりの平均コストを求める。** 集計法・出納法・ポテンシャル法の 3 手法は同じならしコストを異なる形式で与えるだけで、証明の強さは同等である。 - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 17 ならし解析]] — MULTIPOP・2 進カウンタ・動的な表の 3 例 - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 19 フィボナッチヒープ]] — ポテンシャル関数 $\Phi(H)=t(H)+2m(H)$ により DECREASE-KEY をならし $O(1)$ にする - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 21 互いに素な集合族のためのデータ構造]] — ランクによる併合と経路圧縮の $O(m\,\alpha(n))$ をポテンシャル法で証明する - **並列化では逐次の実行時間 1 つではなく、仕事量 $T_1$ とスパン $T_\infty$ の 2 尺度で評価する。** 並列度 $T_1/T_\infty$ が達成可能な高速化の上限を与え、貪欲スケジューラは $T_P \le T_1/P + T_\infty$ で最適の 2 倍以内に収まる。 - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 27 マルチスレッドアルゴリズム]] — 第 2 章のマージソートと第 4 章の行列乗算をこの尺度で再解析する - **同一のアルゴリズムでも、内部で使うデータ構造の選択が漸近計算量を変える。** - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 23 最小全域木]] — Prim は 2 分ヒープで $O(E \lg V)$、フィボナッチヒープで $O(E + V \lg V)$ - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 24 単一始点最短路問題]] — Dijkstra は優先度付きキューの実現により $O(V^2)$ から $O(V \lg V + E)$ まで変わる ## 未解決の問い - 分割統治・動的計画法・貪欲法の 3 者は適用条件の強さで一列に並ぶが、乱択化・近似・並列化はこの列とは直交する軸である。6 技法を統一的に整理する軸は立てられるか。 - ならし解析のポテンシャル法は、フィボナッチヒープや互いに素な集合族のように「後で払う」構造には効くが、ポテンシャル関数の発見自体には系統的な手続きがない。設計と解析を同時に進める方法はあるか。 - マトロイド理論は貪欲法が最適解を返す問題を特徴づけるが、動的計画法に対応する同種の代数的特徴づけは知られているか。 ## 未編纂の観察 - **同じ「比較の下界を回避する」構図が、ソートと優先度付きキューの両方で繰り返される。** 第 8 章は比較ソートの $\Omega(n\lg n)$ 下界を決定木モデルで示したうえで、キーが小さい整数だという追加情報を使う計数ソート・基数ソート・バケツソートでこれを回避する。第 20 章は比較に基づく優先度付きキューの $\Omega(\lg n)$ を、キーが $\{0,\dots,u-1\}$ の整数だという同種の追加情報で回避し $O(\lg\lg u)$ を得る。すなわち「下界は計算モデルに対して立つのであって問題に対して立つのではない」という一点が、異なる部(第 II 部と第 V 部)で二度示されている。(Source: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 8 線形時間ソート]], [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 20 van Emde Boas木]]) - **既存のデータ構造に属性を足して新操作を得るという「補強」は、それ自体が 1 つの設計技法として明示されている。** 第 14 章は 2 色木に部分木サイズを足して順序統計量木を、端点最大値を足して区間木を作る手順を 4 段階に定式化し、定理 14.1 で「属性が自身と両子から計算できるなら挿入・削除の $O(\lg n)$ を損なわずに維持できる」という一般条件を与える。第 13 章の 2 色木・第 18 章の B 木・第 19 章のフィボナッチヒープが個別の構造を作るのに対し、第 14 章だけが構造を作る手続きを対象にしている。(Source: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 14 データ構造の補強]], [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 13 2色木]]) - **緩和(RELAX)・安全な辺・増加道は、いずれも「不変式を保ちながら 1 ステップ進める」という同型の骨格を持つ。** 第 24 章は 3 つの最短路アルゴリズムの違いを「RELAX をどの順序で何回適用するか」だけに還元し、第 23 章は最小全域木の一般法を「安全な辺を 1 本ずつ加える」に還元し、第 26 章は最大フローを「残余ネットワーク上の増加道でフローを増やす」に還元する。いずれも正当性の証明は不変式(上界性質・$A$ がある最小全域木の部分集合・フロー保存則)の維持に帰着し、具体的アルゴリズムはステップの選び方の違いにすぎない。(Source: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 24 単一始点最短路問題]], [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 23 最小全域木]], [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 26 最大フロー]]) - **近似アルゴリズムの近似比証明は、最適解の値を直接扱わず「計算しやすい下界」との比で示すという共通の型を持つ。** 頂点被覆の 2 近似は極大マッチングのサイズを、TSP の 2 近似は最小全域木の重みを、重み付き頂点被覆は線形計画緩和の最適値を、それぞれ最適解の下界として使う。第 34 章の帰着が「問題 A が解ければ問題 B も解ける」という上向きの議論であるのに対し、これは「最適解はこれ以上小さくならない」という下向きの議論であり、両者が対をなして近似可能性の議論を支えている。(Source: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 35 近似アルゴリズム]], [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 34 NP完全性]]) ## 関連 - 書籍: [[アルゴリズムイントロダクション 第3版]] - 概念: [[計算複雑性]] / [[グラフアルゴリズム]] ## 出典 - T. コルメン, C. ライザーソン, R. リベスト, C. シュタイン 共著, 『アルゴリズムイントロダクション 第3版 総合版』, 近代科学社, 2013, 第 4・5・7・8・11・13・14・15・16・17・19・20・21・23・24・26・27・35 章.