Java 中的广度优先搜索

Breadth-First search in Java

提问by Tray

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.

我必须在 Java 中运行广度优先搜索以进行分配。我有一个 5x5 的瓷砖网格（总共 24 个 - 1 个瓷砖是“空白”的）。搜索的重点是通过向上、向下、向左或向右移动“空白”来重新排列图块，最终将图块重新排列为正确的顺序。

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.

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

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.

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

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

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

Any hints or tips would be much appreciated!

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

回答by Ray Hidayat

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 EVERYTHINGdown one (SLOW!). You'd be enqueuing at the end and dequeuing at the start, therefore SLOW!

首先，我肯定会使用实际的 Queue 对象而不是 ArrayList。这是队列接口上的 Java API 页面：http: //java.sun.com/j2se/1.5.0/docs/api/java/util/Queue.html- 您可以在该页面上看到有许多实现者队列，如果你不知道该选择什么，一个简单的 LinkedList 就可以了。ArrayList中会产生巨大的性能损失，因为它只是从快结束时删除，如果你从其他地方有转移阵列中删除一切下移（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.

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

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.

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

回答by Daniel Spiewak

Breadth-first search without duplicate checking is definately going to give you results like the ones you are seeing. In fact, it's fairly trivial to prove that the algorithm as you have implemented it will neverterminate. Feel free to wait for it though... :-)

没有重复检查的广度优先搜索肯定会给您提供您所看到的结果。事实上，证明您实现的算法永远不会终止是相当简单的。不过，请随意等待... :-)

What you need is an ancillary data structure (preferably a Set) to store pre-examined positions. Thus, part of your code will look like the following:

您需要的是一个辅助数据结构（最好是 a Set）来存储预先检查的位置。因此，您的部分代码将如下所示：

public Queue<Position> queue = new LinkedList<Position>();
public Set<Position> done = new HashSet<Position>();

public Position[] findPath(Position start, Position goal) {
    if (done.contains(start)) return null;

    done.add(start);
    // add subsequent states to `queue`
    ...
}

As mentioned in other answers, depth-first search is a muchbetter solution in this case. Assuming that the goalposition is reachable, it should yield exponentially superior search times for all but the most contrived of positions.

正如在其他的答案中提到，深度优先搜索是一个多在这种情况下更好的解决方案。假设该goal位置是可到达的，它应该为除了最人为设计的位置之外的所有位置产生指数级的优越搜索时间。

回答by basszero

At first glance, it would seem that you may end up with duplicate states and hence cycles in your graph. You may need to look into some way to identify if two states are the same and if you've already visited one before.

乍一看，似乎您最终可能会出现重复的状态，从而导致图中出现循环。您可能需要寻找某种方法来确定两个状态是否相同，以及您之前是否已经访问过一个状态。

EDIT: Putting aside the algorithmic restrictions, perhaps there is a formula to move block X in position Y to position Z without distrubing any other tiles. Given this you can just compute all of the transformations required. I'm just musing about the problem now.

编辑：抛开算法限制，也许有一个公式可以将位置 Y 的块 X 移动到位置 Z 而不干扰任何其他瓷砖。鉴于此，您只需计算所需的所有转换即可。我现在只是在思考这个问题。

回答by Tray

I have done the 'brute search' - the problem is, with a 5x5 grid there are SO many combinations that it just takes forever. I left it running whilst I went to work...8 hours later, it was still going, the queue arraylist size was up to 100k different states and my pc sounded like it was going to overheat and explode lol

我已经完成了“蛮力搜索” - 问题是，对于 5x5 的网格，有太多的组合需要花费很长时间。我去上班时让它一直运行...... 8 小时后，它仍在运行，队列数组列表大小高达 100k 不同状态，我的电脑听起来像是要过热爆炸，哈哈

I know my code works (eventually, like I said) so I would be happy to submit it. I'm just worried about the time it takes to find a solution and wondered whether there is a better approach I could take, other than using an arraylist to create a queue.

我知道我的代码有效（最终，就像我说的那样）所以我很乐意提交它。我只是担心找到解决方案所需的时间，并想知道除了使用数组列表创建队列之外，是否还有更好的方法。

回答by plinth

While it's probably not within the scope of your assignment, there is an algorithm for solving this type of puzzle. Basically, there are a two moves that work for every line except the last two, and a two moves that work for the last two lines. Using this approach gets you a much faster solution.

虽然它可能不在您的作业范围内，但有一种算法可以解决此类难题。基本上，除了最后两行外，每一行都有两个移动，最后两行有两个移动。使用这种方法可以获得更快的解决方案。

Unfortunately, since this is an assignment, you are no doubt expected to do brute force searching.

不幸的是，由于这是一项任务，您无疑需要进行蛮力搜索。

回答by Tray

I have to actually write code for both. So I am about to move onto depth first search. Before I did it, I just wanted to make sure I wasn't going to be laughed out of my course for producing code that took forever and a day to find a solution!!!!!!!

我必须实际为两者编写代码。所以我即将进入深度优先搜索。在我这样做之前，我只是想确保我不会因为我的代码而被笑出我的课程，这些代码需要永远一天的时间才能找到解决方案！！！！！！！！！

回答by Paul Brinkley

You didn't say whether you check this or not, but it sounds like you're not pruning cycles.

你没有说你是否检查这个，但听起来你不是修剪周期。

