欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

人工智能-自动机模型

程序员文章站 2022-03-05 11:13:23
这是一类智能的算法,没有什么固定的模式,就是一个算法思想,可以给我们一些有价值的指导,当我们想要做一些相关工作的时候,可以扩宽我们的视野,打开我们的脑洞,借鉴其中的原理。我不想多说里面的什么数学和公式,只要你懂里面的思想会迁移到实际的应用中就很不错,更好的则是在其基础上形成自己的思维,需要用的话,就像什么神经网络一样,最好使用现成的框架。简介有限状态机,(英语:Finite-stat......

这是一类智能的算法,没有什么固定的模式,就是一个算法思想,可以给我们一些有价值的指导,当我们想要做一些相关工作的时候,可以扩宽我们的视野,打开我们的脑洞,借鉴其中的原理。我不想多说里面的什么数学和公式,只要你懂里面的思想会迁移到实际的应用中就很不错,更好的则是在其基础上形成自己的思维,需要用的话,就像什么神经网络一样,最好使用现成的框架。

 

简介

有限状态机,(英语:Finite-state machine, FSM),又称有限状态自动机,简称状态机,是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。

 

状态存储关于过去的信息,就是说:它反映从系统开始到现在时刻的输入变化。转移指示状态变更,并且用必须满足来确使转移发生的条件来描述它。动作是在给定时刻要进行的活动的描述。有多种类型的动作:

进入动作(entry action):在进入状态时进行

退出动作:在退出状态时进行

输入动作:依赖于当前状态和输入条件进行

转移动作:在进行特定转移时进行

通俗的介绍

接下来来说说理解,首先从名字上来看,机指的是算法 状态则就是状态 有限表示其中状态是有限个数的。具体在模型上来看,有限状态机应该是这样的

人工智能-自动机模型

这是一个简单的例子,在一个情境中存在三种状态,两种动作,圆圈表示就是的是状态,状态之间的箭头表示状态的转移,而箭头上的表示对应的触发条件,例如在1状态如果发生b则状态变化为2,自己到自己的箭头表示状态不变化。

下面可以有一个更加通俗的小图例

人工智能-自动机模型

这是一个游戏ai的状态自动机模型,表示了ai在过程中的不同状态转换,虽然没有标志条件,但是看起来是不是更有意思了。

 

概念及加深理解

其在任意时刻都处于有限状态集合中的某一状态。当有一个触发动作时可以从当前状态转换到另一个状态,或者仍然保持在当前状态。任何一个FSM都可以用状态转换图来描述,图中的节点表示FSM中的一个状态,有向加权边表示输入字符时状态的变化。如果图中不存在与当前状态与输入字符对应的有向边,则FSM将进入“消亡状态(Doom State)”,此后FSM将一直保持“消亡状态”。状态转换图中还有两个特殊状态:状态1称为“起始状态”,表示FSM的初始状态。状态6称为“结束状态”,如果一个流程适用状态机来拟合,当达到结束状态后则表示该过程与模型拟合

人工智能-自动机模型

在图例中,我们的状态机初始是在状态1,这是人为初始设置的,而后根据我们箭头上的转移条件,我们可以看到随着状态的不断变化.如果达到了状态6,一切却停止了,因为无论施加什么条件都不能使状态发生变化,我们的状态机也结束了。

 

适用范围

这种基本原理决定了它是适用对象必须是包含多种状态的,但状态这是一个描述而且没有那么严格,可以是协议交互中不同的状态,也可以是有其中ai人物的状态,也可以是一个字符串中字符的状态。FSM的作用主要是描述对象在它的生命周期内所经历的状态序列,以及如何响应来自外界的各种事件。而我们使用它,常用的功能也就是两点:

  • 在当前状态,根据系统的输入决定下一状态,也就是控制或者类似于ai
  • 判断一个事件、序列是否符合某个流程,以此来判断目标是否符合我们的要求

这里有几个小例子,一个是TCP协议状态机,大家应该都有所耳闻,三次握手什么的计算机网络课上 协议课上都是主菜

 

人工智能-自动机模型

注意的地方

虽然我我们有用过状态机,但是也遇到过不少,无论是其他人的论文中,还是某些博客上,我只说说在理解时或者是实现时容易导致的问题‘

1.注意状态的变化

自动机就是状态到状态的变化,如果是一个大的模型,其中的状态和调试势必是非常多的,我们如果只是观察和理解的话,从这个转移图中直接看就可以。但是如果需要自己动手实现某个自动机的时候,我们需要有充分的准备,起码是心中有这样一个表,不用仔细看,只是为了示意用从别人那里摘过来的,当然在文尾已经引用了原文链接。

人工智能-自动机模型

这样的一个图可以很明显的展示你要做的工作,哪怕是比较复杂的逻辑,过了一段时间你在看也不会烦,因为这个图已经表明了一切,不需要你再去思考太多

2.实现方案

这个列表已经这么明显了,就是一个矩阵,对于条件的判断和转移我们可以使用if 也可以使用switch语句,甚至可以malloc一个矩阵然后定义好其中的元素。

抛除上边的不说,如何定义一个状态转移结构,方法也很多,甚至我们可以不需要定义特殊的结构,就使用一个变量来表示当前状态,其他的所有输入判断未尝不可以使用一个大循环来解决。当然在你有一定基础的情况下,采用链表的结构类似于【当前状态,【条件,下一状态】集合】这也不是不可以。

 

https://blog.csdn.net/benjonc/article/details/79870947 有关于一些接口的设计

https://www.jianshu.com/p/5eb45c64f3e3

 https://www.cnblogs.com/benxintuzi/p/4931258.html 还包含了c代码的示意实现

https://baike.baidu.com/item/%E6%9C%89%E9%99%90%E7%8A%B6%E6%80%81%E6%9C%BA/2081914?fr=aladdin

https://www.jianshu.com/p/5eb45c64f3e3

https://blog.csdn.net/bbs598598/article/details/50728332

本文地址:https://blog.csdn.net/iamsongyu/article/details/85861163