广度优先搜索Java

我不得不在Java中进行广度优先搜索以进行分配.我有一个5x5网格的瓷砖(总共24个 - 一个瓷砖留下'空白').搜索的目的是通过向上,向下,向左或向右移动"空白"来重新排列图块,以最终将图块重新排列为正确的顺序.

为了进行此搜索,我创建了一个Arraylist'队列'.我有一个方法,在这个arraylist的索引0处获取状态,找到可以跟随的每个合法移动,然后将它们分别添加到arraylist的末尾.

从理论上讲,这一直持续到最终找到'目标国'.问题是当我运行搜索时,'队列'arraylist继续变得越来越大.今天我把它运行了几个小时仍然没有找到解决方案.

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

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

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

现在你没有明确提到你在完成它们之后将它们取出(删除它们)所以我认为你是这样,因为这是一个原因.

您是否必须专门使用广度优先搜索？如果我算得对,那就有25个!(阶乘)组合,所以这是15511210043330985984000000组合,从理论上讲,如果你正在进行广度优先搜索,你的算法不太可能完成.是不允许深度优先搜索？如果必须使用广度优先搜索,那么使其更快的唯一方法是修剪不可能导致最佳解决方案的状态.不知道你会怎么做.