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

Question

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

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

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

• 平均 4.5 次比较（1.5 找层，1.5 找行，1.5 找位置）
• 3 次比较的最佳情况
• 9 次比较的最坏情况

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

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

Answer 1

马尔可夫链通过转换矩阵演变，在您的情况下可能是 27x27 矩阵。但是，您提出问题的方式意味着您不是在处理一般情况，并且有一些适用的特殊条件。

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