2

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

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

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

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

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

4

11 回答 11

7

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

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

您是否必须专门使用广度优先搜索？如果我计算正确，有 25 个！（阶乘）组合，所以这是 15511210043330985984000000 个组合，理论上这意味着如果您进行广度优先搜索，您的算法可能永远不会完成。不允许深度优先搜索吗？如果您必须使用广度优先搜索，那么让它更快的唯一方法是修剪掉不可能导致最佳解决方案的状态。不知道你会怎么做。

于 2009-01-28T20:47:42.817 回答
2

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

您需要的是一个辅助数据结构（最好是 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`
    ...
}

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

于 2009-01-28T20:49:55.900 回答
1

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

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

于 2009-01-28T20:42:32.670 回答
0

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

不幸的是，由于这是一项任务，毫无疑问，您应该进行蛮力搜索。

于 2009-01-28T20:39:19.870 回答
0

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

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

于 2009-01-28T20:47:07.607 回答
0

我认为这个练习的想法是让你意识到深度优先搜索是解决这个特定难题的更好方法。

于 2009-01-28T20:49:29.927 回答
0

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

于 2009-01-28T20:51:59.763 回答
0

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

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

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

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

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

于 2009-01-28T20:56:40.300 回答
0

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

于 2009-01-28T21:06:43.073 回答
0

我目前的做法如下：

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

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

于 2009-01-28T21:08:42.993 回答
0

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

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

因此，为了清楚起见，如果每个图块都分配了一个字母，并且列出了每个州的图块，我们可能会这样：

State 1: ABCDEFGHIJKLMNOP
State 2: BCADEFGHIJKLMNOP

自然状态 1 将按顺序排在第一位。因此，只需将 compareTo 机制推断为适用于磁贴到磁贴（我确定你的磁贴有 ID 或索引或其他东西不是吗？），你就会有一个排序的访问列表。然后，当您调用visited.contains(state) 时，程序将能够非常快速地计算出一个状态是否已被访问。

于 2009-01-28T21:27:40.893 回答