アルゴリズムとデータ構造編【探索】 第0章 はじめに

先頭へ戻る

このエントリーをはてなブックマークに追加

この章の概要

この章の概要です。

イントロダクション

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

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

二分探索のようなアルゴリズムならば、多くのプログラミング言語で、標準ライブラリ等の形で用意されています。 例えば、C言語なら bsearch関数(⇒リファレンス)を使えます。
そのため、アルゴリズムの詳細を知らなくても、単純な探索アルゴリズムを利用することは簡単にできます。 しかし、アルゴリズムの特性を理解していないと、性能改善ができなかったり、うまく探索できない理由が分からなかったりするでしょう。

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


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


参考リンク

更新履歴

'2011/10/23 新規作成。



次の章へ

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