java - BFSまたはDFSの適用

Question

この問題を解決するには助けが必要です。2D 配列を使用して、スワップの最小数を見つけようとしました。この問題にどう対処すればよいか正確にはわかりません。BFS と DFS のどちらを使用するか?

4 桁の数字が 2 つ与えられます。最初の数字は最初の数字で、2 番目の数字は目標の数字です。可能な限り少ない操作で初期数を目標数に変換する Java プログラムを作成します。使用可能な演算は次のとおりです。 4 桁のいずれかに 1 を加算します。9 に 1 を足すと 0 になります。4 桁のうちの 1 つから 1 を引きます。0 から 1 を引くと 9 になります。隣接する 2 つの数字を入れ替えます。

例 1: イニシャル番号:1111

最終番号：9999

最小操作数:8

例 2: イニシャル番号:1234

最終番号：2144

最小操作数:2

Answer 1

BFS。

DFS が最初の解を見つけるとき、それは通常、可能な限り少ない数の移動で見つかったものではありません。また、解が近いときに、長くて無意味なパスを探索することもできます (訪問したノードを覚えていないと、無限ループに陥る可能性があります)。これらの問題は、DFS を反復的に深化することで解決できます。これは、メモリの制約がある場合に望ましいかもしれませんが、そのような小さな検索スペースでは BFS の方が簡単です。

Answer 2

最初の数値を目的の数値に変換する最短の方法が得られるため、BFS アルゴリズムを使用する必要があります。DFS は、最短経路ではなく、パスのみを探索します。場合によっては、DFS の方が BFS よりも速く解を見つけることがありますが、アルゴリズムによる保証はありません。