关于在图形/树中搜索，我有几个问题：
让我们假设我有一个空棋盘，我想从A点到B点移动一个棋子 .
A.当使用深度优先搜索或广度优先搜索时，我们必须使用打开和关闭列表吗？这是一个包含要检查的所有元素的列表，以及其他已经检查过的所有元素的列表？没有这些清单，甚至可以做到这一点吗？ A *怎么样，需要它吗？
B.使用列表时，在找到解决方案后，如何获得从A到B的状态序列？我假设你在开放和关闭列表中有项目，而不是只有（x，y）状态，你有一个由（x，y，parent_of_this_node）形成的“扩展状态”？
C.状态A有4种可能的移动（向右，向左，向上，向下） . 如果我第一次向左移动，我应该让它在下一个状态回到原始状态吗？这是，做“正确”的举动？如果没有，我每次都必须横穿搜索树来检查我去过哪些州吗？
D.当我在树上看到一个我已经去过的州时，我应该忽略它，因为我知道这是一个死胡同？我想这样做我必须始终保持访问状态列表，对吗？
E.搜索树和图表之间有什么区别吗？他们只是以不同的方式看待同一件事吗？
3 回答
使用DFS，您肯定需要至少存储当前路径 . 否则你将无法回溯 . 如果您决定维护所有访问（关闭）节点的列表，则可以检测并避免循环（多次扩展同一节点） . 另一方面，你不再具有DFS的空间效率 . 没有封闭列表的DFS只需要与搜索空间深度成比例的空间 .
使用BFS，您需要维护一个开放列表（有时称为边缘） . 否则算法根本无法工作 . 当您另外维护一个关闭列表时，您将（再次）能够检测/避免周期 . 使用BFS，关闭列表的额外空间可能并不坏，因为无论如何你必须保持边缘 . 条纹大小和封闭列表大小之间的关系很大程度上取决于搜索空间的结构，因此这里必须考虑这一点 . 例如 . 对于分支因子为2，两个列表的大小相等，并且具有封闭列表的影响与其优点相比似乎并不十分差 .
A *，因为它可以被视为一些特殊（知情）类型的BFS，需要打开列表 . 省略封闭式清单比BFS更为精细;还决定更新封闭清单内的成本 . 根据这些决定，算法可能会停止最佳和/或完整，具体取决于所使用的启发式的类型等 . 我在此不再详述 .
是的，封闭列表应该形成某种反向树（指向根节点的指针），因此您可以提取解决方案路径 . 您通常需要关闭列表才能执行此操作 . 对于DFS，您当前的堆栈正是解决方案路径（此处不需要关闭列表） . 另请注意，有时您对路径不感兴趣，但仅对解决方案或其存在感兴趣 .
阅读以前的答案，并查找谈论循环检测的部分 .
要避免具有已关闭列表的循环：请勿展开已在关闭列表中的节点 . 注意：路径成本开始发挥作用（记住A *），事情可能会变得更加棘手 .
您可以考虑维护已关闭列表的搜索，以避免作为图搜索的循环和没有一个树搜索的循环 .
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.树是一种图形，其中没有循环/循环 . 因此，您使用相同的图搜索过程来搜索 . 通常生成表示您通过图形搜索的树结构，该结构由从每个节点到搜索之前/之后生成的节点的向后链接隐式表示 . （虽然如果沿着在每个州保留整个计划的路线，将没有树，只有部分解决方案列表 . ）