基于有限状态机的自动售货机控制器

3．3 模型评价
(1)扩展性
为层次型有限状态机模型增加新功能，只需在其根节点下增加一个子节点，因为新的子节点与其他兄弟节点是互斥的，所以模型可以很方便地进行系统功能扩展。
(2)查找算法时间复杂度
假设系统中存在的状态数量为n。如果不采用层次型有限状态机模型，那么系统中的各个状态都是相互独立、互斥的，相当于所有的状态都是一个虚拟根节点的子节点。这样的话，查找下一状态的时间复杂度为：

然而，上面的情况忽略了状态之间的相关性，很有可能当前状态与下一状态是兄弟关系，此时的比较次数就会明显减少。如果采用层次型状态机，假设系统子功能数目为m(m>1)，那么平均每个子功能的状态数目为n／m，当前状态与下一状态为兄弟节点的概率为p(0p1)。这种情况下的时间复杂度为：

其中，t1为当前状态与下一状态不是兄弟节点的查找时间，与状态树的平均深度^有关。但是由于存在局部相关性，并且这种相关性越大(即p值越大)，平均时间复杂度就越集中在前面部分(p・n)／(m・2)，后面的表达式值可以忽略不计，即：

显然，T(n)2T(n)1。因此，该模型对于查找下一状态在时间复杂度上也是有优势的。

结 语
通过建立层次型有限状态机模型，并应用改进的数据结构与状态转换算法，自动售货机控制器的程序结构更为清晰。原来存在于程序中的诸多标志变量，由状态机的各个状态所取代，使系统具有更好的扩展性；并且模型很好地利用了状态的相关性，缩短了查找所花费的时间。但是，该模型也存在一定的局限性。比如，很大数量在构造状态树时需要的存储空间给一般嵌入式系统的成本带来了挑战，不过可以试图通过让所有的状态共享内存空间的方法来解决这个问题。因此，层次型有限状态机模型应用于较为复杂的嵌入式系统具有更普遍的意义。