如何在遍历树时展开树？-Java 学习之路

我正在制作一个程序来解决一个3拼图（有3个块和一个空白），这是一个8拼图的较小版本 . 我试图通过将与黑色相邻的块移动到空白区域来构建树;因此每个州都可以给出2个状态（分支因子= 2） . 我正在使用广度优先搜索来解决树，但是要遍历树，首先必须进行（扩展） . 由于我无法继续永久地扩展树，我必须有一些方法将树扩展到一定的深度，然后遍历它 . 因此，当遍历到达最后一级时，将调用expand（）函数以进一步扩展它 . 可以有人给我一个明确的方法或算法来实现这个想法吗？或者有另一种方法可以解决我的问题吗？

2 回答

0

我有一个你可能觉得有用的实现 . 它是用C语言编写的，并且在我的github上有很好的文档 .

https://github.com/sitting-duck/stuff/tree/master/School%20-%20Comp%20Sci/Artificial%20Intelligence%20Spring%202015/Assn%201%20-%20Basic%20Search/Part%201/search

您可以从查看实际代码中受益，有时高级解释甚至伪代码可能会留下一些需要的东西 .

如果有任何不清楚的地方请评论，我正在尝试为我的所有代码写清楚可理解的文档 .

回复于 2024-04-24T22:16:46+08:00
1
保留所有不同董事会状态的 set . 如果两个板状态在任何位置具有不同的部分（空白计为一个部分），则它们是不同的 . 您可以通过使用一致的顺序连接所有数字来构建字符串来描述状态;大多数语言/库直接支持字符串集 .

您应该只展开（）未访问的板状态 . 无论何时第一次访问某个州，都应将其添加到"visited states" 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
```
回复于 2024-04-24T22:16:46+08:00

如何在遍历树时展开树？

2 回答

相关问题