存储大前缀树的最佳方式

Question

我打算编写一个程序,代表AI玩玩棋盘游戏.我希望将每个玩过的游戏保留在前缀树中,以搜索类似的游戏.但我担心这棵树会变得太大而无法留在记忆中.那么存储它的最佳方式是什么.并且能够快速搜索它.我不认为将其写入文件是一个很好的解决方案.可能是DB的一位王者？

Answer 1

您正在寻找的是嵌入式数据库，其中大多数是用 C++ 编写的，但也有一些具有 C# 包装器。我推荐Berkeley DB for .NET （它是Oracle Berkeley DB 的包装器）。

我建议您为每个前缀树生成一个唯一的哈希值，其中生成的哈希值将具有正确表示相似前缀树的局部性：换句话说，两个相似前缀树的哈希值应该彼此非常接近。您所指的游戏被称为 Tic-Tac-Toe，因此散列类似的 Tic-Tac-Toe 游戏应该很容易，这里有一些参考资料（我没有真正阅读它们，我只是快速搜索了“哈希 Tic-Tac-Toe”，这些是结果）：

• 我想这可能是java的例子
• 井字游戏策略缩减
• http://cg.scs.carleton.ca/~luc/1997notes/topic14/

然后，哈希值存储在 Berkeley DB 中，前缀树存储在 aux 文件中，或者如果您愿意，也可以将其存储在值中。由于 Berkeley DB 存储键值对，因此您可以将哈希设置为键并将值设置为任何内容（即您的前缀树或包含前缀树的 aux 文件的路径）。然后您要做的就是查找类似的哈希值并从 aux 文件中检索相应的树。

Berkeley DB 按顺序存储相似的键，因此您可以放心，它不会移动键并破坏哈希的局部性。由于局部性不会被破坏，因此您可以进行额外的优化并检索大页的键值对，并减少在磁盘上执行的查找和查找次数。