練習問題

\(\textsc{SubsetSum}\) を一般化した次の問題に対する再帰的なアルゴリズムを説明してください。

1. 正の整数からなる配列 \(X[1..n]\) と整数 \(T\) が与えられたときに、和が \(T\) となる \(X\) の部分集合の数を求める。

2. 正の整数からなる二つの配列 \(X[1..n]\) と \(W[1..n]\) と \(T\) が与えられ、\(W[i]\) が \(X[i]\) の重さ (weight) を表しているときに、和が \(T\) となる \(X\) の部分集合の中で重さが最大となるものの重さを求める。和が \(T\) となる \(X\) の部分集合がない場合には \(- \infty\) を返す。

次にあげる文字列分割問題の変種に対する再帰的なアルゴリズムを説明してください。文字列を受け取ってそれが "単語" を表す場合に限って \(\textsc{True}\) を返すサブルーチン \(\textsc{IsWord}\) が使えると仮定してください。

1. 文字列 \(A[1..n]\) が与えられたときに、\(A\) を単語の並びに分割する方法の数を求める。例えば、\(\color{maroon}{\texttt{ARTISTOIL}}\) という文字列は \(\color{maroon}{\texttt{ARTIST} \cdot \texttt{OIL}}\) と \(\color{maroon}{\texttt{ART} \cdot \texttt{IS} \cdot \texttt{TOIL}}\) に分割できるので、アルゴリズムはこの文字列に対して \(2\) を返す。

2. 二つの文字列 \(A[1..n]\) と \(B[1..n]\) が与えられたときに、同じ添え字を使って \(A\) と \(B\) を単語の列に分割できるかどうかを判定する。例えば \(\color{maroon} \texttt{BOTH} \)\( \color{maroon} \texttt{EART} \)\( \color{maroon} \texttt{HAND} \)\( \color{maroon} \texttt{SATU} \)\( \color{maroon} \texttt{RNSPIN}\) と \(\color{maroon} \texttt{PINS} \)\( \color{maroon} \texttt{TART} \)\( \color{maroon} \texttt{RAPS} \)\( \color{maroon} \texttt{ANDR} \)\( \color{maroon} \texttt{AGSLAP}\) は次のように同じ添え字を使って単語の列に分割できるので、アルゴリズムは \(\textsc{True}\) を返す。 \[ \begin{aligned} \color{maroon}{\texttt{BOT} \cdot \texttt{HEART} \cdot \texttt{HAND} \cdot \texttt{SAT} \cdot \texttt{URNS} \cdot \texttt{PIN}} \\ \color{maroon}{\texttt{PIN} \cdot \texttt{START} \cdot \texttt{RAPS} \cdot \texttt{AND} \cdot \texttt{RAGS} \cdot \texttt{LAP}} \end{aligned} \]

3. 二つの文字列 \(A[1..n]\) と \(B[1..n]\) が与えられたときに、同じ添え字を使って \(A\) と \(B\) 両方を単語の列に分割する方法の数を求める。

整数 \(n\) に対する加算鎖 (addition chain) とは、 \(1\) で始まって \(n\) で終わる増加数列であって各要素がそれまでに出てきた二つ要素の和として表せるものを言います。つまり、整数の列 \(x_{0} < x_{1} < x_{2} < \ldots < x_{l}\) が整数 \(n\) の加算鎖であることは、次の条件を満たすことと同値です:

• \(x_{0} = 1\)
• \(x_{l} = n\)
• 任意の \(k > 0\) に対して、ある添え字 \(i \leq j < k\) が存在して \(x_{k} = x_{i} + x_{j}\) となる

加算鎖の長さとは数列の長さから \(1\) を引いたものです (最初の要素は長さに含まれません)。例えば、\(\langle 1, 2,\) \(3, 5,\) \(10, 20, 23,\) \(46,92, 184,\) \(187, 374 \rangle\) は 374 の加算鎖であり、長さは 11 です。

