設計指針

アルゴリズムの設計指針

アルゴリズムを設計する際の様々な指針について紹介する。

強欲アルゴリズム: 単一の戦略で解く
分割統治法: 問題を小さく分割してアタック
再帰法: 小サイズの問題の解を仮定して解く（数学的帰納法）
動的計画法: 部分問題の解を保存して利用
試行錯誤法: しらみつぶしに調べる

１．強欲アルゴリズム

単一の戦略で、局面ごとの最適手(解)が選択できるような問題に適用

例．コインの支払い問題：$x$円を支払う最少枚数の硬貨を求めよ
100円、50円、10円、5円、1円の各硬貨が（十分な枚数）ある。
戦略：高い硬貨から順に、その硬貨で支払えるだけ支払う（$\div$は切り捨て、$\text{mod}$は割った余り）
①100円硬貨で$(x\div 100)$枚支払い残額を$x$とする（$x\leftarrow x \mod 100$）
② 50円硬貨で$(x\div\ \ 50)$枚支払い残額を$x$とする（$x\leftarrow x \mod\ \ 50$）
③ 10円硬貨で$(x\div\ \ 10)$枚支払い残額を$x$とする（$x\leftarrow x \mod\ \ 10$）
④　5円硬貨で$(x\div\ \ \ \ 5)$枚支払い残額を$x$とする（$x\leftarrow x \mod\ \ \ \ 5$）
⑤　1円硬貨で$x$枚支払う

40円硬貨があると、強欲アルゴリズムは適用できない。
パズル：50円、40円、10円硬貨で80円支払う最少枚数は？

強欲アルゴリズムが与える解をもとめよ
最少枚数解を求めよ

２．分割統治法

問題を
・互に独立な部分問題に分割し
・それらの解を組み合わせて
もとの問題を解く

全体問題を解く：主プログラム、関数 main
部分問題を解く：サブルーチン、手続き、関数

ライブラリ：共通して使われる部分問題アルゴリズム集
　整列アルゴリズム、辞書クラス

３．再帰法

分割統治法で、部分問題に、元の問題と同じでサイズの小さな問題が現れるとき
問題の解が(分からなくても)あると仮定して解ける（数学的帰納法、再帰呼出し）

例．ハノイの塔：右図のように置かれた$n$枚の円板を
左端の杭から右端の杭に移す。その際、
　①移動は杭から杭へ一枚ずつ
　②円板をより小さな円板の上には置けない　　　　　（ウィキペディアより）
解．円盤が0枚($n=0$)なら何もしなくてよい
$n-1$枚の円板が移せると仮定して
　①上の$n-1$枚の円板を左端から中央に移す
　②最大(一番下)の円板を左端から右端に移す
　③中央の$n-1$枚の円板を右端に移す

パズル．$n=4$のハノイの塔を手を動かして解いてみよう。

整列アルゴリズムの再考
基数法以外を再帰的観点から、
問題分割と解の統合の手法を整理
（桃色は手間をかけている部分）
計算時間は、分割のサイズによる
　1つと残り⇒$n^2$、均等⇒$n\log_2n$
再帰アルゴリズムでは、
　部分問題のサイズ均等化⇒効率化

アルゴリズム	問題分割	解の統合	時間オーダー
選択ソート	最大値と残り	不要	$n^2$
クイックソート	基準値以下と以上	不要	平均$n\log_2n$
挿入ソート	１個と残り	挿入(併合)	$n^2$
マージソート	半分ずつ	併合	$n\log_2n$

注．挿入・マージソートの再帰版は、デモの最終ステップを考えると分かりやすい

動的計画法（ダイナミックプログラミング）

再帰法で同じ部分解を繰り返し必要とする場合に、部分解の表を作り再計算をさける
・メモ化再帰：再帰呼び出しで一度計算した部分解を表に保持する
・表作成：必要になりそうな部分解を(小さい方から順に)すべて構成する

