我要编写一个程序，该程序将代表AI来与玩家进行棋盘游戏。我想将每个玩过的游戏都保留在前缀树中，以搜索类似的游戏。但是我担心树会变得太大而无法保存在内存中。那么什么是最好的存储方式。并能够快速搜索它。我认为将其写入文件不是很好的解决方案。可能在DB的王者中？
最佳答案
您正在寻找的是嵌入式DB，其中大多数都是用C++编写的，但是有些具有C#包装器。我建议Berkeley DB for .NET(这是Oracle's Berkeley DB的包装)。
我建议您为每个前缀树生成一个唯一的哈希，其中生成的哈希将具有正确表示相似前缀树的局部性:换句话说，两个相似前缀树的哈希应彼此非常接近。您所指的游戏称为Tic-Tac-Toe，因此对类似的Tic-Tac-Toe游戏进行哈希运算应该很容易，这里有一些引用资料(我没有真正读过它们，我只是快速搜索了“散列井字游戏”，这些就是结果):
然后，将哈希存储在Berkeley DB中，并将前缀树存储在aux文件中，或者如果需要，也可以将其存储在值中。由于Berkeley DB存储键值对，因此您可以将哈希值设置为键，并将值设置为任何值(即，前缀树或包含前缀树的aux文件的路径)。然后，您要做的就是查找相似的哈希并从aux文件中检索相应的树。
Berkeley DB会顺序存储类似的 key ，因此您可以依靠它不会移动 key 并破坏哈希的局部性这一事实。由于位置不会被破坏，因此您可以进行其他优化，并检索较大的键值对页面，并减少在磁盘上进行查找和查找的次数。
关于c# - 存储大前缀树的最佳方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6071034/