language-agnostic - 使用深度/广度优先/A*算法在图树中搜索

Question

我有几个关于在图形/树中搜索的问题:

假设我有一个空棋盘，我想将一个棋子从 A 点移动到 B 点。

A. 当使用深度优先搜索或广度优先搜索时，我们必须使用开放列表和封闭列表吗？这是一个包含所有要检查的元素的列表，以及其他所有已经检查过的元素的列表？甚至可以在没有这些列表的情况下做到这一点吗？ A* 怎么样，需要吗？

B. 使用列表时，在找到解决方案后，如何获得从 A 到 B 的状态序列？我假设当你在打开和关闭列表中有项目时，而不是只有 (x, y) 状态，你有一个由 (x, y, parent_of_this_node) 形成的“扩展状态”？

C. 状态 A 有 4 种可能的移动(向右、向左、向上、向下)。如果我做第一个向左移动，我应该让它在下一个状态回到原来的状态吗？这，就是，做“正确”的举动吗？如果没有，我是否必须每次都遍历搜索树以检查我去过哪些州？

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

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

Answer 1

A. When using depth first search or breadth first search must we use open and closed lists ?

使用 DFS，您肯定需要至少存储当前路径。否则，您将无法回溯。如果您决定维护所有访问(关闭)节点的列表，您就能够检测并避免循环(多次扩展同一节点)。另一方面，您不再具有 DFS 的空间效率。没有封闭列表的 DFS 只需要与搜索空间的深度成正比的空间。

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

What about A*, does it need it?

A*，因为它可以被看作是某种特殊(通知)类型的 BFS，需要打开列表。省略封闭列表比 BFS 更微妙；还决定更新封闭列表中的成本。根据这些决定，算法可能会停止优化和/或完成，具体取决于所使用的启发式类型等。我不会在这里详细介绍。

B.

是的，封闭列表应该形成某种逆向树(指向根节点的指针)，因此您可以提取解决方案路径。您通常需要关闭列表来执行此操作。对于 DFS，您当前的堆栈正是解决方案路径(此处无需封闭列表)。另请注意，有时您对路径不感兴趣，而只对解决方案或它的存在感兴趣。

C.

阅读以前的答案并查找讨论循环检测的部分。

D.

为了避免封闭列表的循环:不要扩展已经在封闭列表内的节点。注意:随着路径成本的发挥(记住 A*)，事情可能会变得更加棘手。

E. Is there any difference between search trees and graphs?

您可以考虑维护封闭列表的搜索，以避免循环作为图搜索和没有单树搜索的搜索。