Java 中的广度优先搜索 [英] Breadth-First search in Java

问题描述

我必须在 Java 中运行广度优先搜索才能完成任务.我有一个 5x5 的瓷砖网格(总共 24 个 - 1 个瓷砖是空白"的).搜索的重点是通过向上、向下、向左或向右移动空白"来重新排列图块，最终将图块重新排列为正确的顺序.

I am having to run a breadth-first search in Java for an assignment. I have a 5x5 grid of tiles (24 in total - 1 tile is left 'blank'). The point of the search is to rearrange the tiles by moving the 'blank' up, down, left or right to eventually rearrange the tiles into the correct order.

为了进行这个搜索，我创建了一个 Arraylist 'queue'.我有一个方法，它获取这个数组列表索引 0 处的状态，找到每个可以跟随的合法移动，然后将它们添加到数组列表的末尾.

To do this search, I have created an Arraylist 'queue'. I have a method that takes the state at index 0 of this arraylist, finds each of the legal moves that can follow and then adds them each to the end of the arraylist.

理论上，这会一直持续到最终找到目标状态".问题是，当我运行搜索时，队列"数组列表只会越来越大.今天我让它运行了几个小时，但仍然没有找到解决方案.

In theory, this continues until the 'goalstate' is eventually found. The problem is that when I run the search, the 'queue' arraylist just continues to get bigger and bigger. Today I left it running for hours and still the solution had not been found.

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

This suggests that maybe I have gone about this solution the wrong way and there is a much better way for me to do a breadth-first search in Java. I know my solution does work (eventually) as when I use a start state that isn't too different from the goalstate, it doesn't take too long to find the right path. However, I have been given a start state to use, which unfortunately, is nowhere close to the goalstate!!!

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

Any hints or tips would be much appreciated!

推荐答案

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

First of all, I would definitely be using an actual Queue object instead of an ArrayList. Here's the Java API page on the Queue interface: http://java.sun.com/j2se/1.5.0/docs/api/java/util/Queue.html - you can see on that page that there are many implementors of Queue, if you don't know what to choose, a simple LinkedList will do. ArrayList will have a huge performance hit because it is only fast deleting from the end, if you delete from anywhere else in the array it has to shift EVERYTHING down one (SLOW!). You'd be enqueuing at the end and dequeuing at the start, therefore SLOW!

现在您没有明确提到您在处理完项目后将其出列(删除它们)，所以我认为您是这样，因为那是一个原因.

Now you didn't explicitly mention that you are dequeuing items (removing them) after you're done with them so I presume you are, because that would be one reason.

你必须专门使用广度优先搜索吗?如果我算对了，有25个！(阶乘)组合，所以这是 15511210043330985984000000 个组合，理论上这意味着如果您进行广度优先搜索，您的算法不太可能完成.不允许深度优先搜索吗?如果您必须使用广度优先搜索，那么加快搜索速度的唯一方法就是剪掉不可能得到最优解的状态.不知道你会怎么做.

Do you have to specifically use breadth-first search? If I calculated right, there are 25! (factorial) combinations, so that's 15511210043330985984000000 combinations, which theoretically means if you're doing a breadth-first search, your algorithm is not likely to ever finish. Is depth-first search not allowed? If you must use breadth-first search, the only way to make it go faster would be to prune off the states which could not possibly lead to an optimal solution. Not sure how you would go about that.

这篇关于Java 中的广度优先搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！