(有限)状态机

(有限)状态机,第1张

状态是最基本的设计模式。

而我们常常说的状态机指有限状态机,缩写是FSM(Finite State Machine)。

无限状态机仅仅是理论上存在的概念,比如,把1/3变成一个状态机的话,那这个状态就是无限循环了,实际上没啥实际的应用意义。

我们常说的状态机指有限状态机。

不夸张的说,状态机模型是世界运行的基础,大脑做的决策推演,在火星上运行的祝融号,计算机软件的底层设计,游戏中的沙雕AI,其底层逻辑都是状态机。

有限状态机的定义: 有限个状态 及在这些状态之间的转移和动作等行为的数学模型;在计算机科学中,状态机的关键要素是状态和状态的转移。

按照输入输出关系,状态机模型有2个,分别是Moore模型(发明者:Edward Moore 1956)和Mealy模型(发明者:George H. Mealy 1955),看到这俩名字,莫名的就想到了《Rick and Morty》...

这两个模型的特点可以用如下公式概括:

一句话:

Moore的设计仅仅与状态有关,Mealy的设计与状态和输入有关系。

Mealy的状态比Moore的状态要少。

它们的设计和表示方法如下所示:

moore和mealy本质上并没有什么差别,设计上可以互相转化。

上图中的A Mealy 转为 Morre 如下所示:

上图中的B Moore 转为 Mealy 如下所示:

推导过程可以参考:http://catonblack.cn/2019-01-18/mealy2moore/

回到程序设计的话题,要设计一个通用的状态机程序,只用switch,case肯定是不够的;

当然,不管是用哪种语言,只要把握住状态机的三个核心要素即可,即:

画成一张图如下(手动 @陈振):

把它转换成一个数据结构,即:

通用的设计思路是把所有的状态和状态转换表达成一个表,通过查表的形式驱动状态机运转起来。

状态转移表,示例是一个输入4个数字密码(9527)的状态转移表:

状态机的查询和运转:

运行结果展示:

在python里面有一个transitions状态机库,感兴趣的同学可以自己学习一把。

运行结果:

掌握了核心思想,设计一个状态机的通用程序并不是很复杂的事情。

-- EOF --

这个应该是mealy的状态机,输出由输入和状态输出同时决定。Mealy 型

output=f(input,state)

output=f(input,state)

nextstate=f(input,state)

nextstate=f(input,state)


欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/yw/11925876.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023-05-19
下一篇 2023-05-19

发表评论

登录后才能评论

评论列表(0条)

保存