授業資料/12

Top / 授業資料 / 12

前回の課題について
動的計画法もどき
- 動的計画法もどきと再帰定義の例
  - フィボナッチ(Fibonacci)数
  - ツリー(木構造)のノードの関係
今日の総仕上げ
- 上級者向け
レポート
about Icons, ClipArts

前回の課題について †

さて，前回の課題について説明しよう．課題を再掲すると以下のとおりである．

ファイル操作とファイル入出力の両方を使う必要がある，次の条件を満たすプログラムを書け．ただし条件は以下の通りである．

入力用のデータが入っているファイル名を一つめの起動パラメータとしてもらう
実行時にまずは最初にファイルのバックアップを行う
二つめの起動パラメータは1文字である．その文字を c と表しておくと，プログラムは入力データの各行がその文字 c を何文字含んでいるかを調べ，output.dat というファイルに行番号と共に出力する.

↑

全体構造 †

いつものように，まずは全体構造から始めよう．
面倒なところは関数に追い出す基本に則って，つぎのようになるだろう．

ポイントは，「バックアップ操作は可能な限り早めの段階で行う」という点だ．

バックアップ操作の前に他の操作，特にファイルの open などを行うのはなるべく避けるべし．
これは，open のモード指定を間違えると，ファイルの中身が無くなってしまうからだ．バックアップはそうした「危険な操作」の悪影響を受けないようにファイルの中身を万が一に備えてとっておくことなのだから，順番はよくよく考えよう．

だから，

万が一の悪影響を予測して

プログラムを作るべし

ということになる．

↑

関数の実装: バックアップ †

まずは簡単なバックアップ関数の実装だ．といっても単にコピーをすればまずは用は足りるので，次のように簡単に書ける．
もちろん，何代分のバックアップを取るとか，差分をとって圧縮をかけて無駄を減らすとか，きちんとしたバージョンコントロールソフトを使うとか，応用はいくらでもあるので，調べてみるのもよいだろう．

# ファイル名をもらうと，バックアップを行う
def backup(fn)

  # バックアップファイル名を作る．
  bk_fn = fn + ".bak"

  # バックアップ(単なるコピー)
  FileUtils.cp(fn,bk_fn)

end

↑

関数の実装: 文字を数える †

こちらの関数もそんなに大変ではない．今までの知識の範囲内で素直に考えれば例えば以下のようになるだろう．

# 文字列と文字をもらうと，その文字が何回でてくるかをカウントする
def c_count(st, c)

  count = 0
  for i in 1..st.length do
    if (c == st[i-1].chr) then
      count += 1
    end
  end
  
  return count
end

(上級者向け) ちなみに，Ruby には .count という命令がある．調べて使ってみるのもよいだろう．

↑

動的計画法もどき †

さて，今回はコマンド云々ではなく，プログラムそのものの内容だ．
以前，再帰定義を用いたプログラムを学んだが，今回はその逆のやり方を教えよう．
それは動的計画法(もどき)というものである．これを知るには，以前の再帰定義を今一度思い出そう．
再帰定義によるプログラミングとは，まとめてしまえば

[再帰定義によるプログラミングとは]

問題をより小さな問題に分割し，

最後に欲しい答 = より小さな問題の答えの組み合わせ

という定義式を書いて，あとはお任せ

というものであった．いわば，「問題を分割し」「最後の答からアプローチする」方法である．これに対し，動的計画法とは「問題を分割し」「一番小さな問題からアプローチする」方法で，標語的に書いてしまうと

[動的計画法もどきによるプログラミングとは]

問題をより小さな問題に分割し，

一番小さな問題を解いて，答えを保存しておく，そして，

先の答えを利用して次に小さな問題を解いて，答えを保存，

そして… という繰り返しで最後の答えが求まったら終了

というものである．

動的計画法の本来の意義, 定義は
「問題を小さく分解して，『解く必要のない問題を捨てつつ』必要な問題を小さな方から解いてその答えを組みあわせつつより大きな問題を解く」
というもので，最適化問題に対して主に使われるものである．「動的」というのは，様々な判断が計算途中で行われることからついている．
今回は問題を分解して小さな方から解くという部分についてのみ説明しているが，この『解く必要のない問題を捨てる』ことで計算量が小さくなるので，ここも実は重要なところだ．ただし，これを理解するには入門的な今の学習段階では荷が重いので，ここについては今回は説明しない．上級者はそれぞれ調べてみるのもよいだろう．

さて，ピンと来ないだろうから，例をいくつか示そう．

↑

動的計画法もどきと再帰定義の例 †

↑

フィボナッチ(Fibonacci)数 †

まず，既にプログラミングを行ったことのあるフィボナッチ数を例にとろう．
以前フィボナッチ数を求める方法には，再帰定義とループによる二通りがあり，それぞれの特徴やプログラミングについて学んだ．
実は，その「ループによる方法」がここでいう動的計画法もどきによる方法であったのだ．
そして，それらを図にすると次のような関係になる．

どちらの方法も，より小さな問題の答えを利用して大きな問題の答えを得るという「問題の分割」については同じ方法であるが，答えを求めるための考え方の向きが逆である．
そこに着目しよう．

