フィボナッチ探索は、与えられたリストから要素を見つけるために使用される、もう一つの分割統治アルゴリズムです。
この記事では、フィボナッチ探索がどのように動作するか、バイナリサーチとどう違うか、そしてpythonで実装します。
この記事もチェック：Pythonでグラフの深さ優先探索アルゴリズムを実装する方法を解説する
前提条件
フィボナッチ探索を始める前に、まず理解しておかなければならないことが2つあります。
1. バイナリサーチ
バイナリサーチは分割統治アルゴリズムであり、答えを見つけるためにリストを分割することを意味します。
このアルゴリズムを実行するために、与えられたリストはソートされている必要があります。
リストはソートされているので、ターゲットは真ん中の要素から相対的にどこにあるかがわかります。
リストの真ん中でターゲットを見つけるか、真ん中の要素より小さいか大きいかによって、真ん中から片方を排除します。
片方を排除したら、もう片方でこの処理を繰り返す。
このように、1回の反復でリストの半分を削っていくので、n個の要素を見つけるにはlog2n回の反復で済みます。
2. フィボナッチ数
フィボナッチ数とは、フィボナッチ級数を構成する数です。
そこで、まずフィボナッチ級数を定義してみましょう。
級数は再帰的に次のように定義できる。
F(n) = F(n-1) + F(n-2)
F(1) = 1
F(0) = 0
|
フィボナッチ数を得るには、指数や黄金比を含む公式で直接得る方法もありますが、この方法は、級数の捉え方の意味するところです。
上の定義で、F(n)は「n番目のフィボナッチ数」という意味です。
つまり、0番目のフィボナッチ数は0、1番目のフィボナッチ数は1、2番目のフィボナッチ数は1番目と0番目のフィボナッチ数の和、3番目のフィボナッチ数は2番目と1番目のフィボナッチ数の和、、、となります。
最後に、n番目のフィボナッチ数は、その前の2つのフィボナッチ数の和、つまり、(n-1)番目のフィボナッチ数と(n-2)番目のフィボナッチ数の和となるのです。
以下は、最初の10個のフィボナッチ数の計算です。
F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = 3 + 2 = 5
F(6) = 5 + 3 = 8
F(7) = 8 + 5 = 13
F(8) = 21
F(9) = 34
F(10) = 55
... |
つまり、0番目から始まるフィボナッチ級数は
F = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
フィボナッチ探索をPythonで実装する
バイナリサーチと同様に、フィボナッチサーチも分割統治アルゴリズムであり、ソートされたリストが必要です。
また、リストを2つに分割し、2つの部分の中心にある項目と対象を比較し、その比較結果に基づいて片方を消去します。
では、具体的にバイナリサーチとどう違うのでしょうか。
フィボナッチ探索では、フィボナッチ数を使ってリストを2分割するので、リストを長さの異なる2つの部分に分割することになります。
また、そのために割り算を行うのではなく、CPUへの負荷が少ない足し算を行います。
では、詳細を見ていきましょう。
まず、与えられたリストの長さが必要です。
次に、リストの大きさ以上の最小のフィボナッチ数を見つけます。
つまり、リストのサイズが100であれば、100より大きい最小のフィボナッチ数は144です。
これをフィボナッチ数n番目とします。
上の例では、144は12番目のフィボナッチ数です。
この後、その数からフィボナッチ級数を2回遡ることになる。
基本的には、(n-2)番目のフィボナッチ数を求めます。
つまり、上の例では、12番目のフィボナッチ数は144なので、10番目のフィボナッチ数は55となります。
これをインデックスとして、リストを2つに分割するのです。
つまり、リストのこのインデックスを見て、リストが昇順にソートされていると仮定して、このインデックスの項目がターゲットより小さければ左側を、そうでなければ右側を排除します。
これを、探している項目が見つかるまで、つまり、計算したインデックスの項目がターゲットと一致するまで続けます。
では、このアルゴリズムのコードを見てみましょう。
def fibonacci_search(lst, target):
size = len(lst)
start = -1
f0 = 0
f1 = 1
f2 = 1
while(f2 < size):
f0 = f1
f1 = f2
f2 = f1 + f0
while(f2 > 1):
index = min(start + f0, size - 1)
if lst[index] < target:
f2 = f1
f1 = f0
f0 = f2 - f1
start = index
elif lst[index] > target:
f2 = f0
f1 = f1 - f0
f0 = f2 - f1
else:
return index
if (f1) and (lst[size - 1] == target):
return size - 1
return None
|
では、実際に実行して出力を見てみましょう。
この記事もチェック：Pythonによるバブルソートの昇順、降順の実装方法とコードを解説する
まとめ
この記事では、フィボナッチ数とは何か、フィボナッチ探索アルゴリズムでどのように使用されるか、アルゴリズム自体がどのように動作するか、そしてそのアルゴリズムをpythonで実装しました。
次のチュートリアルでお会いしましょう。