1. 与えられた \(n\) に対する加算鎖の長さの最小値を求めるバックトラッキングを使った再帰的アルゴリズムを説明してください。特に興味がある場合を除いて、アルゴリズムを解析したり最適化しようとしないでください。満点のためには、実行時間が \(n\) に関して指数的で正しく動くアルゴリズムが答えられれば十分です。 [ヒント: この問題は文字列の分割問題よりも \(n\) クイーン問題に近いです。]

2. ❤ 与えられた \(n\) に対する加算鎖の長さの最小値を求めるバックトラッキングを使った再帰的アルゴリズムで、実行時間が \(n\) に対して劣指数的 (sub-exponential) であるものを説明してください。 [ヒント: エジプトのロープ絞め士、インダス川の韻律学者、ロシアの農民たちが気付いたことが、この問題でも有効です。]

1. \(A[1..m]\) と \(B[1..n]\) を任意の配列とします。 \(A\) と \(B\) の共通部分列 (common subsequence) とは \(A\) の部分列でもあり \(B\) の部分列でもあるような配列を言います。 \(A\) と \(B\) の最長共通部分列の長さを表す関数 \(\mathit{lcs}(A, B)\) の単純で再帰的な定義を示してください。

2. \(A[1..m]\) と \(B[1..n]\) を任意の配列とします。 \(A\) と \(B\) の共通超配列 (common supersequence) とは \(A\) と \(B\) の両方を部分列として含む配列のことを言います。 \(A\) と \(B\) の最短共通超配列の長さを表す関数 \(\mathit{scs}(A, B)\) の単純で再帰的な定義を示してください。

3. 配列 \(X[1..n]\) がバイトニック (bitonic) であるとは、ある添え字 \(i\ (1 < i < n)\) が存在して、接頭部分 \(X[1..i]\) が増加列で接尾部分 \(X[i..n]\) が減少列となること言います。与えられた整数の配列 \(A\) の最長バイトニック部分列の長さを求める関数 \(\mathit{lbs}(A)\) の単純で再帰的な定義を示してください。

4. 配列 \(X[1..n]\) が振動している (oscillating) とは、全ての偶数 \(i\) について \(X[i] < X[i + 1]\) であり、全ての奇数 \(i\) について \(X[i] > X[i+1]\) であることを言います。与えられた整数の配列 \(A\) の最長振動部分列の長さを求める関数 \(\mathit{los}(A)\) の単純で再帰的な定義を示してください。

5. 与えられた整数の配列 \(A\) の最短振動超配列の長さを求める関数 \(\mathit{sos}(A)\) の単純で再帰的な定義を示してください。

6. 配列 \(X[1..n]\) が凸 (convex) であるとは、全ての \(i\) について \(2 \cdot X[i] < X[i - 1] + X[i + 1]\) が成り立つことを言います。与えられた整数の配列 \(A\) の最長凸部分列の長さを求める関数 \(\mathit{lxs}(A)\) の単純で再帰的な定義を示してください。

この問題の入力は二つの配列 \(X[1..k], Y[1..n]\) (\(k \leq n\)) です。

