广度优先在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排队。我有需要在这个ArrayList的索引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.

在理论上，这将继续直到goalstate'被最终发现。问题是，当我运行搜索时，排队的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中的广度优先搜索一个更好的方法。我知道我的解决方案不会，当我使用的是不是太不同于goalstate开始状态（最终）工作，它并不需要太长的时间找到正确的道路。不过，我一直在考虑启动状态下使用，这很不幸，是无处接近goalstate！

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!!!

任何提示或提示将是非常美联社preciated！

Any hints or tips would be much appreciated!

推荐答案

首先，我肯定是用一个实际的队列对象而不是一个ArrayList。这里的队列接口上的Java API页面： HTTP ：//java.sun.com/j2se/1.5.0/docs/api/java/util/Queue.html - 你可以在该网页上看到，有排队的许多实现者，如果你不知道选什么，一个简单的LinkedList就行了。 ArrayList中会产生巨大的性能损失，因为它不仅速度快从最终删除，如果从其他地方数组中删除它移一切一个（ SLOW ！ ）。你会在年底入队，并在一开始出列，因此 SLOW ！

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!

现在你没有明确提到，你是出列的项目（消除他们），你与他们完成后，让我presume你，因为那将是一个原因。

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屋！