Dennis Soemers 的回答是正确的：您应该使用 HashSet 或类似的结构来跟踪 BFS Graph Search 中的访问状态。

但是，它并不能完全回答您的问题。你是对的，在最坏的情况下，BFS 会要求你存储 16 个！节点。即使集合中的插入和检查时间为 O(1)，您仍然需要大量的内存。

要解决此问题，请不要使用 BFS。除了最简单的问题之外，它对于所有问题都是棘手的，因为它需要时间和内存，这些时间和内存在距离最近的目标状态的距离上呈指数增长。

一种更节省内存的算法是迭代深化。它具有 BFS 的所有理想属性，但仅使用 O(n) 内存，其中 n 是到达最近解的移动次数。这可能还需要一段时间，但您会在与 CPU 相关的限制之前很久就达到内存限制。

更好的是，开发特定领域的启发式算法，并使用A* 搜索。这应该要求您只检查极少数的节点，并允许搜索在更接近线性时间的时间内完成。

您可以使用 a set（在数学意义上，即不能包含重复项的集合）来存储您已经看到的状态。您需要能够对此执行的操作是：

• 插入元素
• 测试元素是否已经存在

几乎每种编程语言都应该已经支持可以在常量中执行这两种操作的数据结构（$O(1)$） 时间。例如：

• set在 Python 中
• HashSet在爪哇

乍一看，将你见过的所有状态添加到这样的集合中似乎在内存方面会很昂贵，但与你的边界已经需要的内存相比，它并不算太糟糕；如果您的分支因子是$b$, 你的边界将增长$b - 1$您访问的每个节点的元素（删除$1$从边界节点“访问”它，添加$b$新的继任者/孩子），而您的集合只会增长$1$每个访问节点的额外节点。

在伪代码中，这样的集合（让我们命名它closed_set，以与维基百科上的伪代码保持一致，可以在广度优先搜索中使用，如下所示：

frontier = First-In-First-Out Queue
frontier.add(initial_state)

closed_set = set()

while frontier not empty:
    current = frontier.remove_next()

    if current == goal_state:
        return something

    for each child in current.generate_children()
        if child not in closed_set:    // This operation should be supported in O(1) time regardless of closed_set's current size
            frontier.add(child)

    closed_set.add(current)    // this should also run in O(1) time

（此伪代码的某些变体也可能起作用，并且根据情况或多或少地有效；例如，您还可以使用closed_set包含已将子节点添加到边界的所有节点，然后完全避免generate_children()调用如果current已经在closed_set.)

我上面描述的将是处理这个问题的标准方法。直觉上，我怀疑一个不同的“解决方案”可能是在将新的继承状态列表添加到边界之前总是随机化它们的顺序。这样，您不会避免偶尔添加您之前已经扩展到边界的状态的问题，但我确实认为它应该会显着降低陷入无限循环的风险。

请注意：我不知道对此解决方案的任何正式分析证明它总是避免无限循环。如果我尝试在脑海中“运行”这个，直觉上，我怀疑它应该可以工作，并且不需要任何额外的内存。虽然可能存在我现在没有想到的边缘情况，所以它也可能根本不起作用，上面描述的标准解决方案将是一个更安全的选择（以更多内存为代价）。

虽然给出的答案通常是正确的，但 15 谜题中的 BFS 不仅非常可行，而且是在 2005 年完成的！可以在此处找到描述该方法的论文：

http://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdf

几个关键点：

• 为此，需要外部存储器——即 BFS 使用硬盘驱动器而不是 RAM 进行存储。
• 实际上只有 15!/2 个状态，因为状态空间有两个相互不可达的组件。
• 这在滑动瓷砖拼图中很有效，因为状态空间从一个级别到另一个级别的增长非常缓慢。这意味着任何级别所需的总内存远小于状态空间的完整大小。（这与魔方之类的状态空间形成对比，其中状态空间增长得更快。）
• 因为滑动拼图是无向的，所以您只需要担心当前层或上一层中的重复项。在有向空间中，您可能会在搜索的任何先前层中生成重复项，这会使事情变得更加复杂。
• 在 Korf 的原始作品（上面链接）中，他们实际上并没有存储搜索的结果——搜索只是计算了每个级别有多少个状态。如果要存储第一个结果，则需要 WMBFS 之类的东西（http://www.cs.du.edu/~sturtevant/papers/bfs_min_write.pdf）
• 当状态存储在磁盘上时，有三种主要方法可以比较前一层的状态。
  • 首先是基于排序的。如果对两个后继文件进行排序，则可以按线性顺序扫描它们以查找重复项。
  • 第二个是基于哈希的。如果您使用散列函数将后继者分组到文件中，则可以加载小于完整状态空间的文件以检查重复项。（请注意，这里有两个散列函数——一个将状态发送到文件，一个用于区分该文件中的状态。）
  • 第三是结构化重复检测。这是一种基于散列的检测形式，但它的完成方式是可以在生成重复项时立即检查它们，而不是在它们全部生成之后。

这里还有很多要说的，但是上面的论文提供了更多的细节。

具有讽刺意味的是，答案是“使用任何你想要的系统”。hashSet 是个好主意。但是，事实证明您对内存使用的担忧是没有根据的。BFS 在这类问题上非常糟糕，它为您解决了这个问题。

考虑到您的 BFS 要求您保留一堆未处理的状态。随着您进入谜题，您处理的状态变得越来越不同，因此您可能会看到 BFS 的每一层将要查看的状态数乘以大约 3。

这意味着，当您处理 BFS 的最后一层时，您必须在内存中至少有 16!/3 个状态。无论您用来确保适合内存的任何方法都足以确保您之前访问的列表也适合内存。

正如其他人指出的那样，这不是最好的算法。使用更适合该问题的算法。