我有几个关于在图表/树中搜索的问题：
假设我有一个空棋盘，我想将棋子从 A 点移动到 B 点。
A. 当使用深度优先搜索或广度优先搜索时，我们必须使用开放列表和封闭列表吗？这是一个包含所有要检查的元素的列表，以及已经检查过的所有其他元素的列表？甚至可以在没有这些列表的情况下做到这一点吗？A*呢，需要吗？
B. 使用列表时，找到解决方案后，如何获得从 A 到 B 的状态序列？我假设当您在打开和关闭列表中有项目时，不仅仅是具有 (x, y) 状态，而是具有由 (x, y, parent_of_this_node) 形成的“扩展状态”？
C. 状态 A 有 4 种可能的移动方式（右、左、上、下）。如果我先左移，我应该让它在下一个状态回到原来的状态吗？这，就是，做“正确”的举动吗？如果不是，我是否必须每次都遍历搜索树以检查我去过哪些州？
D. 当我在树上看到我已经去过的状态时，我是否应该忽略它，因为我知道这是一条死胡同？我想要做到这一点，我必须始终保留访问状态的列表，对吗？
E. 搜索树和图有什么区别吗？它们只是看待同一事物的不同方式吗？
A. 当使用深度优先搜索或广度优先搜索时，我们必须使用开放列表和封闭列表吗？
使用 DFS，您肯定需要至少存储当前路径。否则你将无法回溯。如果您决定维护所有访问（关闭）节点的列表，则可以检测并避免循环（多次扩展同一节点）。另一方面，您不再具有 DFS 的空间效率。没有封闭列表的 DFS 只需要与搜索空间深度成比例的空间。
使用 BFS，您需要维护一个开放列表（有时称为边缘）。否则算法根本无法工作。当您另外维护一个封闭列表时，您将（再次）能够检测/避免循环。使用 BFS，封闭列表的额外空间可能还不错，因为无论如何您都必须维护边缘。边缘大小和封闭列表大小之间的关系很大程度上取决于搜索空间的结构，因此这里必须考虑这一点。例如，对于 2 的分支因子，两个列表的大小相等，与它的好处相比，关闭列表的影响似乎不是很糟糕。
A*呢，需要吗？
A*，因为它可以被看作是一些特殊的（知情的）BFS 类型，需要打开列表。省略封闭列表比使用 BFS 更微妙；还决定更新封闭列表中的成本。根据这些决定，算法可能会停止优化和/或完成，具体取决于所使用的启发式类型等。我不会在这里详细介绍。
B.
是的，封闭列表应该形成某种逆树（指向根节点的指针），因此您可以提取解决方案路径。您通常需要关闭列表来执行此操作。对于 DFS，您当前的堆栈正是解决方案路径（此处无需封闭列表）。另请注意，有时您对路径不感兴趣，而只对解决方案或其存在感兴趣。
C。
阅读以前的答案并查找有关循环检测的部分。
D.
为了避免封闭列表的循环：不要扩展已经在封闭列表中的节点。注意：随着路径成本的出现（记住 A*），事情可能会变得更加棘手。
E. 搜索树和图有什么区别吗？
您可以考虑维护一个封闭列表的搜索，以避免循环作为图形搜索和没有一棵树的搜索。
A) 可以避免打开/关闭列表 - 您可以尝试所有可能的路径，但这需要很长时间。
B) 一旦你达到了目标，你使用 parent_of_this_node 信息从目标“倒退”。从目标开始，获取其父级，获取父级的父级等，直到到达起点。
C）我认为没关系 - 您描述的步骤不可能导致更短的路径（除非您的步骤有负权，在这种情况下您不能使用 Dijkstra/A*）。在我的 A* 代码中，我检查了这种情况并忽略它，但做最容易编码的事情。
D）这取决于 - 我相信 Dijkstra 永远无法重新打开同一个节点（有人可以纠正我吗？）。A* 绝对可以重新访问一个节点 - 如果您找到到同一节点的较短路径，则保留该路径，否则您将忽略它。
E) 不确定，我自己从未专门为树木做过任何事情。
这里有一个很好的 A* 介绍：http: //theory.stanford.edu/~amitp/GameProgramming/ 涵盖了很多关于如何实现开放集、选择启发式等的细节。
A. 打开和关闭列表是常见的实现细节，而不是算法本身的一部分。例如，在没有这些的情况下进行深度优先树搜索是很常见的，规范方式是树的递归遍历。
B. 典型的做法是确保节点回溯到先前的节点，从而允许通过遵循反向链接来重构计划。或者，您只需将到目前为止的整个解决方案存储在每个候选者中，尽管将其称为真正的节点会产生误导。
C. 我假设向左移动然后向右移动会将您带到等效状态 - 在这种情况下，您可能已经探索了原始状态，它将在关闭列表中，因此不应该被放回打开列表。您不必每次都遍历搜索树，因为您保留了一个封闭列表 - 通常实现为 O(1) 结构 - 正是为了了解哪些状态已经被完全检查过。请注意，您不能总是假设处于相同位置与处于相同状态是相同的——对于大多数游戏寻路目的而言，它是，但对于通用搜索而言，它不是。
D. 是的，访问状态列表就是您所说的封闭列表。您还需要检查打开列表以确保您不打算检查给定状态两次。您不需要搜索任何树，因为您通常将这些东西存储在线性结构中。整个算法正在搜索一棵树（或图），它生成一棵树（代表状态空间的节点），但您没有在算法中的任何点显式搜索树结构。
E. 树是一种图，其中没有循环/循环。因此，您可以使用相同的图形搜索过程进行搜索。通常会生成一个树结构来表示您在图中的搜索，该树结构由从每个节点到在搜索中之前/生成它的节点的反向链接隐式表示。（虽然如果你沿着在每个状态下持有整个计划的路线，将没有树，只有部分解决方案的列表。）