例．フィボナッチ数列 $\ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ \dots$
$f_{ib}(n)=\begin{cases} 1 & n<3 \\ f_{ib}(n-1)+f_{ib}(n-2) & それ以外 \end{cases}$

表作成：$f_{ib}(1), f_{ib}(2), \dots, f_{ib}(n)$の順に求める

パズル．[再帰法]計算の再帰回数と$f_{ib}(n)$の値との関係を求めよ。
([再帰法]で大きな$n$の$f_{ib}(n)$を計算してはいけない！)

コラム．

$f_{ib}(n)=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n=\left[\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n\right]=\left[\frac{(1.618\cdots)^n}{2.236\cdots}\right]$
（[]は小数点以下四捨五入）という式でも計算できる。ただし計算誤差が生じ$f_{ib}(76)$の[補足]は、[表作成]や[メモ化再帰]の正しい値からずれる。
ユークリッドの互除法は高速：最も手間がかかるのは次の場合で、$\bmod$が$n$回必要になる
$\gcd(f_{ib}(n),f_{ib}(n+1))\\ =\gcd(f_{ib}(n+1),f_{ib}(n))\\ =\gcd(f_{ib}(n),f_{ib}(n-1))\\ \cdots\\ =\gcd(f_{ib}(3),f_{ib}(2))　(=\gcd(2,1)）\\ =\gcd(1,0)=1$
つまり、互除法による$\gcd(j,k)$の最悪計算時間は $\log_{1.618}(\min(j,k))$ に比例する

例．一般的なコインの支払い問題
$p_{ay}(x):x$円の最少支払枚数、支払えない場合は無限大
再帰式０：最少支払いを分割した各々も最少支払なので
$p_{ay}(x)=\begin{cases} 1 & x円硬貨がある\\ \displaystyle \min_{0\lt y\lt x}(p_{ay}(y)+p_{ay}(x-y)) & それ以外 \end{cases}$
再帰式１：最少支払から硬貨を1枚除いたものも最少支払なので
$p_{ay}(x)=\begin{cases} 1 & x円硬貨がある\\ \displaystyle \min_{y円硬貨}　(p_{ay}(x-y)+1) & それ以外 \end{cases}$

表作成法における工夫：「使える硬貨の種類を1つずつ増やす」
　すべての$x$に対し、$g(x)\leftarrow \infty$
　各$y$円硬貨について
　　$p_{ay}(x)\leftarrow \min(p_{ay}(x),p_{ay}(x-y)+1)$
　に基づき、$p_{ay}(x)$の表を計算しなおす

メモ化再帰と表作成法

パズル．3,5円硬貨で11円支払う場合をアプリで求め、その計算過程を調べてみよう。

(メモ化)再帰法：
　部分問題への分割ができれば、直接的な解法の記述は不必要
　再帰呼び出しには、それなりの負荷がかかる。
　再帰プログラムを自動的にメモ化して実行するシステムもある。
表作成法：
　直接的な解法の記述が必要。
　一般に高速
　不要な値を計算する可能性がある。

遅延評価
　式の評価を、実際に必要になるまで遅らせる手法や実装。

試行錯誤法

解の各候補 $x$
　$x$が解ならば $x$ を出力(して終了)

候補を、途中解を伸ばしていって構成する（迷路等）⇒再帰法
　Solve($x$)
　　$x$ が解なら出力(して終了)
　　$x$ からの各伸長候補 $w$
　　　Solve($xw$)
と定義して Solve(空) とする。
再帰呼び出しの実現法により、この手法が行うのは
　途中解を伸ばせるだけ伸ばして失敗したら戻る、解空間の深さ優先探索

伸長候補の順位付け：評価関数
・伸長しても解が得られないことがあらかじめ分かれば、候補に入れない
・解が得られそうな候補から順に調べる

アルゴリズムの考え方：設計指針