使用深度/广度优先/A* 算法在图树中搜索
我有几个关于在图/树中搜索的问题：
假设我有一个空的棋盘，我想将一个棋子从 A 点移动到 B 点。
A. 当使用深度优先搜索或广度优先搜索时，我们必须使用 open和封闭名单？这是一个包含所有要检查的元素的列表，以及其他已检查的所有其他元素？没有这些列表是否可以做到这一点？那A*呢，需要吗？
B. 使用列表时，找到解后，如何得到从 A 到 B 的状态序列？我假设当您在打开和关闭列表中有项目时，您不只是具有 (x, y) 状态，而是具有由 (x, y,parent_of_this_node) 形成的“扩展状态”？
C. 状态 A 有 4 种可能的移动（右、左、上、下）。如果我先向左移动，我应该让它在下一个状态回到原来的状态吗？这是“正确”的举动吗？如果没有，我必须每次都遍历搜索树来检查我去过哪些州吗？
D. 当我在树中看到我已经去过的状态时，我是否应该忽略它，因为我知道这是一个死胡同？我想要做到这一点，我必须始终保留访问过的州列表，对吗？
E. 搜索树和图有什么区别吗？它们只是看待同一事物的不同方式吗？
I have a couple of questions about searching in graphs/trees:
Let's assume I have an empty chess board and I want to move a pawn around from point A to B.
A. When using depth first search or breadth first search must we use open and closed lists ? This is, a list that has all the elements to check, and other with all other elements that were already checked? Is it even possible to do it without having those lists? What about A*, does it need it?
B. When using lists, after having found a solution, how can you get the sequence of states from A to B? I assume when you have items in the open and closed list, instead of just having the (x, y) states, you have an "extended state" formed with (x, y, parent_of_this_node) ?
C. State A has 4 possible moves (right, left, up, down). If I do as first move left, should I let it in the next state come back to the original state? This, is, do the "right" move? If not, must I transverse the search tree every time to check which states I've been to?
D. When I see a state in the tree where I've already been, should I just ignore it, as I know it's a dead end? I guess to do this I'd have to always keep the list of visited states, right?
E. Is there any difference between search trees and graphs? Are they just different ways to look at the same thing?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
使用 DFS，您肯定需要至少存储当前路径。否则你将无法回头。如果您决定维护所有已访问（关闭）节点的列表，则可以检测并避免循环（多次扩展同一节点）。另一方面，你不再拥有 DFS 的空间效率。没有闭表的DFS只需要与搜索空间深度成正比的空间。
使用 BFS，您需要维护一个开放列表（有时称为边缘列表）。否则算法根本无法工作。当您另外维护一个封闭列表时，您将（再次）能够检测/避免循环。使用 BFS，封闭列表的额外空间可能并没有那么糟糕，因为无论如何你都必须维护边缘。边缘大小和闭合列表大小之间的关系很大程度上取决于搜索空间的结构，因此这里必须考虑这一点。例如，对于 2 的分支因子，两个列表的大小相等，并且与它的好处相比，拥有封闭列表的影响似乎并不是很糟糕。
A*，因为它可以被视为某种特殊的（知情的）类型的 BFS，需要开放列表。省略封闭列表比 BFS 更微妙；还决定更新封闭列表中的成本。根据这些决定，算法可能不再是最佳的和/或完整的，具体取决于所使用的启发式类型等。我不会在这里详细介绍。
是的，闭合列表应该形成某种逆树（指向根节点的指针），因此您可以提取解决方案路径。您通常需要关闭列表来执行此操作。对于 DFS，您当前的堆栈正是解决方案路径（此处不需要封闭列表）。另请注意，有时您对路径不感兴趣，而只对解决方案或解决方案的存在感兴趣。
阅读之前的答案并查找有关循环检测的部分。
为了避免封闭列表的循环：不要展开已经位于封闭列表内的节点。注意：随着路径成本的发挥（记住 A*），事情可能会变得更加棘手。
您可以考虑维护一个封闭列表的搜索，以避免像图搜索和没有树搜索那样的循环。
With DFS you definitely need to store at least the current path. Otherwise you would not be able to backtrack. If you decide upon maintaining a list of all visited (closed) nodes, you are able to detect and avoid cycles (expanding the same node more than once). On the other side you don't have the space efficiency of DFS anymore. DFS without closed list only needs space proportional to the depth of the search space.
With BFS you need to maintain an open list (sometimes called fringe). Otherwise the algorithm simply can't work. When you additionally maintain a closed list, you will (again) be able to detect/avoid cycles. With BFS the additional space for the closed list might be not that bad, since you have to maintain the fringe anyway. The relation between fringe size and closed list size strongly depends upon the structure of the search space, so this has to be considered here. E.g. for a branching factor of 2, both lists are equal in size and the impact of having the closed list doesn't seem very bad compared to its benefits.
A*, as it can be seen as some special (informed) type of BFS, needs the open list. Omitting the closed list is more delicate than with BFS; also deciding upon updating costs inside the closed list. Depending upon those decisions, the algorithm can stop being optimal and/or complete depending on the type of heuristic used, etc. I won't go into details here.
Yup, the closed list should form some kind of inverse tree (pointers going towards the root node), so you can extract the solution path. You usually need the closed list for doing this. For DFS, your current stack is exactly the solution path (no need for closed list here). Also note that sometimes you are not interested in the path but only in the solution or the existence of it.
Read previous answers and look for the parts which talk about the detection of cycles.
To avoid cycles with a closed list: don't expand nodes that are already inside the closed list. Note: with path-costs coming into play (remember A*), things might get more tricky.
You could consider searches that maintain a closed list to avoid cycles as graph-searches and those without one tree-searches.
A）可以避免打开/关闭列表 - 您可以尝试所有可能的路径，但这将花费很长时间。
B) 一旦达到目标，就可以使用parent_of_this_node 信息从目标“向后走”。从目标开始，获取其父级，获取父级的父级，等等，直到到达起点。
C）我认为这并不重要 - 您描述的步骤不可能导致更短的路径（除非您的步骤具有负权重，在这种情况下您不能使用 Dijkstra/A*）。在我的 A* 代码中，我会检查这种情况并忽略它，但会执行最容易编码的操作。
D）这取决于 - 我相信 Dijkstra 永远无法重新打开同一个节点（有人可以纠正我吗？）。 A* 绝对可以重新访问一个节点 - 如果您找到到同一节点的更短路径，则保留该路径，否则忽略它。
E）不确定，我自己从来没有专门为树木做过任何事情。
这里有一个关于 A* 的很好的介绍：
http://theory.stanford.edu/~amitp/GameProgramming/
其中涵盖了有关如何实现开放集、选择启发式等的许多细节。
A) It's possible to avoid the open/closed lists - you could try all possible paths, but that would take a VERY long time.
B) Once you've reached the goal, you use the parent_of_this_node information to "walk backwards" from the goal. Start with the goal, get its parent, get the parent's parent, etc. until you reach the start.
C) I think it doesn't matter - there's no way that the step you describe would result in a shorter path (unless your steps have negative weight, in which case you can't use Dijkstra/A*). In my A* code, I check for this case and ignore it, but do whatever is easiest to code up.
D) It depends - I believe Dijkstra can never reopen the same node (can someone correct me on that?). A* definitely can revisit a node - if you find a shorter path to the same node, you keep that path, otherwise you ignore it.
E) Not sure, I've never done anything specifically for trees myself.
There's a good introduction to A* here:
http://theory.stanford.edu/~amitp/GameProgramming/
that covers a lot of details about how to implement the open set, pick a heuristic, etc.
答：开放列表和封闭列表是常见的实现细节，而不是算法本身的一部分。在没有这些的情况下进行深度优先树搜索是很常见的，例如，规范的方式是树的递归遍历。
B. 通常要确保节点引用先前的节点，从而允许通过遵循反向链接来重建计划。或者，您只需将到目前为止的整个解决方案存储在每个候选中，尽管将其称为真正的节点会产生误导。
C. 我假设向左移动然后向右移动会将您带到等效的状态 - 在这种情况下，您已经探索了原始状态，它将位于关闭列表中，因此不应该被放回开放列表。您不必每次都遍历搜索树，因为您保留一个封闭列表（通常实现为 O(1) 结构），正是为了了解哪些状态已被充分检查。请注意，您不能总是假设处于相同位置与处于相同状态相同 - 对于大多数游戏寻路目的而言，是这样，但对于通用搜索而言，则不然。
D. 是的，访问过的状态列表就是您所说的关闭列表。您还需要检查打开列表以确保您不打算两次检查给定状态。您不需要搜索任何树，因为您通常将这些东西存储在线性结构中。该算法作为一个整体正在搜索一棵树（或一张图），并生成一棵树（代表状态空间的节点），但您不会在算法内的任何点显式搜索树结构。
E. 树是一种没有循环/循环的图。因此，您可以使用相同的图形搜索过程来搜索。通常会生成一个树结构来表示通过图形进行的搜索，该树结构由从每个节点到搜索中在其之前/生成该节点的节点的反向链接隐式表示。 （尽管如果你沿着在每个州保留整个计划的路线，将不会有树，只有部分解决方案的列表。）
A. Open and Closed lists are common implementation details, not part of the algorithm as such. It's common to do a depth-first tree search without either of these for example, the canonical way being a recursive traversal of the tree.
B. It is typical to ensure that nodes refer back to previous nodes allowing for a plan to be reconstructed by following the back-links. Alternatively you just store the entire solution so far in each candidate, though it would then be misleading to call it a node really.
C. I'm assuming that moving left and then moving right bring you to an equivalent state - in this case, you would have already explored the original state, it would be on the closed list, and therefore should not have been put back onto the open list. You don't traverse the search tree each time because you keep a closed list - often implemented as an O(1) structure - for precisely this purpose of knowing which states have already been fully examined. Note that you cannot always assume that being in the same position is the same as being in the same state - for most game path-finding purposes, it is, but for general purpose search, it is not.
D. Yes, the list of visited states is what you're calling the closed list. You also want to check the open list to ensure you're not planning to examine a given state twice. You don't need to search any tree as such, since you typically store these things in linear structures. The algorithm as a whole is searching a tree (or a graph), and it generates a tree (of nodes representing the state space) but you don't explicitly search through a tree structure at any point within the algorithm.
E. A tree is a type of graph with no cycles/loops in it. Therefore you use the same graph search procedure to search either. It's common to generate a tree structure that represents your search through the graph, which is represented implicitly by the backwards links from each node to the node that preceded/generated it in the search. (Although if you go down the route of holding the entire plan in each state, there will be no tree, just a list of partial solutions.)