$shibayu36->blog;

クラスター株式会社のソフトウェアエンジニアです。エンジニアリングや読書などについて書いています。

力づく法・分割統治法・動的計画法 - アルゴリズム学習(その5)

tech algorithm

アルゴリズムの設計手法として、力ずく法・分割統治法・動的計画法というような考え方があった。新しいアルゴリズムを学ぶ時、どの設計手法でやっているのだろうかと意識しておくと、頭に入りやすい気がした。そこで、自分の頭を整理するためにメモを書いておく。自分用メモなので、情報の正確さについては保証がない。

力づく法

  • 全探索する方法
  • アルゴリズムの考え方としては単純なことが多いが、かなり遅いものになることが多い
  • 例えば、Nクイーンなら、N個の置き方を全通り作って、それぞれが条件をみたすか確認し、条件を満たしたら返すようなもの。Nの二乗のなかから、N個の組み合わせを作って試すので、計算が膨大になる
  • 例えば文字列マッチなら、1文字ずつずらしながら、マッチさせたいパターンとテキストの文字を比較していくようなもの

分割統治法

  • Wikipediaによると、そのままでは解決できない大きな問題を小さな問題に分割し、その全てを解決することで、最終的に最初の問題全体を解決するという手法らしい
  • クイックソートはまさにそのような解決方法。2つのグループにわけて、さらにソートを実行し、最終的に全体が解決されるという構造になっている
  • 2分探索も同じような考え方である
  • 分割統治法という設計手法があるので、計算量でlogが出てくることが多い

参考

動的計画法

  • 分割統治法を利用すると、同じ小問題を何度も解いてしまっていて、効率が悪い時がある
  • そこで大きい問題を小さい問題に分割した後、小さい問題から解いていきながら、その結果をメモしておくことで、同じ小問題を何度も計算しないようにする方法を動的計画法と呼ぶ
  • フィボナッチ数列の計算の場合、普通の再帰、つまりfib(n) = fib(n-1) + fib(n-2)で計算していく方法がある。しかしこれでfib(6)を計算すると、fib(3)の結果を何度も計算することになる。これでは効率が悪い
  • 逆にfib(1)から計算して、その結果を配列resultsに記録していき、fib(n)の計算は配列に入っている結果を使って、results[n-1] + results[n-2]としていけば、何度も同じような計算をしなくても良い。このようなものが動的計画法と呼べる

参考

まとめ

今回はアルゴリズムの設計の考え方についてメモしてみた。このような種類の考え方があるということを知っておくと、アルゴリズムを勉強するときや、自分で難しい問題を解く時に参考になると思った。

これまでの学習