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

はじめに

少し飛びましたが、前回の続きやっていきます。
www.hanachiru-blog.com

今回のテーマは「動的計画法」になります。

<br />

はじめに
概要
ロッド切り出し問題
- 動的計画法適応
  - トップダウン型の動的計画法
  - ボトムアップ型の動的計画法
- 部分問題グラフ
連鎖行列積問題

概要

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

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

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

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

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

ロッド切り出し問題

入力：長さ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$ も同様．

第２段階：再帰的な解

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]と定義する．

第３段階：最適コストの計算

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

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

実行時間は $O(n^3)$ ．

第４段階：最適解の構成

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

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

はなちるのマイノート

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