c# - 存储大前缀树的最佳方式

Question

我将编写代表 AI 与玩家玩棋盘游戏的程序。我想将每个玩过的游戏都保存在前缀树中，以便在其中搜索类似的游戏。但我担心这棵树会变得太大而无法保存在内存中。那么什么是最好的存储方式。并且能够快速搜索它。我不认为将它写入文件是好的解决方案。可能在某个数据库之王中？

Answer 1

您正在寻找的是嵌入式数据库，其中大部分是用 C++ 编写的，但也有一些具有 C# 包装器。我推荐 Berkeley DB for .NET (这是 Oracle's Berkeley DB 的包装器)。

我建议您为每个前缀树生成一个唯一的散列，其中生成的散列将具有适当表示相似前缀树的位置:换句话说，两个相似前缀树的散列应该彼此非常接近.您所指的游戏称为 Tic-Tac-Toe，因此散列类似的 Tic-Tac-Toe 游戏应该很容易，这里有一些引用资料(我没有真正阅读它们，我只是快速搜索了“哈希 Tic-Tac-Toe”，结果就是这些:

• I think this might be java example
• TicTacToe strategic reduction
• http://cg.scs.carleton.ca/~luc/1997notes/topic14/

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

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