ループで探索処理を続行します。経路をのばす処理はバックトラックのプログラムとほぼ同じです。キューに追加するところに注意してください。それでは実行してみましょう。#t結果を見ればおわかりのように、最初に見つかる経路が最短で、最後に見つかる経路が最長となります。最短手数を求めるのに適したアルゴリズムですが、生成する局面数が多くなると大量のメモリを必要とします。このため、メモリが不足するときには使うことができないという欠点があります。逆に深さ優先探索の場合、メモリの消費量は少ないのですが、最初に見つかる解が最短手数とは限らないという問題点があります。それでは、大量のメモリを使わずに最短手数を求める方法はないのでしょうか。実は、とても簡単な方法があるのです。それは、深さ優先探索の「深さ」に上限値を設定し、解が見つかるまで上限値を段階的に増やしていくという方法です。手ずつ増やしていくわけです。deeping)」といいます。反復深化は最短手数を求めることができるアルゴリズムですが、幅優先探索と違って局面を保存する必要がないため、必要となるメモリは深さ優先探索と同程度で済みます。プログラムも深さ優先探索と同じくらい簡単に作成することができます。同じ探索を何度も繰り返すため実行時間が増大する、という欠点があります。ようするに、使用するメモリは少ないが実行時間が長くなるアルゴリズムなのです。経路を反復深化で求めてみましょう。反復深化のプログラムはとても簡単です。手ずつ増やしてその関数を呼び出せばいいのです。プログラムは次のようになります。