このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

目次

はじめに

 アルゴリズムを設計するときによく使われる有用な方法論として、再帰法・分割統治法・動的計画法・バックトラック法がある。

再帰法

 再帰(recursion)とは、自分で自分自身を呼び出す(再帰呼び出しという)ことであり、これを適用して再帰的アルゴリズムを設計することができる。

 再帰呼び出しは、自分自身を直接的に呼び出しても、間接的に呼び出してもよい。

  • 再帰手続き
    • 再帰呼び出しを含む手続き
  • 再帰関数
    • 再帰呼び出しを含む関数

再帰とプログラミング言語

 再帰は、すべてのプログラミング言語ができるわけではない。できる言語とできない言語の両方ともが存在する。

  • 再起が可能
    • Pascal,C,Lisp,LOGOなど
  • 再帰が不可能
    • COBOL,BASIC,Fortranなど

分割統治法

 大きな問題の解法を考えるとき、一度に全体を考えることは難しい。哲学者でもあり数学者でもあったデカルトも「困難は分割せよ」といっていた。そこで、問題をいくつかの小さいな部分問題に分けて、分けられた単位を独立に解決しようとするアプローチが効果的な場合が多い。このように分割した小さな問題を解決していき、その結果を組み合わせて元の問題を解決していこうという方法を、分割統治法(divide an conquer method)という。

 分割統治法を実現する方法として、再帰がよく使われる。例えば、ソートのアルゴリズムであるクイックソートデータ探索のアルゴリズムである2分探索法などで、分割統治法は使われている。

動的計画法

 動的計画法(dynamic programming)は、ボトムアップ方式で小問題の解を順に表を使って積み上げていく問題解決方法である。ある種の最適解を求める問題に適用される方法である。

 この方法では、部分的な問題を解決してその解を表に記録していく。より大きな範囲の問題を解決するときは記録された表を参照して解を求め表に記録していき、最終的に問題全体の解を求めるという考え方である。

動的計画法と分割統治法

 小さな問題の解を求めて、それをまとめて全体問題の解にする点で分割統治法と似ている。しかし、分割統治法では小問題が互いに重複しない形で分割できるときに有効であり、考え方としてトップダウン方式である。これに対して、動的計画法は分割統治法がうまく使えないときに有効である。

バックトラック法

 バックトラック(back track)とは「同じ道を通って帰る」という意味である。バックトラック法(後戻り法)とは、問題の解を求めていく過程でその試行が不適当とわかった時点で、その試行前の状態に戻って次の試行を行う。解が得られるまで次々とこのような試行錯誤を繰り返す。

 途中まで進んだ試行の過程の記録は、後戻りする時点ですべて消去され、次の試行の実行に移っていく。この点で、試行の記録を残していく動的計画法とは大きく異なる。解に対する適切なアルゴリズムが導き出せないときに、解になりうるものを次から次へと調べていく方法である。一般的には解を得るのに大きな時間を要する。

参考文献

  • 『平成12年度 【要点・重点】短期集中速攻対策 第1種』