深さ制限の検索ロジック - バックトラッキングを停止するにはどうすればよいですか？

Question

ロジックのアドバイスを探しています。私は開始状態から終了状態に達するために深度限定検索を実行しています。私は深さ> 0で各ノードから可能なすべての動きを拡大しています（これは問題です）。

私は以前の状態を保存しようとしましたが、展開しないための条件として含めました。しかしながら、これはまた、他の拡張枝がこの状態を通過する能力を否定する。

ロジックの観点から、この問題を回避するにはどうしたらいいですか？

@acententのコメント(here)は、それぞれの訪問された状態とそれに対応する深さを保存するconfigDepthクラスを作成するアイデアを私に与えました。次に、次の再帰で -

IF newState(depth) == state(depth-1) THEN !expand 

このソリューションに関するご意見はありますか？私は多くの盲目の路地を下り、新鮮な意見や考えが必要です。

ありがとうございます。

Answer 1

再帰は深度検索を実装するのに適しているので、到達可能な最大深度を受け取る別の再帰を作成することができます。この深さに達すると、再帰を中断します。この深度に達していない要素をまだ持っている前のノードに戻ります。

このためには、ツリーの作成から頂点の深さを知っているか、再帰を行っているときに頂点を計算するだけで済みます。