全2512文字
実用的なソフトウエアを開発するにはアルゴリズムの知識は欠かせない。基礎から機械学習まで、厳選した10個のアルゴリズムをPythonによる実装とともに解説する。
［5 古典的なAI］ 深さ優先探索
「深さ優先探索」（depth-first search、dfs）は、「グラフ」と呼ばれるデータ構造を探索するためのアルゴリズムです。1950年代後半に起きた第1次AIブームでは、深さ優先探索がAIの中心的なアルゴリズムの一つでした。深さ優先探索は、現在では“古典的なAIのアルゴリズム”と言えます。
ここでは迷路（これもグラフの一種と見なせます）の探索を通して、深さ優先探索を説明しましょう。
図1の迷路の探索を考えます。Sはスタート地点で、Gはゴールです。求めたいのはスタートからゴールへの経路です。人間であれば見た瞬間にわかるわけですが、コンピュータに探索させる場合は、何らかのルールをコンピュータに与える必要があります。今回は、深さ優先探索のアルゴリズムが、与えるルールになります。
図1●迷路。深さ優先探索でゴールを探索する
[画像のクリックで拡大表示]
深さ優先探索とは、大雑把に言うと、一つの方向へ先へ先へと探索を進め、行き止まり（袋小路）になったら直前の分岐に戻って、まだ探索していない道へ進む、というアルゴリズムです。この動作を続けると、必ずゴールに到達します。ポイントとなるのは「直前の分岐に戻る」動きで、これは「バックトラック」と呼ばれます。また、探索済みの道をマークする処理も重要です。
