现在我有一个迷宫要通过 BFS 解决，以从起点找到目标。我需要打印一些信息，所以我决定创建一个具有 A、B 和 C 实例变量的类节点（是的，我使用 JAVA）。但我的问题是，在BFS期间，我不应该扩展具有相同A和B的节点。这意味着，例如，我首先扩展了节点（1,2,3），而不是我不应该扩展节点第二（ 1,2,5)。所以我想我应该尝试建立一个哈希图或哈希表。每次对于一个节点 node(x,y,z)，我都应该检查它的 (x,y) 是否曾经发生过。我该如何实施？它仍然是哈希时间 O(1) 吗？我应该以其他方式设计课程吗？谢谢！
问问题
194 次
2 回答
1
是的，您可以为此使用哈希表。您需要做的就是定义equals(Object)和hashCode()方法。对于这些，只要您只测试 (x,y) 而不是 (z)，那么任何具有相同 (x,y) 的节点都会在哈希图中发生冲突。但这还重要吗？您是否有两个具有相同 (x,y) 但 z 值不同的节点？那将是一个非常奇怪的迷宫……
编辑：最后听起来set对象也可以工作，并且正是您想要使用的。
于 2013-02-25T01:17:51.240 回答
0
对于这类工作，递归算法通常是最好的方法。
您的问题提出了一种需要使用全局信息的迭代方法。递归方法不需要保留此类信息，并且 woukd 还使您的代码更易于理解和实现。
于 2013-02-25T01:04:53.057 回答