我有一些关于在图/树中搜索的问题：

假设我有一个空的棋盘，我想把一个卒从 A 点移动到 B 点。

A. 当使用深度优先搜索或广度优先搜索时，我们必须使用开放列表和封闭列表吗？ 也就是说，一个列表包含所有要检查的元素，另一个列表包含所有已经检查过的元素？ 没有这些列表是否可能实现？ A* 算法呢，它需要这些列表吗？

B. 当使用列表时，在找到解决方案后，如何从 A 到 B 获取状态序列？ 我假设当开放列表和封闭列表中的项目，不仅仅只是 (x, y) 状态，而是有由 (x, y, 父节点) 组成的 “扩展状态” ？

C. 状态 A 有 4 种可能的移动（右、左、上、下）。 如果我首先向左移动，我是否应该让它在下一个状态中返回到原始状态？ 也就是说，进行“右”移动？ 如果不这样做，我是否必须每次遍历搜索树来检查我去过哪些状态？

D. 当我在树中看到一个已经去过的状态时，我应该直接忽略它吗，因为我知道这是一个死胡同？ 我想为了做到这一点，我必须始终保留已访问状态的列表，对吗？

E. 搜索树和图之间有什么区别吗？ 它们只是看待同一件事的不同方式吗？

回答：

A. 当使用深度优先搜索或广度优先搜索时，我们必须使用开放列表和封闭列表吗？

对于深度优先搜索（DFS），你肯定需要存储至少当前路径。 否则你将无法回溯。 如果你决定维护一个所有已访问（封闭）节点的列表，你就可以检测并避免循环（多次扩展同一个节点）。 另一方面，你不再具有深度优先搜索的空间效率。 没有封闭列表的深度优先搜索只需要与搜索空间的深度成比例的空间。

对于广度优先搜索（BFS），你需要维护一个开放列表（有时称为边缘列表）。 否则该算法根本无法工作。 当你额外维护一个封闭列表时，你将（再次）能够检测/避免循环。 对于广度优先搜索，封闭列表的额外空间可能不是那么糟糕，因为你无论如何都必须维护边缘列表。 边缘列表大小和封闭列表大小之间的关系很大程度上取决于搜索空间的结构，因此必须在此处加以考虑。 例如，对于分支因子为 2，两个列表的大小相等，并且与它的好处相比，拥有封闭列表的影响似乎并不是很糟糕。

A* 算法呢，它需要这些列表吗？

A* 算法，因为它被看作是一种特殊的（知情）广度优先搜索，需要开放列表。 省略封闭列表比广度优先搜索更棘手； 还要决定是否更新封闭列表中的成本。 根据这些决定，该算法可能会停止保持最优性和/或完整性，具体取决于所使用的启发式类型等等。 我不会在这里深入细节。

B.

是的，封闭列表应该形成某种反向树（指针指向根节点），这样你就可以提取解决方案路径。 通常你需要封闭列表才能做到这一点。 对于深度优先搜索，你当前的堆栈正是解决方案路径（这里不需要封闭列表）。 还要注意，有时你只对解决方案或其存在感兴趣，而对路径不感兴趣。

C.

阅读前面的答案，并查找其中谈到检测循环的部分。

D.

为了使用封闭列表避免循环：不要扩展已经存在于封闭列表中的节点。 注意：当路径成本起作用时（记住 A*），事情可能会变得更加棘手。

E. 搜索树和图之间有什么区别吗？

你可以将维护封闭列表以避免循环的搜索视为图搜索，而将没有封闭列表的搜索视为树搜索。