4

我正在寻找一种可以相当有效地支持联合、查找和去联合的数据结构（至少为 O(log n) 或更好），因为标准的不相交集结构不支持去联合。作为背景，我正在使用 MCTS [ http://en.wikipedia.org/wiki/Monte_Carlo_tree_search]编写围棋 AI ，这将用于跟踪石头组，因为它们在回溯过程中连接和断开连接。我认为这可能会更容易，因为去联合不是在集合中的某个任意对象上，而是始终是最新联合的“撤消”。

我已经阅读了以下论文，虽然我可以执行建议的数据结构，但它似乎有点过头了，并且需要一段时间来实现 http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article =1773&上下文=cstech

当然，虽然 O(a(n)) 会很棒，但我很确定路径压缩不适用于去联合，而且我会对 O(log n) 感到满意。我的直觉告诉我一个解决方案可能与堆有关，但我无法弄清楚任何事情。

4

1 回答 1

6

您所描述的有时称为 union-find-split 问题，但大多数现代数据结构（或至少，我所知道的）通常以不同的方式看待这个问题。将每个元素视为森林中的一个节点。然后，您希望能够在操作下维护森林

  • 链接(x, y)，添加边 (x, y)，
  • find (x)，它返回包含 x 的树的代表节点，以及
  • cut (x, y)，将边缘从 x 切割到 y。

这些数据结构通常称为动态树或链接切割树。据我所知，没有与标准联合查找数据结构的实现简单性相匹配的有效数据结构。可能对您的案例有帮助的两种数据结构是链接/切割树（也称为 Sleator-Tarjan 树或 ST-tree）和 Euler-tour 树（也称为 ET-tree），它们都可以执行所有上述操作的时间为 O(log n)。

希望这可以帮助！

于 2014-09-10T01:51:17.223 回答