bit早就想好了对策：穷举所有可能的状态序列肯定是比较直观的想法，但是这个目标太“大”！需要把问题分解一下，分解为一个一个的子任务。具体到现在的这个情况就是：最终目标我们要找到一个长度为43789241的状态序列，但是一下子找到这个序列太难了，所以不妨考虑一下先找到一部分序列。

其实就是把整个时间序列进行拆分，每个时刻都计算一下当前时刻达到该状态的所有可能并依次往下计算，可有效减少计算量。

如果从全局考虑，那么一共需要考虑27种路径，每个节点之间的距离不一样，我们需要找到最短的那一条路，那么我们现在的情况难道是把27种所有的路径的距离全都算一遍然后作比较吗？不，我们可以这么想，假设从s到e的最短路径经过c1，那么从这条最短路径从s到c1这段路径一定是从s到c时刻各个状态当中最短的路径。

有人可能会觉得是不是还存在其他路径比这个更短呢？

不会的，因为如果从s到c时刻存在比最短路径的这个子路径更短的路径，那么用这个更短的路径替换掉这段子路径，那么新形成的这个s到e的总路径就会比原来更短，这与我们的假设矛盾（假设就是最短路径，不存在更短的路径）；以此类推，我们只需要找到从出发点开始到每一个时刻t的各个状态的最短路径状态x，然后从t时刻的状态x出发，考虑到t+1时刻的各个状态的路径长短就可以了，这样每个时刻我们都会选出最短路径经过的那个状态，放弃考虑其他所有状态，，，，一直到终点我们就可以大大减少计算量。

换到我们现在遇到的这个问题，我们就可以依次找到从周期开始的时刻到43789241个时刻的每一个时刻最大可能的状态序列的那个磁场状态，直到最后时刻，这样我们就可以找到我们想要的那个磁场状态序列， 然后考虑到每个时刻预测结果的验证过程，在下一个周期开始之后的每一个时刻根据预测的磁场状态有效的调节我们的磁场干扰装置，进而影响中子星对我们的飞创的引力束缚，使得我们的飞船与中子星保持相对的引力平衡距离，平稳驶过这一片空间。

说干就干，大家一致觉得bit的提议合理，飞船按照大家讨论的方案驶向经过中子星的——逃逸不可能范围——也就是说进入这片区域之后，一旦磁场预测失误，那么结果可能就是进入中子星的怀抱… …

第1个时刻顺利通过，第2个时刻顺利通过，第3个时刻顺利通过…第43789200个时刻顺利通过，就在大家为刚才的4000多万个成功预测感到庆幸，为即将度过的剩下41个时刻（也就是不到一秒钟的时间）期待不已紧张到窒息的时候，飞船突然发生了倾斜，所有人感受到了一股撕裂感的同时，飞船被吞没了… …

02—掉书袋

【1】 上述情节是对隐马尔科夫模型(hmm)算法的一个通俗演义。

【2】 hmm是典型的序列模型。

【3】 hmm模型有三个基本问题：

（1）评估问题，也被称为识别问题。给定模型λ（模型通常以一组参数的形式出现，比如<a,b,π>）和观测序列o，计算每个hmm模型产生当前观测序列的输出概率p(o|λ)，通过对比各个模型输出概率，概率最大的模型即为识别结果。

（2）解码问题。给定模型λ和观测序列o，寻找最有可能产生观察序列o的隐含状态序列的过程，即寻找最佳状态序列 q = q1q2q...qt来最好地解释观测序列o。

（3）学习问题。已知观测序列o，估计模型参数(a，b，π)，使p(o|λ)最大。

上述情节是针对问题（2）进行演义，磁场状态对应模型中的隐状态序列，引力序列对应模型中的观测序列；同时为了简化问题，模型参数未介绍详细参数。

【4】bit提出的解法是求解状态序列时典型的前向算法，就是为了计算效率问题，典型的动态规划思路，此处也不做详细介绍。

03—参考文献

1. 关键字：《统计学习方法》、李航

2. 关键字：《机器学习》、西瓜书、周志华

3. 关键字：coursera、hmm

比奇屋 www.biqi5.com