状态机适合解决什么样的问题？[关闭]

StackOverflow https://stackoverflow.com/questions/40602

  •  09-06-2019
  •  | 
  •  

题

状态机最适合解决什么样的编程问题？

我读过有关使用状态机实现的解析器的信息，但想找出需要作为状态机实现的问题。

有帮助吗？

解决方案

最简单的答案可能是它们几乎适用于任何问题。不要忘记计算机本身也是一个状态机。

不管怎样，状态机通常用于解决存在一些输入流的问题，并且在给定时刻需要完成的活动取决于该点在该流中看到的最后一个元素。

此输入流的示例：解析时的一些文本文件、正则表达式的字符串、事件，例如 player entered room 用于游戏AI等

活动示例：准备好读取一个数字（在另一个数字后面跟着一个 + 出现在计算器解析器的输入中），转身（在玩家接近然后打喷嚏之后），执行跳跃踢（在玩家按下左，左，右，上，上之后）。

其他提示

这么好的资源居然是免费的 状态机电子书. 。我自己的快速回答如下。

当您的逻辑必须包含有关上次运行时发生的情况的信息时，它必须包含状态。

因此，状态机只是记住（或作用于）信息的任何代码，这些信息只能通过理解之前发生的事情来获得。

例如，我的程序必须使用一个蜂窝调制解调器。它必须按顺序执行以下步骤：

  1. 重置调制解调器
  2. 启动与调制解调器的通信
  3. 等待信号强度表明与信号塔连接良好
  4. ...

现在我可以阻止主程序并简单地按顺序执行所有这些步骤，等待每个步骤运行，但我想向用户提供反馈并同时执行其他操作。因此，我将其实现为函数内的状态机，并每秒运行该函数 100 次。

enum states{reset,initsend, initresponse, waitonsignal,dial,ppp,...}
modemfunction()
{
  static currentstate

  switch(currentstate)
  {
  case reset:
    Do reset
    if reset was successful, nextstate=init else nextstate = reset
    break
  case initsend
    send "ATD"
    nextstate = initresponse 
    break
  ...
  }
currentstate=nextstate
}

更复杂的状态机实现协议。例如，我使用的 ECU 诊断协议只能发送 8 字节数据包，但有时我需要发送更大的数据包。ECU很慢，所以我需要等待响应。理想情况下，当我发送消息时，我使用一个函数，然后我不关心会发生什么，但我的程序必须在某个地方监视线路并发送和响应这些消息，将它们分解成更小的部分，并将收到的消息重新组装成最后的消息。

有状态协议（例如 TCP）通常表示为状态机。然而，您很少需要将任何东西实现为状态机本身。通常您会使用一的损坏，即让它在处于一种状态时执行重复的操作，在转换时记录数据，或在保持一种状态时交换数据。

工作流程（请参阅.net 3.0 中的 WF）

它们有很多用途，解析器是其中一个值得注意的用途。我个人曾使用简化的状态机在应用程序中实现复杂的多步骤任务对话框。

一个解析器示例。我最近编写了一个解析器，它从另一个程序获取二进制流。解析的当前元素的含义指示下一个元素的大小/含义。可能存在（少量）有限数量的元素。因此有一个状态机。

它们非常适合对改变状态的事物进行建模，并且具有在每次转换时触发的逻辑。

例如，我会使用有限状态机来跟踪邮件包裹，或者在注册过程中跟踪用户的不同状态。

随着可能的状态值数量的增加，转换的数量也会呈爆炸式增长。在这种情况下，状态机有很大帮助。

游戏中的对象通常表示为状态机。AI 角色可能是：

  • 守护
  • 挑衅的
  • 巡逻
  • 睡着了

所以你可以看到这些可能会模拟一些简单但有效的状态。当然，您可能可以制作一个更复杂的连续系统。

另一个例子是在 Google Checkout 上进行购买等流程。Google 提供了财务和订单的多种状态，然后通知您信用卡清算或被拒绝等转换，并允许您通知它订单已发货。

复杂系统中的正则表达式匹配、解析、流程控制。

正则表达式是状态机的一种简单形式，特别是有限自动机。尽管可以使用相互递归函数来实现它们，但它们本身具有自然的表示形式。

状态机如果实施得当，将会非常高效。

如果您想制作一个可读的状态机，有一个针对多种目标语言的优秀状态机编译器。

http://research.cs.queensu.ca/~thurston/ragel/

它还可以让您避免可怕的“转到”。

游戏中的人工智能通常是使用状态机来实现的。帮助创建更容易构建和测试的离散逻辑。

我想到的事情是：

  • 机器人/机器操纵...工厂里的那些机械臂
  • 模拟游戏（SimCity、赛车游戏等）

概括：当您有一串输入与其中任何一个交互时，需要了解先前的输入，或者换句话说，当处理任何单个输入时都需要了解先前的输入。（也就是说，它需要有“状态”）

但据我所知，这不能简化为解析问题。

附带说明一下，您可以使用适当的尾部调用来实现状态机，就像我在 尾递归 问题。

在该示例中，游戏中的每个房间都被视为一种状态。

此外，使用 VHDL（和其他逻辑综合语言）的硬件设计到处都使用状态机来描述硬件。

如果您需要一个简单的随机过程，您可以使用马尔可夫链，它可以表示为状态机（给定当前状态，下一步该链将以一定的概率处于状态 X）。

任何工作流应用程序，尤其是具有异步活动的工作流应用程序。工作流中的某个项目处于某种状态，状态机知道如何通过将该项目置于不同的状态来对外部事件做出反应，此时会发生一些其他活动。

状态的概念对于应用程序“记住”系统的当前上下文并在新信息到达时做出正确反应非常有用。任何重要的应用程序都通过变量和条件将该概念嵌入到代码中。

因此，如果您的应用程序由于您所处的上下文而每次收到新信息时都必须做出不同的反应，您可以使用状态机对您的系统进行建模。一个例子是如何解释计算器上的按键，这取决于您当时正在处理的内容。

相反，如果您的计算不依赖于上下文而仅依赖于输入（例如将两个数字相加的函数），则您将不需要状态机（或者更好地说，您将拥有一个具有零状态的状态机）

有些人根据状态机设计整个应用程序，因为他们捕获了项目中需要记住的基本内容，然后使用一些过程或自动编码器使它们可执行。以这种方式编程需要一些范式机会，但我发现它非常有效。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top