1. \(X\) が \(Y\) の部分列であるかを判定するバックトラッキングを使った再帰的なアルゴリズムを説明してください。例えば文字列 \(\color{maroon}{\texttt{PPAP}}\) は文字列 \(\color{#2D2F91}{\texttt{P}} \color{maroon}{\texttt{EN}} \)\( \color{#2D2F91}{\texttt{P}} \color{maroon}{\texttt{INE}} \)\( \color{#2D2F91}{\texttt{A}} \color{maroon}{\texttt{PPLEAPPLE}} \)\( \color{#2D2F91}{\texttt{P}} \color{maroon}{\texttt{EN}}\) の部分列です。

2. \(Y\) から要素を取り除いて \(X\) を \(Y\) の部分列でなくなるようにするとき、取り除かなくてはならない最小の要素数を求めるバックトラッキングを使った再帰的なアルゴリズムを説明してください。同じことですが、\(X\) の超配列でない \(Y\) の部分列のうち最長のものを求める問題を解くアルゴリズムを考えても構いません。例えば \(\color{maroon}{\texttt{PENPINE}} \color{#2D2F91}{\texttt{A}} \color{maroon}{\texttt{PPLE}} \color{#2D2F91}{\texttt{A}} \color{maroon}{\texttt{PPLEPEN}}\) から二つの \(\color{#2D2F91}\texttt{A}\) を取り除いた文字列は \(\color{maroon}{\texttt{PPAP}}\) を部分列として持ちません。

3. ❤ \(Y\) の互いに重ならない二つの部分列の両方に \(X\) が含まれることがあるかを判定するバックトラッキングを使った再帰的なアルゴリズムを説明してください。例えば \(\color{#2D2F91}{\texttt{P}} \color{maroon}{\texttt{EN}} \color{#2D2F91}{\texttt{P}} \color{maroon}{\texttt{INE}} \color{#2D2F91}{\texttt{A}} \color{green}{\texttt{PP}} \color{maroon}{\texttt{LE}} \color{green}{\texttt{A}} \color{#2D2F91}{\texttt{P}} \color{maroon}{\texttt{PLE}} \color{green}{\texttt{P}} \color{maroon}{\texttt{EN}}\) の中には \(\color{maroon}{\texttt{PPAP}}\) が二つの互いに重ならない部分列として含まれます。

特に興味がある場合を除いて、アルゴリズムの実行時間の解析をしないでください。三つのアルゴリズムは全て指数時間で実行されますが、次の章で改善する方法を示すので、現時点での正確な実行時間は重要ではありません。

この問題では、鍵 \(A[1..n]\) と頻度 \(f[1..n]\) を受け取って探索コストを最小にする最適二分探索木を作る、バックトラッキングを使ったアルゴリズムを設計します。この設定は本文中で触れた問題と同じですが、この問題では追加の制約があります。

1. AVL 木 (AVL tree) は自動的にバランスが保たれる二分探索木のうち最初に発見されたものであり、1962 年に Georgy Adelson-Velsky (ゲオルギー・アデルソン・ヴェルスキー) と Evgenii Landis (エフゲニー・ランディス) によって提案されました。AVL 木では任意の頂点 \(v\) について、\(v\) の左右の部分木の高さは最大でも \(1\) しか違いません。

   鍵と頻度を表す配列を受け取って最適な AVL 木を返す、バックトラッキングを使った再帰的なアルゴリズムを説明してください。

2. 対称二分 B 木 (symmetric binary B-tree) も自動的にバランスが保たれる二分木であり、1972 年に Rudolf Bayer (ルドルフ・ベイヤー) によって提案されました。1978 年に Robert Sedgewick (ロバート・セッジウィック) と Leonidas Guibas (レオニダス・ギバス) によって単純な形に変形され、現在では赤黒木 (red-black tree) という名前で知られています。

   赤黒木は次の制約を持つ二分探索木です:

   • 全ての頂点は赤または黒である。
   • 赤い頂点の親は黒い。
   • 根から葉への任意の道は同じ数の黒い頂点を含む。

   鍵と頻度を表す配列を受け取って最適な赤黒木を返す、バックトラッキングを使った再帰的なアルゴリズムを説明してください。

3. AA 木 (AA tree) は 1993 年に Arne Andersson (アルネ・アンデルソン) によって提案され、2000 年に Mark Allen Weiss (マーク・アレン・ウェイス) によって単純化され (そして名前を付けられ) ました。2006 年には Robert Sedgewick によって鏡写しの (バランスを保つためのアルゴリズムが異なる) データ構造が提案されていますが、このデータ構造は "AA 木" ではなく "左に傾いた赤黒木" と呼ばれました。

   AA 木は次の追加の制約を持つ赤黒木です:

   • 左の子は赤くない¹。

   鍵と頻度を表す配列を受け取って最適な AA 木を返す、バックトラッキングを使った再帰的なアルゴリズムを説明してください。

   特に興味がある場合を除いて、アルゴリズムの実行時間の解析をしないでください。三つのアルゴリズムは全て指数時間で実行されますが、次の章で改善する方法を示すので、現時点での正確な実行時間は重要ではありません。