java - BFS或DFS的应用

Question

我需要帮助来解决这个问题，我尝试使用二维数组，然后找到最少的交换次数。不确定如何解决这个问题。是使用 BFS 还是 DFS？

给你两个四位数的数字。第一个数字是初始数字，第二个数字是目标数字。编写一个 java 程序，使用尽可能少的操作将初始数字转换为目标数字。可用的操作如下： 四位数字之一加 1。将 1 加到 9 得到 0。从四个数字之一中减去 1。从 0 中减去 1 得到 9。交换两个相邻的数字

例如 1：初始编号：1111

最终编号：9999

最少操作次数：8

例如 2：初始编号：1234

最终编号：2144

最少操作次数：2

Answer 1

您应该使用 BFS 算法，因为它将为您提供将第一个数字转换为目标数字的最短方法。DFS 仅探索路径，而不是最短路径。在某些情况下，DFS 可能比 BFS 更快地找到解决方案，但没有算法保证。

Answer 2

BFS。

当 DFS 找到第一个解决方案时，它通常不是在尽可能少的移动次数中找到的。当解决方案接近时，它还可以探索漫长而无意义的路径（如果您不记得访问过的节点，它可能会陷入无限循环）。这些问题可以通过迭代深化 DFS 来解决，如果存在内存限制，这可能是可取的，但对于如此小的搜索空间，BFS 更简单。