我必须在 Java 中运行广度优先搜索来查找作业。我有一个 5x5 的图块网格（总共 24 个图块 - 1 个图块留为“空白”）。搜索的重点是通过向上、下、左或右移动“空白”来重新排列图块，最终将图块重新排列成正确的顺序。
为了进行此搜索，我创建了一个 Arraylist“队列”。我有一个方法，它获取此数组列表索引 0 处的状态，找到可以遵循的每个合法移动，然后将它们分别添加到数组列表的末尾。
理论上，这种情况会一直持续到最终找到“目标状态”为止。问题是，当我运行搜索时，“队列”数组列表继续变得越来越大。今天我让它运行了几个小时，但仍然没有找到解决方案。
这表明我可能以错误的方式解决了这个问题，并且有更好的方法可以在 Java 中进行广度优先搜索。我知道我的解决方案确实有效（最终），因为当我使用与目标状态没有太大不同的开始状态时，找到正确的路径并不需要太长时间。然而，我已经得到了一个可以使用的起始状态，不幸的是，它与目标状态相去甚远！
任何提示或技巧将不胜感激！
首先，我肯定会使用实际的 Queue 对象而不是 ArrayList。这是 Queue 接口上的 Java API 页面：http://java.sun.com/j2se/1.5.0/docs/api/java/util/Queue.html http://java.sun.com/j2se/1.5.0/docs/api/java/util/Queue.html- 你可以在该页面上看到 Queue 的实现有很多，如果你不知道该选择什么，一个简单的 LinkedList 就可以了。 ArrayList 会对性能造成巨大影响，因为它只能从末尾快速删除，如果从数组中的其他任何位置删除，它必须移动一切下一个（SLOW！）。你会在最后入队并在开始时出队，因此SLOW!
现在，您没有明确提到在完成项目后您正在将项目出队（删除它们），所以我认为您是这样，因为这将是原因之一。
您是否必须专门使用广度优先搜索？如果我没算错的话，有25个！ （阶乘）组合，所以这是 15511210043330985984000000 个组合，理论上这意味着如果您正在进行广度优先搜索，您的算法不太可能完成。深度优先搜索不允许吗？如果必须使用广度优先搜索，则使其速度更快的唯一方法是修剪掉不可能导致最佳解决方案的状态。不知道你会怎么做。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
