复杂决策树生成器

Question

我正在尝试编写一种二叉树，但它非常大，我不想将每个元素都保存在内存中。我更愿意在需要时使用生成器函数来构造每个节点。

树模拟游戏中的决策。游戏从一帧 n 个选项开始。玩家选择两个选项（不能相同），并使用不同的操作将它们组合起来。因此，一个框架有 (n * (n-1)) * t 个可能的步骤，其中 t 是操作数。

一旦做出决定，就会产生 n - 1 个选项的新框架，其中上次选择的两个选项已被删除，但这些选项的结果已包含在内。可能的不同选择的数量现在是 ((n - 1) * (n - 2)) * t。此过程一直持续到当前帧中的选项数 <= 1.

我想以特定方式遍历决策树中的所有可能路径 - 完全遍历每条路径一直到最后一帧（其中 n = 1） , 在移动到下一条可能的路线之前，该路线从最大的帧 (size = n) 开始，但在每个帧中采用下一系列选择。除了我在这里描述的内容之外，这些决定的结果与这些目的无关。所有路线都必须一直到最后一帧（其中 n = 1）——我不需要包括部分遍历的路线。

我有以下代码，我想生成一张决策图。 :

public class PathStep
{
    public int FrameSize;
    public int Index1;
    public int Index2;
    public int Operation;

    public override string ToString()
    {
        return String.Format("F:{0} I1:{1} I2:{2} O{3}", this.FrameSize, this.Index1, this.Index2, this.Operation);
    }
}

public class Frame
{
    public int Size { get; private set; }

    public Frame(int size)
    {
        this.Size = size;
    }

    public IEnumerable<PathStep> AllPossibleSteps()
    {
        return this.step_helper(this.Size, 0);
    }

    private IEnumerable<PathStep> step_helper(int frame_size, int depth)
    {
        throw new NotImplementedException(); //TODO
    }


    private static IEnumerable<Frame> frames_in_game(int initial_frame_size)
    {
        for (var i = initial_frame_size; i > 0; i--)
            yield return new Frame(i);
    }

    private static IEnumerable<PathStep> steps_in_frame(int frame_size)
    {
        int op_count = Operation.Operations().Count();

        for (var first = 0; first < frame_size; first++)
        {
            for (var second = 0; second < frame_size - 1; second++)
            {
                for (var i = 0; i < op_count; i++)
                {
                    yield return new PathStep() { FrameSize = frame_size, Index1 = first, Index2 = second, Operation = i };
                }
            }
        }
    }



}

我将如何填写我的 step_helper 方法来映射树中每个可能的决策变化，并按照连续游戏的顺序生成它们？我需要涵盖所有可能的路线，并且 yield return 按顺序在给定路线中采取的每一步，但我走完整路线的顺序无关紧要，只要我涵盖所有路线即可。

Answer 1

我重新思考了我的问题，并意识到以下几点：

如果n * (n -1) * t = options_per_frame

然后我可以将每条路径表示为一个选项网格，（如果有 1 个索引）开始于：

   let t = 4

   n |n-1|t | n = ?
   1 |1  |1 | 6
   1 |1  |1 | 5
   1 |1  |1 | 4
   1 |1  |1 | 3
   1 |1  |1 | 2

其次是：

   n |n-1|t | n = ?
   1 |1  |1 | 6
   1 |1  |1 | 5
   1 |1  |1 | 4
   1 |1  |1 | 3
   1 |1  |2 | 2

并以

结尾

   n |n-1|t | n = ?
   6 |5  |4 | 6
   5 |4  |4 | 5
   4 |3  |4 | 4
   3 |2  |4 | 3
   2 |1  |4 | 2

其中单元格中的每个值表示所选选项的 index/id，而 headers 指定可以放入单元格的最大值。所以，你可以把它想象成一个时钟——不同大小的 "gears" 用于相互旋转，这样变化就会随着幅度的减小而级联下来。在时间上，每秒 1000 毫秒 "rotates"，每小时 60 秒 "rotates"，一天 24 小时 "rotates" 等等。所以我创建了一个 PathGrid class，它返回了网格的下一次迭代，这让我可以一直跟踪每条路径，而不必为树建模或使用递归。我已经上传了我的解决方案 here.

复杂决策树生成器

Complex Decision Tree Generator

c#

algorithm

tree

generator

data-structures