algorithm - 如何表示要用于 DFS/BFS 的数据

Question

我被分配了一个问题，需要使用各种搜索技术来解决。问题与 Escape From Zurg 非常相似问题或 Bridge and Torch问题。我的问题是我不知道如何将数据表示为树。

这是我对如何做到这一点的猜测，但它对搜索没有多大意义。

另一种方法是使用按步行时间排序的二叉树。但是，我仍然不确定我是否正确地解决了这个问题，因为搜索算法不一定需要二叉树。

如有任何有关表示此数据的提示，我们将不胜感激。

Answer 1

通常，当您使用树搜索来解决问题时，每个节点代表世界的一些可能“状态”(例如，谁在桥的哪一侧)，每个节点的子节点代表所有可能的“后继状态”(可以从前一个状态一步到达的新状态)。深度优先搜索然后表示尝试一个选项直到它死胡同，然后备份到另一个选项可用的最后状态并尝试它。广度优先搜索表示并行尝试许多选项，然后查看第一个选项何时找到目标节点。

就编码的实际方式而言，您可以将其表示为多路树。每个节点可能包含当前状态，以及指向子节点的指针列表。

希望这对您有所帮助!