基于有限狀態(tài)機的自動售貨機控制器

3．3 模型評價
(1)擴展性
為層次型有限狀態(tài)機模型增加新功能，只需在其根節(jié)點下增加一個子節(jié)點，因為新的子節(jié)點與其他兄弟節(jié)點是互斥的，所以模型可以很方便地進行系統(tǒng)功能擴展。
(2)查找算法時間復雜度
假設系統(tǒng)中存在的狀態(tài)數(shù)量為n。如果不采用層次型有限狀態(tài)機模型，那么系統(tǒng)中的各個狀態(tài)都是相互獨立、互斥的，相當于所有的狀態(tài)都是一個虛擬根節(jié)點的子節(jié)點。這樣的話，查找下一狀態(tài)的時間復雜度為：

然而，上面的情況忽略了狀態(tài)之間的相關性，很有可能當前狀態(tài)與下一狀態(tài)是兄弟關系，此時的比較次數(shù)就會明顯減少。如果采用層次型狀態(tài)機，假設系統(tǒng)子功能數(shù)目為m(m>1)，那么平均每個子功能的狀態(tài)數(shù)目為n／m，當前狀態(tài)與下一狀態(tài)為兄弟節(jié)點的概率為p(0p1)。這種情況下的時間復雜度為：

其中，t1為當前狀態(tài)與下一狀態(tài)不是兄弟節(jié)點的查找時間，與狀態(tài)樹的平均深度^有關。但是由于存在局部相關性，并且這種相關性越大(即p值越大)，平均時間復雜度就越集中在前面部分(p?n)／(m?2)，后面的表達式值可以忽略不計，即：

顯然，T(n)2T(n)1。因此，該模型對于查找下一狀態(tài)在時間復雜度上也是有優(yōu)勢的。

結(jié) 語
通過建立層次型有限狀態(tài)機模型，并應用改進的數(shù)據(jù)結(jié)構(gòu)與狀態(tài)轉(zhuǎn)換算法，自動售貨機控制器的程序結(jié)構(gòu)更為清晰。原來存在于程序中的諸多標志變量，由狀態(tài)機的各個狀態(tài)所取代，使系統(tǒng)具有更好的擴展性；并且模型很好地利用了狀態(tài)的相關性，縮短了查找所花費的時間。但是，該模型也存在一定的局限性。比如，很大數(shù)量在構(gòu)造狀態(tài)樹時需要的存儲空間給一般嵌入式系統(tǒng)的成本帶來了挑戰(zhàn)，不過可以試圖通過讓所有的狀態(tài)共享內(nèi)存空間的方法來解決這個問題。因此，層次型有限狀態(tài)機模型應用于較為復雜的嵌入式系統(tǒng)具有更普遍的意義。