algorithm - 最高效的马尔可夫链算法

Question

我当前的副项目需要使用 3x3x3 马尔可夫链。我想出的第一个实现是让矩阵中的每个位置都有机会移动到那个位置(所有位置的值总和为 1)。根据矩阵中的值，这将导致:

• 平均 13.5 次比较
• 1 次比较的最佳案例
• 27 次比较的最坏情况

我的下一个想法是将每一行和每一层的总和存储为一个额外的类变量数组。这将允许它在以下位置找到正确的位置:

• 平均进行 4.5 次比较(1.5 次查找层，1.5 次查找行，1.5找位置)
• 3 次比较的最佳案例
• 9 次比较的最坏情况

我们已经可以看出这是一个更好的实现比较，但也有一些额外的数据需要存储。

有没有更好的方法来实现这个？

Answer 1

马尔可夫链通过转移矩阵演化，在您的情况下，它可能是 27x27 矩阵。但是，您提出问题的方式暗示您不是在处理一般情况，而是有一些特殊情况适用。

如果我要这样做，我的第一个想法是现在的计算机速度如此之快，以至于不值得担心初始版本的效率，最好得到一些初步结果。所以我只会开始担心后续版本的效率。特别是，您的更高效版本显然更难正确，并且如果您保存的某些变量与马尔可夫链的基础状态不同步，可能会有点危险。因此，测试这种更高效实现的重要工具是您首先想到的强力低效实现。