はなちるのマイノート

Unityをメインとした技術ブログ。自分らしくまったりやっていきたいと思いますー!

アルゴリズムイントロダクション第15章前半の個人まとめ

概要

動的計画法は部分問題の解を結合することによって問題を解く方法である.

動的計画アルゴリズムは以下の四つの段階を経て開発される.

  1. 最適解の構造を特徴づける
  2. 最適解の値を再帰的に定義する
  3. 最適解の値を計算する
  4. 計算された情報から一つの最適解を構成する

今回の記事では以下の二つの問題に対して動的計画法を用いて考える.

  • ロッド切り出し問題
  • 連鎖行列積問題

ロッド切り出し問題

入力:長さnインチの金属の棒,長さ i \in \{1,2,...,n\}に対応する価格 p_iの表
出力:収益の最大値

全通りの切り方(左端から長さiで切るor切らない)を試すと, 2^{n-1}となり指数時間かかってしまう.

動的計画法適応

棒の分割を n = i_1 + i_2 + ... + i_kのように表すと,長さnの金属棒の収益の最大値r_nは以下で表せる.
 r_n = p_{i_1} + p_{i_2} + ... + p_{i_k}

より一般化してみる.
 r_n = max(p_n, r_1 + r_{n-1}, r_2 + r_{n-2}, ... , r_{n-1} + r_1)
 r_n = max_{1 \leq i \leq n}(p_i + r_{n-i}) 

トップダウン型の動的計画法
f:id:hanaaaaaachiru:20211129180326p:plain
MEMOIZED-CUT-ROD(p, n)
f:id:hanaaaaaachiru:20211129180641p:plain
MEMOISED-CUT-ROD-AUX(p, n, r)
ボトムアップ型の動的計画法
f:id:hanaaaaaachiru:20211129181002p:plain
BOTTOM-UP-CUT-ROD(p, n)


実行時間は漸近的に同じ \Theta(n^2)

部分問題グラフ

部分問題グラフは有効グラフであり,部分問題を一つの頂点として表し,部分問題xの最適解を決定する手順に直接的に部分問題yの最適解を利用するなら辺を繋ぐ.

f:id:hanaaaaaachiru:20211129181832p:plain
n=4のロッド切り出し問題の部分問題グラフ

典型的には,ある部分問題の解の計算時間はその部分問題に対応する部分問題グラフ上の頂点の次数(外向辺の数)に比例し,部分問題の数は部分問題グラフの頂点数と一致する.

連鎖行列積問題

入力:n個の行列 A_1, A_2, ... , A_n
出力: A_1, A_2, ... ,A_nの最小スカラー乗算回数

ただし今回は行列の行・列のサイズのみ必要な情報のため, i = 1, 2, ..., nに対して行列 A_i p_{i-1} \times p_iとし,入力を p_0, p_1, ... , p_nとする.

括弧つけの個数を P(n)としてとき,愚直に全ての括弧付けを調べる.
 P(n) = \begin{cases}1 & n =1のとき\\\sum_{k=1}^{n-1}P(k)P(n-k) & n \geq 2のとき\end{cases}

これを計算すると \Omega(4^n/n^{3/2})であり指数時間となる.

第一段階:最適括弧付けの構造

動的計画法適応にあたって問題が部分構造最適性を持つか調べる.

 i \leq jとしたとき,積 A_iA_{i+1}・・・A_jを計算した結果である行列を A_{i..j}と書く.

f:id:hanaaaaaachiru:20211129183606p:plain
Ai..jの定義
f:id:hanaaaaaachiru:20211129183858p:plain
Ai..jの計算

部分構造最適性を証明する.

 A_iA_{i+1}...A_jの最適括弧付けは,積を A_k A_{k+1}で分割すると仮定する.このとき A_iA_{i+1}...A_k A_{k+1}A_{k+2}...A_jは最適な括弧つけでなければならない.

なぜなら, AiA_{i+1}...A_kに対してより効率的な括弧つけがあったとするなら, A_iA_{i+1}...A_jのそれに置き換えたものを使うことでより効率的になるからである. A_{k+1}A_{k+2}...A_jも同様.

第2段階:再帰的な解

m[i,j]を行列 A_{i..j}の計算に最小限必要なスカラー乗算回数とすると以下の漸化式がなりたつ.

 m[i,j] = m[i,k] + m[k+1,j] + p_{i-1}p_kp_j

上式ではkを既知の値として考えているが,kはj-i通りあるので未知とすると以下の式が成り立つ.

 m [ i,j ] = \begin{cases}0 & i = j\\min_{i \leq k < j}\{ m [ i,k ] + m [ k+1,j ] + p_{i-1}p_kp_j   \} & x > 0\end{cases}


また分割地点kをs[i,j]と定義する.

第3段階:最適コストの計算

ボトムアップの動的計画法を記述する.

f:id:hanaaaaaachiru:20211129185604p:plain
MATRIX-CHAIN-ORDER(p)


実行時間は O(n^3)

第4段階:最適解の構成

最適な分割地点をs[i,j]に記録していたので,以下の関数により括弧付けを出力できる

f:id:hanaaaaaachiru:20211129185621p:plain
PRINT-OPTIMAL-PARENS(s,i,j)