16

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

我已经阅读了关于使用状态机实现的解析器，但想了解一些需要作为状态机实现的问题。

4

15 回答 15

15

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

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

这个输入流的例子：解析时的一些文本文件，正则表达式的字符串，player entered room游戏AI等事件等。

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

于 2008-09-02T21:40:38.627 回答
10

一个很好的资源是这个免费的状态机电子书。我自己的快速回答如下。

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

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

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

  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很慢，所以我需要等待响应。理想情况下，当我发送消息时，我使用一个函数，然后我不在乎会发生什么，但是我的程序必须在某个地方监视线路并发送和响应这些消息，将它们分解成更小的部分，并将接收到的消息重新组合成最后的消息。

于 2008-09-02T20:57:59.960 回答
2

TCP 等有状态协议通常表示为状态机。但是，您很少需要将任何东西实现为适当的状态机。通常你会使用一个损坏，即让它在一个状态下执行重复动作，在它转换时记录数据，或者在保持在一个状态下交换数据。

于 2008-09-02T20:45:59.007 回答
1

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

于 2008-09-02T20:46:19.177 回答
1

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

于 2008-09-02T20:46:47.943 回答
1

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

于 2008-09-02T20:47:12.047 回答
1

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

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

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

于 2008-09-02T20:48:30.157 回答
1

游戏中的 AI 经常使用状态机来实现。帮助创建更容易构建和测试的离散逻辑。

于 2008-09-02T20:50:44.580 回答
1

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

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

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

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

于 2008-09-02T20:50:50.977 回答
1

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

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

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

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

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

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

于 2008-09-02T20:53:35.917 回答
0

想到的事情是：

  • 机器人/机器操作……工厂里的那些机械臂
  • 模拟游戏，（模拟城市，赛车游戏等）

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

不过，我所知道的并不能归结为解析问题。

于 2008-09-02T20:49:59.060 回答
0

顺便说一句，您可以使用正确的尾调用来实现状态机，就像我在尾递归问题中解释的那样。

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

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

于 2008-09-02T20:56:37.513 回答
0

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

于 2008-09-02T20:58:00.647 回答
0

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

于 2008-09-02T21:01:21.480 回答
0

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

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

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

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

于 2008-09-15T14:04:42.247 回答