有限状态机学习

xiao7cn 发布于2019-08-16 10:57 / 3353人阅读

摘要：状态机有三个特征状态总数是有限的。由于有限状态机的这些特征，我们可以把状态转移的过程做成类似这样的状态转移表。

有限状态机是什么

有限状态机（英语：finite-state machine，缩写：FSM）又称有限状态自动机，简称状态机，是表示有限个状态（State）以及在这些状态之间的转移（Transition）和动作（Action）等行为的数学模型。

状态机有三个特征：

状态（State）总数是有限的。

在任一时刻，只处于一种状态。

在某种条件（Event）下，会从某种状态转移（Transition）到另一种状态，同时执行某个动作（Action）。

从有限状态机的定义和特征我们可以看到它的几个重要概念：

状态（State）：包括初始状态和事件触发后的状态，同时必须要有一个最终状态。

事件（Event）：触发状态机从一种状态切换到另一种状态。

转移（Transition）：状态切换路径，包含Event(触发该转移的事件)，Source(源状态），Target(目的状态)。

动作（Action）：表示在进行状态转移后要执行的具体行为。

由于有限状态机的这些特征，我们可以把状态转移的过程做成类似这样的状态转移表。

条件当前状态	状态A	状态B	状态C	状态D
条件X	状态B	状态C	状态D	...
条件Y	状态C	状态D	...	...
条件Z	...	状态A	状态A	状态A

可以归纳为一个公式。
Old State + Event = New State

把上面的状态转移表用公式表达就是
状态A + 条件X = 状态B
状态A + 条件Y = 状态C
...

有限状态机例子

我们小时候都应该玩过贪吃蛇这个游戏，游戏规则不必再说，我们看看使用有限状态机来实现这个游戏。

状态转移表：

条件当前状态	GAME_OVER	UP	DOWN	LEFT	RIGHT
EAT	...	UP	DOWN	LEFT	RIGHT
HIT	...	GAME_OVER	GAME_OVER	GAME_OVER	GAME_OVER
TURN_UP	UP	...	...	UP	UP
TURN_DOWN	DOWN	...	...	DOWN	DOWN
TURN_LEFT	LEFT	LEFT	LEFT	...	...
TURN_RIGHT	RIGHT	RIGHT	RIGHT	...	...

EAT：吃掉食物
HIT：撞墙或自己
TURN_UP：向上转向事件
...
GAME_OVER：为了简便一点，我们让它既是开始又是结束的状态，当按下上下左右任一键时开始游戏。
UP: 向上前进状态，此时可以吃掉食物，也可以撞到墙或自己，同时可以向左向右转向，但按下向上或向下是不会触发任何动作。
...

当我们把状态转移表定义好之后就会发现这个游戏剩下的部分非常好写，而且逻辑非常清楚，这就是有限状态机的好处。

有限状态机在编程中有哪些应用

词法分析

正则表达式

网络协议

游戏设计

自动电话客服

...

我们用有限状态机做什么

笔者目前所在的部门是正在使用OpenStack做电子网络靶场的一个项目，必然少不了对虚拟机各项指标的采集，因此对采集进行监控也是必要的措施，以便在采集故障之后及时预警。

整个监控流程是由客户端（Java微服务）往Kafka中发一条采集配置，采集端（Python）收到这条配置后进行解析配置，然后进行指标采集，同时往Kafka回传一些运行信息，当想要停止采集时需要客户端再次下发一条关闭配置，采集端进行执行并回传至Kafka关闭信息。

看似这个过程十分简单，像把大象装进冰箱一样简单。

打开冰箱门。

把大象塞进行。

关上冰箱门。

使用有限状态机来做其中的状态转移时真的就像是把大象塞进冰箱一样简单（其中使用restful接口接收客户端的开始关闭配置，监听kafka指定topic来处理采集端消息）。

定义状态转移表

条件当前状态	Idle	processing	wait_close	exception	timeout
start_conf
error_conf	closed
pro_start	processing
heartbeat		processing			processing
error_runtime		exception
stop_conf	wait_close	wait_close		wait_close
pro_stop			closed	closed	closed
msg_timeout	timeout	timeout	timeout	timeout
fix					closed

事件

start_conf：客户端（Java微服务）采集配置

error_conf：采集端（Python）配置解析错误

pro_start：采集端（Python）开始采集

heartbeat：采集端（Python）正在采集

error_runtime ：采集端（Python）采集过程中出错

stop_conf:客户端（Java微服务）关闭配置

pro_stop: 采集端（Python）退出采集

msg_timeout:采集端（Python）消息超时

fix: 监控端手动确认任务已经人为修复

状态

Idle：收到采集配置后有限状态机的默认状态

processing：正在采集

wait_close ：收到关闭配置后等待关闭

exception：采集异常

timeout：超时

closed：采集关闭

使用状态机进行编码

笔者这里使用的库是squirrel-foundation，支持多实例状态机并且和spring进行整合也比较简单。

总结

有限状态机能使我们从复杂的状态转移判断中脱离出来，专心业务逻辑，并且避免状态转移过程的判断错误，是一种很强大的模型。

GPU云服务器云服务器有限状态机状态机 python 状态机深度学习状态

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/70781.html

有限状态机学习

摘要：状态机有三个特征状态总数是有限的。由于有限状态机的这些特征，我们可以把状态转移的过程做成类似这样的状态转移表。有限状态机是什么有限状态机（英语：finite-state machine，缩写：FSM）又称有限状态自动机，简称状态机，是表示有限个状态（State）以及在这些状态之间的转移（Transition）和动作（Action）等行为的数学模型。状态机有三个特征：状态（St...

bbbbbb 2019-07-30 15:07 评论0 收藏0
状态决定视图——基于状态的前端开发思考

摘要：前端与状态现在的前端开发中，对于状态的管理是重中之重。有限状态机那么如何更好的管理前端软件的复杂度的状态机思想给出了自己的答案。有限状态机并不是一个复杂的概念简单说，它有三个特征状态总数是有限的。前提在现在的前端社区，关于MVVM、Model driven view 之类的概念，已经算是非常普及了。React/Vue 这类框架可以算是代表。而自己虽然有 React/Vue 的使用经...

miya 2019-08-20 18:22 评论0 收藏0
前端设计模式用起来（1）状态模式

摘要：有限状态机可以归纳出四个要素现态即当前的状态。但状态模式还有一点需要注意到，当采用子类继承实现多种具体状态的时候，注意控制状态的数量，以免出现子类数量膨胀的现象在使用或等更完整面向对象语言时。业务代码开发久了，偶尔看看设计模式，总会让自己有一种清新脱俗的感觉。总想把这种感觉记下来，但一想到要先起个恰如其分的标题和开头，就让我有一种百爪挠心的纠结，所以迟迟没有开始。今天起更新我学习设计...

Salamander 2019-08-23 12:58 评论0 收藏0
“数学之美”系列十：有限状态机和地址识别

地址的识别和分析是本地搜索必不可少的技术，尽管有许多识别和分析地址的方法，最有效的是有限状态机。一个有限状态机是一个特殊的有向图（参见有关图论的系列），它包括一些状态（节点）和连接这些状态的有向弧。下图是一个识别中国地址的有限状态机的简单的例子。每一个有限状态机都有一个启始状态和一个终止状态和若干中间状态。每一条弧上带有从一个状态进入下一个状态的条件。比如，在上图中，当前的状态是省，如果遇到一个词...

libxd 2019-04-25 17:59 评论0 收藏0