はじめに | Programming Place Plus　アルゴリズムとデータ構造編【探索アルゴリズム】　第０章

この章の概要

この章の概要です。

• イントロダクション
• 参考リンク
• 更新履歴

イントロダクション

この先の章では、探索アルゴリズムを扱います。探索アルゴリズムは、サーチアルゴリズムとも呼ばれます。

探索アルゴリズムは、条件を満たす解を探し出すアルゴリズムです。もっとも一般的なのは、配列のようなデータの集まりの中から、特定の値をもった要素を探し出すタイプです。大抵のアルゴリズムの入門書に載っている、線形探索（第１章参照）や二分探索（第４章参照）と呼ばれるアルゴリズムが、これに当たります。

二分探索のようなアルゴリズムならば、多くのプログラミング言語で、標準ライブラリなどの形で用意されています。たとえば、Ｃ言語には bsearch関数があります。

そのため、アルゴリズムの詳細を知らなくても、単純な探索アルゴリズムを利用することは簡単にできます。しかし、アルゴリズムの特性を理解していないと、性能改善ができなかったり、うまく探索できない理由が分からなかったりするでしょう。

たとえば、ソート済みでない配列に対して bsearch関数を使うことできますが、正しい結果を得られる保証がありません。これは、二分探索は、対象のデータ列が整列済みであることを前提としているためです。

探索は、非常に応用範囲の広い分野です。翻訳を行うに当たっては辞書データベースのようなものを「探索」する必要があるでしょうし、複雑にはりめぐらされたネットワーク上の最短経路を探す行為も「探索」です。将棋のようなゲームで、次に採るべき最善の手を選び出すことにも「探索」の手法が関わってきます。「配列の中から値を探す」ことは、もっとも単純な「探索」の利用方法ですが、それがすべてではありません。