アルゴリズムとデータ構造 -No.2-

アルゴリズムとデータ構造の学習

この記事は以下の本で学んだ内容を自分なりにまとめたものです。 bookclub.kodansha.co.jp

前回に引き続き、今回は全探索・再帰・分割統治法についてまとめていきたいと思います。

全探索

全探索とは、解きたい問題に対して、考えられる可能性を全て調べ上げることによって解決する手法です。

線形探索法

線形探索法とは全探索の一種で、一つひとつの要素を順に調べていく手法です。例として、ある数列の中から特定の要素が含まれているかを判定する問題に対して、全ての要素を順番に確認していくプログラム等が挙げられます。このように1重のfor文によるアルゴリズムの計算量はO(N)となります。

ペアの全探索

与えられたデータの中から最適なペアを探索する問題では、2重のfor文によって解くことができ、このようなアルゴリズムの場合の計算量はO(N2)となります。

組み合わせの探索

さて、上記二つに加えてより実用的かつ応用的な組み合わせの探索では、より複雑な対象を探索するため、より高度な探索技法が必要となります。具体的には、再帰・グラフ等が挙げられます。以下で再帰について詳しくまとめていきます。

再帰

さて、複雑な問題にも対応できるより汎用的な全探索手法であり、全てのアルゴリズムの基礎として重要である再帰関数を用いる手法をまとめていきます。

再帰の重要なルール

再帰を用いる際には以下のルールを守らないといけません。

  • 再帰法は、再帰終了条件を持たなければならない。
  • 再帰法は、状態を変えながら再帰終了条件に進んでいかなければならない。
  • 再帰法は、再帰的に関数自身を呼び出さなければならない。

ベースケース

ベースケースとは、再帰関数の中で再帰呼び出しを行わずにreturnするケースのことです。この、ベースケースに対する処理はとても大事で、なぜならこの処理が行われないと再帰呼び出しを無限に繰り返してしまいます。また、実装上のポイントとして、再帰呼び出しを行った時の引数がベースケースに近づくようにするべきです。これも、ベースケースに対する処理を記述してもベースケース自体に近づくことができなければ再帰呼び出しを無限に繰り返してしまうことになるからです。

pythonによるサンプルコード

正しくベースケース処理を行えている例

本の中ではC++でサンプルコードが記載されていましたが、pythonで簡単な再帰関数を実装してみました。

def func(n):
    if n <= 0:
        return n
    return n + func(n-1)

この例は、1からnまでの自然数の和を返す再帰関数であり、nが0以下の場合には再帰呼び出しを行わずにreturnしています。これが先ほど説明したベースケースです。 例えばnが10である場合、func(10) = 10 + func(9)であり、func(9)は 9 + func(8) を戻り値として返します。このような処理をベースケース、つまりnが0まで繰り返すことで最終的に1から10までの和を返してくれます。

再帰呼び出しを無限に繰り返してしまう例

def func(n):
    if n <= 0:
        return n
    return n + func(n+1)

さて、この例ではどうでしょう？ この例では、ベースケースに対する処理を記述しているにも関わらず、再帰呼び出しを無限に繰り返してしまいます。「再帰呼び出しを行った時の引数がベースケースに近づくようにする」というポイントをしっかりと頭に入れて実装するようにしましょう。

分割統治法

さて、再帰に関する説明が一通り終わりましたが、分割統治法とは何でしょう？名前は非常に難しそうですが、この分割統治法とはこれまで学んだ再帰を用いた手法と考えられます。 本の中では、与えられた問題をいくつかの部分問題に分解し、各部分問題を再帰的に解き、それらの解を組み合わせて元の問題の解を構成するアルゴリズム技法、と説明されていました。 簡単に説明すると、再帰のテクニックを用いて、問題を分割し、それを再帰的に解き、それを統合することで解く技法です。

この分割統治法は、すでに多項式時間アルゴリズムが得られている問題に対して、より高速なアルゴリズムを設計する際に役立ちます。

さて、今回は全探索・再帰・分割統治法と第4章まで一気に進めました。再帰という概念はプログラム初学時には非常に理解しづらく、厄介なものでしたが、辛抱強く学習することにします。やはり概念だけ学習しても100%身に付く訳ではないので、どんどん実装して慣れていきたいと思います！！