如何存储复杂的状态机

Question

我需要在 Python 中实现一个相当复杂的状态机。到目前为止，我尝试过的所有内容都非常混乱，有一百万个循环和 if 语句。我有大约 100 个节点，每个节点可以有多个传入和传出弧。

首先，我已经有了状态机的设计，这不是什么需要学习的东西。其次，我不想使用任何像 scikit-learn 这样的包。显然，pandas和numpy都可以，但是我想在Python中勾勒出来，然后将其引入C#，所以不能太依赖Python包。

我也尝试过使用图，但感觉不太对，因为有循环，遍历算法取决于决策，而不是成本。我也在考虑编写一种领域特定语言，但在我投入大量时间之前，我想确保我已经做了一些研究。

用于存储状态机的典型数据结构是什么？它需要能够考虑循环和汇。 DSL 是正确的选择吗？如果是这样，你有什么指示吗？

谢谢！

p.s 它看起来像这样。

来源：Figures - uploaded by Alex Capaldi from referenced research An AgentBased Modeling Approach to Determine Winter Survival Rates of American Robins and Eastern Bluebirds

Answer 1

状态机的最简单表示是图形。

在大多数语言中，您可以使用数组，其索引代表状态，其元素是到其他状态的转换列表。将 human-readable 状态名称与每个索引相关联以支持调试通常很方便。转换需要两部分：转换条件和目标状态数。

我们通过命名我们需要的图形构造函数和元素，在 python 中设计了一个“内部”DSL。我们可以定义一个状态机（原谅我的Python，我不是专家）：

   Class Transition  // defines a single transition
      def __init__(self, condition, target):
        self.condition = condition // store a python lambda here
        self.target = target // may be a state name (optimize to a state index)

   Class State
      def __init__(self, state_name, transitions):
        self.state_name=state_name   // text name of state
        self.transitions=transitions // a "set" (array) of transitions

   Class StateMachine:
      def __init__(self, states):
        self.states = states  // a "set" (array) of named states
      def AddState(self, state):
        self.states.append(state) 
      def compile(self):
        // replaces state names with state indexes; left as reader exercise

我们可以构建一个状态机来识别典型的标识符名称（与正则表达式“[A-Z][A-Z0-9]*”相同）：

    MyIdentifierRecognizer = StateMachine([])
    MyIdentifierRecognizer.AddState(State("ScanFirstIdentifierCharacter",
          [Transition(lambda x: IsLetter(x),"ScanNthIdentifierCharacter"),
           Transition(lambda x: not(IsLetter(x)),"NotAnIdentifier)]))
    MyIdentifierRecognizer.AddState(State("ScanNthIdentifierCharacter",
          [Transition(lambda x: IsLetterOrDigit(x),"ScanNthIdentifierCharacter"),
           Transition(lambda x: not(IsLetterOrDigit(x)),"EndOfValidIdentifier)])) 
    MyIdentifierRecognizer.AddState(State("NotAnIdentifier",[])) // no further transitions posssible
    MyIdentifierRecognizer.AddState(State("EndOfValidIdentifier",[])) // no further transitions possible

运行状态机很简单。我们先设置一个current_state到初始状态的状态机：

     current_state = "ScanFirstIdentifierCharacter"

然后给定一个输入字符：

     character = ...

我们在状态机中找到current_state，然后处理转换寻找满足变化的current_state:

     for s in StateMachine.states   // find the actual state matching current_state
         if s.name == current_state
            state = s
            break
     for t in state.transitions // process all transitions (assumed mutually exclusive)
          if t.condition(character)
             current_state=t.target
             break  // adding this line means "take the first valid transition"

您可以在定义状态机后通过运行一个小“编译器”提高效率，它用数组索引替换文本状态名称。那么状态查找可以直接数组索引。

如果解释此状态机不够快，您可以将各个状态编译成它们等效的目标语言代码并导入该代码。如果做得好，这实际上会产生非常快的状态机。

[注意：作者在我完成这个回答后在他的问题中添加了一个示例流程图。我让他用这种状态机符号来转换他的流程图。

OP 最初提出的与决策树相关的问题引发的另一个考虑：如何存储转换谓词？在我这里的版本中，它们是“不透明的”Python lambda，这将满足一些需求。如果 OP 想以 non-opaque 的方式存储复杂的转换谓词，他将需要“转换”字段来包含表示感兴趣的布尔条件的抽象语法树。有关如何解析（布尔）和执行布尔表达式的详细信息，请参见

如何存储复杂的状态机

How to store a complex state machine

python

dsl

graph

decision-tree