一个放置充分长时间的发射子弹植物,面对一个早已存在于场上的僵尸,于任何一个时间点,考察其距离下一次触发子弹发射倒计时的时间点(不包含当前时间点)的时长x服从的分布律,称为初次攻击分布。该分布律只与植物自身的攻击间隔有关。(注意上述为初次攻击分布的第一种表述)
用马尔可夫链来解决这个问题。“任一个时间点距离下一次触发子弹发射倒计时时长”对应的就是马尔可夫链的一个状态;每cs发生一次状态转移,而且仅与前1cs的状态相关。求这个所谓的初次攻击分布,也即求给定的初始分布下的极限分布(如果存在的话)。
初始分布是什么样的
以豌豆射手为例,其刚刚被种下的第0cs初,其生产物品倒计时内存值被等概率设置为0~150,但是pvz会将初始时刻的0视作1进行处理。因此实际上此时的初始分布是如下的向量:
1cs的概率会是其他概率的2倍(包含了内存值0与1两种情况)。
状态转移的方式
每过1cs内存值减1,当内存值减为0时,它会瞬间以等概率设置为136~150间的值,即第1cs时向量变为
状态转移矩阵
内存值大于1(对应2cs~150cs),下一cs便减1,也即 x_i → x_{i-1} , i>1 的转移概率全部为1。
内存值等于1,下一cs首先变为0,之后等概率变为136~150某值,也即 x_1→x_i , 136 ≤ i ≤ 150 的概率全部为 1/15。
容易写出状态转移矩阵(与一般的记法转置,原因是我前面分布向量写成列向量了):
容易证明:该马尔可夫链是正则链。因此任意给定初始分布都趋于相同的平稳分布。
直接来考虑更一般的情况:
n 是植物最大攻击间隔,k = 最大攻击间隔 - 最小攻击间隔 + 1。对于我们讨论的植物而言,都有 k=15
于是状态转移矩阵
同样是正则链。直接求解
其中向量x表示分布,每个元素是一个概率(豌豆射手为例):
这是一个特征值问题,求出特征向量后归一化即可。得到
它就是我们求得的初次攻击分布。
代入k=15,n=150,200,300可以得到发射类植物,忧郁菇,投掷类植物对应的初次攻击分布(重写成分布的形式):
发射类植物(间隔136~150)
忧郁菇(间隔186~200)
投掷类植物(间隔286~300)
第二种表述:有时候初次攻击分布表述为“……包含本cs的,最早触发子弹发射倒计时的时长(以豌豆射手为例:0cs~149cs)”对应的概率分布。
可以得到相同的初始分布、状态矩阵与平稳分布。只不过现在向量x的含义变为:
即下标 i 对应的是 i-1 cs。
第三种表述:于0cs放置的僵尸,最早触发子弹发射倒计时的时长(以豌豆射手为例:2-151cs)。同理,现在x含义变为:
0cs放置的僵尸,若要在不重置前触发攻击,对应生产物品倒计时至少需要是2,对应最短的“触发子弹发射倒计时的时长”为2cs。如果0cs对应生产物品倒计时为1,且下一次不幸以1/15的概率重置为150,那么就对应最长的间隔151cs。此处也可以看出来,137cs-151cs有一部分情况是由重置了一次得到的。不过这并不影响最终的概率计算,无论是否重置,我们只关心第一次触发攻击的间隔。
上面我介绍了3种“初次攻击分布”的不同表述,它们有各自的使用条件,在使用初次攻击分布”时,务必搞清楚到底用哪一种表述。