存储大前缀树的最佳方法

Question

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

Answer 1

您正在寻找的是一个嵌入式DB，它们中的大多数都是用C++编写的，但也有一些具有C#包装器。我推荐Berkeley DB for .NET (它是Oracle's Berkeley DB的包装器)。

我建议您为每个前缀树生成唯一的散列，其中所生成的散列将具有正确表示相似前缀树的局部性:换句话说，两个相似前缀树的散列应该彼此非常接近。你提到的游戏叫做Tic-Tac-Toe，所以散列类似的Tic-Tac-Toe游戏应该很容易，这里有一些参考资料(我并没有真正读过它们，我只是快速搜索了一下“easy -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文件的路径)。然后，您所要做的就是查找类似的散列，并从aux文件中检索相应的树。

Berkeley DB按顺序存储类似的键，因此您可以相信它不会移动键并破坏您散列的局部性。因为局部性不会被破坏，所以您可以进行额外的优化，检索大量的键-值对，并减少在磁盘上进行的查找和寻道的次数。