0

我正在制作一个程序来解决 3-puzzle(with 3 blocks and a blank) ，它是 8-puzzle 的较小版本。我试图通过将与黑色相邻的块移动到空白空间来构建一棵树；因此每个状态都可以给出 2 个状态（分支因子 = 2）。我正在使用广度优先搜索来解决树，但要遍历树，首先必须制作（扩展）它。由于我不能永远继续扩展树，我必须有一些方法将树扩展到一定深度然后遍历它。所以当遍历到最后一层时，会调用expand()函数进一步展开。谁能给我一个清晰的方法或算法来实现这个想法？还是有其他方法可以解决我的问题？

4

1 回答 1

1

保留set所有不同的董事会状态。如果两个棋盘状态在任何位置有不同的棋子（空白算作棋子），则它们是不同的。您可以通过使用一致的顺序连接所有数字来构建一个字符串来描述状态；大多数语言/库直接支持字符串集。

您应该只 expand() 未访问的棋盘状态。每当您第一次访问某个州时，都应将其添加到“已访问状态”set中。在扩展任何状态之前，请检查它是否已经存在。

完整的算法（对于一般的广度优先，无重复搜索）是：

place initial state into "pending" (a queue)
place initial state into "visited" (a set)
while "pending" is not empty,
   extract its first state, called "next"
   if it is not present in "visited",
      if it is the goal, report success, ending the algorithm
      otherwise, add all its children at the end of "pending"    
if you reach this point, there is no way to reach a goal state from a start state
于 2012-09-10T10:42:40.063 回答