存儲大型前綴樹的最佳方式

我打算編寫一個程序，它將代表與玩家玩棋盤遊戲的AI。我想保持每個玩過的遊戲都在前綴樹中搜索相似的遊戲。但是恐怕樹會變得太大而不能留在記憶中。那麼存儲它的最佳方式是什麼？並且能夠快速搜索。我不認爲將它寫入文件是很好的解決方案。可能會在DB的某個國王？存儲大型前綴樹的最佳方式

來源

2011-05-20 IordanTanev

大怎麼大？內存限制在這些天大約500GB。 – TomTom 2011-05-20 11:10:42

根據遊戲的不同，可能沒有解決方案，除非不存儲所有變體。例如，國際象棋有太多的字段組合，所以最後你必須編程，而不是使用查找表。 – TomTom 2011-05-20 11:11:17

英語不是我的母語，我不知道英文遊戲的名字直接翻譯是海洋國際象棋。但我的目標是用50x50甚至更大的電路板進行非常難的版本。 – IordanTanev 2011-05-20 11:20:45

你在找什麼是嵌入式數據庫，其中大部分都是用C++編寫的，但也有一些C＃包裝器。我建議Berkeley DB for .NET（這是一個圍繞Oracle's Berkeley DB包裝）。

我會推薦的是，你爲每個前綴樹生成一個獨特的散列，其中生成的散列會有一個正確表示相似前綴樹的局部性：換句話說，兩個相似前綴樹的散列應該非常接近每個其他。你所指的遊戲稱爲Tic-Tac-Toe，所以哈希類似的Tic-Tac-Toe遊戲應該很容易，下面是一些參考文獻（我沒有真正閱讀它們，我只是做了一個快速搜索「散列井字棋」，而那些人的結果）：

然後哈希存儲在Berkeley DB和前綴樹存儲在一個輔助文件中，或者如果你想要的話，你也可以將它存儲在值中即由於Berkeley DB存儲了鍵值對，因此可以將散列值設置爲鍵值和值（即您的前綴樹或包含前綴樹的輔助文件的路徑）。然後，你所做的就是查找類似的散列並從aux文件中檢索相應的樹。

伯克利DB按順序存儲相似的鍵，所以您可以依賴它不會移動鍵並打破哈希的局部性的事實。由於本地不會被破壞，因此您可以進行額外的優化並檢索大量的鍵值對，並減少查找次數並尋求您在磁盤上執行的操作。

來源

2011-05-20 13:22:54 Kiril

存儲大型前綴樹的最佳方式

回答

相關問題