java - Java 中的广度优先搜索

Question

我必须在 Java 中运行广度优先搜索来查找作业。我有一个 5x5 的图 block 网格(总共 24 个图 block - 1 个图 block 留为“空白”)。搜索的重点是通过向上、下、左或右移动“空白”来重新排列图 block ，最终将图 block 重新排列成正确的顺序。

为了进行此搜索，我创建了一个 Arraylist“队列”。我有一个方法，它获取此数组列表索引 0 处的状态，找到可以遵循的每个合法移动，然后将它们添加到数组列表的末尾。

理论上，这种情况会一直持续到最终找到“目标状态”为止。问题是，当我运行搜索时，“队列”数组列表继续变得越来越大。今天我让它运行了几个小时，但仍然没有找到解决方案。

这表明我可能以错误的方式解决了这个问题，并且有更好的方法可以在 Java 中进行广度优先搜索。我知道我的解决方案确实有效(最终)，因为当我使用与目标状态没有太大区别的开始状态时，找到正确的路径并不需要太长时间。然而，我已经得到了一个可以使用的开始状态，不幸的是，它离目标状态还很远!!!

任何提示或技巧将不胜感激!

Answer 1

首先，我肯定会使用实际的 Queue 对象而不是 ArrayList。这是队列接口(interface)上的 Java API 页面:http://java.sun.com/j2se/1.5.0/docs/api/java/util/Queue.html - 你可以在该页面上看到 Queue 的实现有很多，如果你不知道该选择什么，一个简单的 LinkedList 就可以了。 ArrayList 会对性能造成巨大影响，因为它只能从末尾快速删除，如果从数组中的其他任何位置删除，它必须将所有内容向下移动一位(慢! )。您将在末尾入队并在开始时出队，因此慢!

现在您没有明确提到您在处理完项目后正在使项目出队(删除它们)，所以我认为您是这样，因为这就是原因之一。

您是否必须专门使用广度优先搜索？如果我没算错的话，有25个! (阶乘)组合，所以这是 15511210043330985984000000 个组合，理论上这意味着如果您正在进行广度优先搜索，您的算法不太可能完成。深度优先搜索不允许吗？如果必须使用广度优先搜索，则使其速度更快的唯一方法是修剪掉不可能导致最佳解决方案的状态。不知道你会怎么做。