First, suppose that instead of representing moves as moving the blank square in some direction, you instead supplied the tile number that was moved. (It's guaranteed to be unique.) Now suppose a legal move is "3" - moving tile #3 into the empty space. The result is a new board layout. A legal move from there is to move tile 3 again, and now you're back where you started.

首先，假设不是将移动表示为向某个方向移动空白方块，而是提供了移动的图块编号。（它保证是唯一的。）现在假设合法移动是“3” - 将第 3 块瓷砖移动到空白区域。结果是一个新的电路板布局。从那里开始的合法移动是再次移动图块 3，现在您又回到了起点。

Slider puzzles can easily have larger cycles. If there's a 2x2 grid with 1-2-3-empty in it, then a valid sequence of moves is 1-2-3-1-2-3-1-2-3-1-2-3 - which sends you back to the beginning.

滑块拼图很容易有更大的周期。如果有一个包含 1-2-3-empty 的 2x2 网格，那么有效的移动序列是 1-2-3-1-2-3-1-2-3-1-2-3 - 它发送给你回到起点。

If your search does not check for and prune duplicate boards, the breadth-first search will still terminate (provided there are no bugs, and there's not a parity error(?) making your board unsolvable) - a correct solution exists that is N moves in length, and you'll take finite time to process every sequence of K moves, so you'll eventually get to N, and your solution. However, the time for each move length increases exponentially (up to 4 moves from each board). You're probably thrashing on memory.

如果您的搜索没有检查和修剪重复的棋盘，广度优先搜索仍将终止（假设没有错误，并且没有奇偶校验错误（？）使您的棋盘无法解决） - 存在正确的解决方案，即 N 次移动在长度上，您将花费有限的时间来处理 K 次移动的每个序列，因此您最终会得到 N，以及您的解决方案。但是，每个移动长度的时间呈指数增长（每块棋盘最多移动 4 步）。你可能在内存中挣扎。

Unfortunately, the brute force approach to checking for duplicate board states is to store every board as you arrive at it, which will also use up memory fast - though perhaps not as fast as your current method. It might be satisfactory, in fact, for a mere 5x5 board.

不幸的是，检查重复板状态的蛮力方法是在您到达时存储每个板，这也会快速耗尽内存 - 尽管可能不如您当前的方法快。事实上，对于仅仅 5x5 的板子，它可能是令人满意的。

回答by Apocalisp

Perhaps a goal-directed depth-first search. Start by solving 9 edge tiles, reducing the puzzle to a 4x4 grid. Then solve the 7 edge tiles of that, reducing to a 3x3 grid which should be easy pickings for your original algorithm.

也许是目标导向的深度优先搜索。首先解决 9 个边缘瓷砖，将拼图缩小为 4x4 网格。然后解决其中的 7 个边缘图块，将其缩小为 3x3 网格，这对于您的原始算法来说应该是很容易选择的。

回答by Tray

The way I am doing it at the moment is as follows:

我目前的做法如下：

• 2 Arraylists; Queue and Visited
• The start state is automatically added to the Visited arraylist
• All possible legal moves from the start start are obtained and each compared to those stored in the Visited arraylist.
• Those legal moves that do not create a 'visited' state are added to the Queue.
• The state held at index 0 of the arraylist is taken, and the process repeats itself.

• 2个数组列表；排队和参观
• 启动状态会自动添加到Visited arraylist
• 获得从开始开始的所有可能的合法移动，并将每个移动与存储在访问数组列表中的移动进行比较。
• 那些不会创建“已访问”状态的合法移动被添加到队列中。
• 保持在数组列表索引 0 处的状态被采用，并且该过程重复自身。

I see from previous answers that I should probably change the arraylists into a different collection. But I am checking that states are not duplicated.

我从以前的答案中看到，我可能应该将数组列表更改为不同的集合。但我正在检查状态是否重复。

回答by Ray Hidayat

Okay the next thing is, if I were to do your visited list, I would use a Set (probably a TreeSet) which would automatically sort the states so that searching to see whether a new state has been visited before would be a lot faster.

好的，接下来是，如果我要做你的访问列表，我会使用一个 Set（可能是一个TreeSet），它会自动对状态进行排序，以便搜索之前是否访问过新状态会快得多。

All you'd need to do is make your state class implement the Comparableinterface. (hopefully you already had expected something like this and made it a class). If you don't know already, using the compareTo method of this interface, you define the sorting order of the objects, which of course would be used by the visited Set. From there you could set up the compareTo method to work like a string comparison except with your tiles.

您需要做的就是让您的状态类实现Comparable接口。（希望你已经预料到了这样的事情，并把它变成了一个类）。如果你还不知道，使用这个接口的 compareTo 方法，你定义对象的排序顺序，当然被访问的 Set 会使用它。从那里您可以将 compareTo 方法设置为像字符串比较一样工作，除了您的图块。

So just to make it clear, if each tile were assigned a letter, and the tiles in each state were listed out, we might have this:

所以只是为了说清楚，如果每个瓦片都分配了一个字母，并且列出了每个州的瓦片，我们可能会有这样的：

State 1: ABCDEFGHIJKLMNOP
State 2: BCADEFGHIJKLMNOP

Naturally state 1 would come first in the order. So just extrapolate that compareTo mechanism to work for tiles to tiles (I'm sure your tiles have IDs or indexes or something don't they?) and you'll have a sorted visited list. Then when you called visited.contains(state) the program will be able to calculate very quickly whether a state has been visited or not.

自然状态 1 将按顺序排在最前面。因此，只需将 compareTo 机制外推到图块之间（我确定您的图块具有 ID 或索引或其他东西，不是吗？），您将拥有一个已排序的访问列表。然后当您调用visited.contains(state) 时，程序将能够非常快速地计算出某个状态是否已被访问过。