じゃあどちらでも同じじゃん，と思うなかれ．フィボナッチ数の問題は「数列」の問題なので，問題の分割の流れが1次元的なので，同じに見えるのだ．これからの例で，これら二つが同じでないことが分かってくるだろう．

↑

ツリー(木構造)のノードの関係 †

次に，二分木(ノードの下にエッジが二本あるツリー)で，ノードの数字が
「注目しているノードについている数字 = その直下のノードについている数字の合計」
という関係にある例を考えよう．
問題としては，「葉(一番下のノード)」には既に数字が与えられているとして，一番上のノード(根)につくべき数字がいくつか求めよ，という問題としよう．
問題を図にすると，例えば次のようなものになる．

この問題に対して，まず再帰定義で計算するためのプログラムを示そう．

特に難しいところはないだろう．

さて，次に動的計画法もどきにしたがって計算するプログラム(この場合は単なるループだが)を示そう．

動的計画法もどきがだいたいどういうものかわかってきたと思う．
そこで，再帰定義と比較して特徴を述べよう．おおよそ次のような感じだ．

[動的計画法もどきの利点]

メモ化無しの再帰定義に比べ，一般的にプログラムが速く動作する
小さな問題側から解くので，プログラムの動作が明快でわかりやすい
問題によっては，プログラムしやすい

[動的計画法もどきの欠点]

答えに関係ない計算(= ムダ)をしてしまうことがある
問題によってはプログラムが複雑になってしまう

上の特徴のうち，「答えに関係ない計算(= ムダ)をしてしまうことがある」ことについてわかりにくいだろうから例を挙げて説明しよう．例えば，次のような状況で根の値を求めるとしよう．

途中でエッジが切れているために一番下の 3+1 の部分の計算は不要なのだが，データの与え方によってはそれが事前に判明せず，動的計画法もどきだと計算をしてしまうことになる．この計算が重かったり，対象が大きなグラフで，切れている箇所が上の方にあったりするとずいぶんムダが大きくなることになる．一方，再帰定義は必要なものだけが計算されるので，そういう意味でのムダはない．

逆にメモ化無しの再帰定義だとムダな計算が生ずる例を挙げておこう．下図がそうである．

この場合，メモ化無しの再帰定義だと何回も同じ計算をすることになり，その分無駄になる．

このように，問題を分割するという根本的なアイディアは同じだが，実際のプログラムとしては問題によって再帰定義と動的計画法もどきに向き不向きがある．その違いは事前の考察によって分かることが多いので，プログラムを組む前に落ち着いて考えよう．

(上級者向け) これまでの話だけから判断すると「メモ化あり再帰定義最強！」ということになるが，実際はそう単純ではない．なぜなら，再帰定義は答えが求まるまで非常に多くの状態をメモリ上に保持しておかねばならず，「メモリ使用量が莫大になりがち」という欠点を持つし，動的計画法は問題によっては「途中で不要な部分問題を捨てることができて」(今回の授業では触れていない)計算量を大きく減らせるからである．

↑

今日の総仕上げ †

さて，では次の問題を解くプログラムを二つ書こう．まず問題を説明する．

下図にあるような経路を持つ街を考える．すると，Start 地点から Goal 地点までは最短で 10 step で行けるが，その行き方は何通りもある．その行き方が何通りあるか，計算するプログラムを書け．

ただし，プログラムについての条件は以下の通りである．

プログラム A は再帰定義によるものとする．上級者はメモ化しよう．
プログラム B は動的計画法もどきによるものとする．
二つの答えが一致することを確認せよ．

(ヒント) 上の Goal までの最短経路をいきなり考えると難しい．「仮に他の点を Goal とすると，そこまでの最短経路の数はどうか」と考えて，それらがどのような関係にあるか考えてみよう．
例えば，Start 地点のすぐ左側の点が Goal の場合は最短経路数は 1 で，すぐ下も同様に 1 だ．そして，Start 地点の左下の点が Goal の場合は最短経路数は 2 となる．そして，これらはどのような関係にあるだろうか．

↑

上級者向け †

上級者向けに，以下の課題がある．条件等は一緒であるが，問題の経路の形状が違う．少し厄介かもしれないが考えてみよう．

↑

レポート †

本日受けた講義および行った実習について，簡単にまとめた報告をせよ.
また，総仕上げの部分で自分で書いたプログラムを報告せよ.

もちろん各自の

所属(学部，学科)
学籍番号
学年
氏名
日時
肝心のレポート内容(得た知見，作業について気づいたこと等も)

を書くのを忘れないように.

↑

about Icons, ClipArts †

Some icons in this page are downloadable at ICONFINDER.

The "note" icon designed by Marco Martin is distributed with the LGPL licence,
the "warning" icon designed by Alexandre Moore with the GPL licence
and the "triangle" icon designed by Joseph North is distributed with the Creative Commons (Attribution-Noncommercial-Share Alike 3.0 Unported) licence.

Some clip arts used in this page are downloadable at Open Clip Art Library.
We deeply appreciate their superb works. With licence, they describe that "the actual clipart content on open clipart library is Public domain" in the web.