c# - 处理非常大的树状数据结构 : OutOfMemoryException

Question

我正在创建一个类似国际象棋的程序的变体，它需要同时生成和遍历一个非常大的树状结构。每个节点有 10 个 bool、一个 int、8 个 ulong、一个 short[64] 和 2 个 ulong[64]。根节点接收一些初始参数，然后从那里以编程方式(递归)确定有效的子节点。

基本上，当用户和程序轮流从一个子节点遍历到另一个子节点时，我的程序会不断地生长这棵树。每次“选择”一个新的子节点时，它的父节点和兄弟节点都不再需要并被丢弃。当树达到(平均)大约 60 的深度(从初始根节点开始)时，有效子节点的数量自然会开始减少，直到大约 75 的深度，树分解为一个最终节点，没有更多的 child 。

起初，这背后的逻辑看起来相当简单，但我不断遇到 OutOfMemoryException，这完全扼杀了任何进一步的进展。

以下是每“一代”有效 child 的一些平均值:

Generation    New Nodes
1             1    
2             20
3             4,000
4             30,000
5             2,200,000
6             > 50,000,000

在我的实际程序中，我什至无法完全展开第五代。当我不保留特定于节点的数据时(一旦节点的数据被用来确定它自己的 child ，我就会清除它)我可以完全扩展第 5 代，但在第 6 代中途遇到了非常坚固的墙。

理想情况下，我希望我的程序最终达到并在“当前”节点之后保持 8 代节点。我看得越多，就越不可能。

我厌倦了使用 sqlite 数据库运行它，但它无法足够快地生长树。

有谁知道处理非常大的树结构的任何潜在替代方案？

Answer 1

您的问题没有通用的答案。我将假设计算这棵大树以确定计算机程序的最佳移动？

在这种情况下，定义一系列 Action 的效用函数可能会对您有所帮助，该函数可以衡量在游戏中做出这一系列 Action 的值(value)。如果目标是达到最高分数或类似的东西，那么该分数是一个很好的效用函数。

有时您无法得出准确的效用函数，在这种情况下，一种常见的方法是对效用进行启发式评估。基本上它是一个近似值，或最佳猜测。启发式越好，对手就越厉害。

您想要进行效用测量的原因是执行修剪。例如，深度优先遍历树几次并计算最小和最大效用。这些值可以帮助您修剪完整的算法，这意味着您可以使用这些边界来确定您的树遍历算法是否可以在完成之前终止。

同样，这完全取决于您的游戏机制以及遍历树的方式，但希望这能让您朝着正确的方向思考。