状态图/有限状态机是否适合对问卷进行建模

Question

我想对上面的问卷建模，我认为它是一个有向无环图。

我一直在寻找的两个库是：

我遇到的几个问题是：

调查问卷依赖于以前的状态，例如的答案以前的问题是用来过渡到另一个状态（问题）。我认为 "external state" 是对的吗能解决这个问题吗？
如果我在第 6 题，我想转到上一题，然后根据之前的答案，这可能是 Q1、Q4 或 Q5。我我想我可以使用一个堆栈来随着问卷的进行推送每个状态，然后弹出以返回到之前的状态。

这听起来可行吗？或者是否有更好的方法来模拟这个问题？

Answer 1

在这里回答问题的后半部分，关于弄清楚如何到达 Q4 和 Q5（暂时忽略 Q1 到 Q6）

将其表示为状态机的典型的第一种朴素方式（也是我最初的方式）使每个问题进入其自己的状态，每个状态在状态机中仅表示一次。使用状态图，您可以将问题 4 和 5 提取到 compound state 中，这样当 Q4AND5 处于活动状态时，正好有一个 Q4 或 Q5 处于活动状态：

<scxml>
  <state id="Q1"/>
  <state id="Q2"/>
  <state id="Q3"/>
  <state id="Q4AND5">
    <state id="Q4"/>
    <state id="Q5"/>
  </state>
  <state id="Q6"/>
</scxml>

然后从 Q3 到 Q4AND5 的转换将导致 Q4 或 Q5 激活，因为有保护转换。

<scxml>
  <state id="Q1">
    <transition event="answer" target="Q2"/>
  </state>
  <state id="Q2">
    <transition event="answer" target="Q3"/>
  </state>
  <state id="Q3">
    <transition event="answer" target="Q4AND5"/>
  </state>
  <state id="Q4AND5">
    <transition cond="if q1 == 'FOO' and q3 == 'BAR'" target="Q4"/>
    <transition cond="if q1 == 'BAR' and q3 == 'FOO'" target="Q5"/>
    <state id="Q4"/>
    <state id="Q5"/>
    <transition event="answer" target="Q6"/>
  </state>
  <state id="Q6"/>
</scxml>

从 Q6 返回将转到 Q4AND5，这将导致机器进入 Q4 或 Q5：

  <state id="Q6">
    <transition event="back" target="Q4AND5"/>
  </state>

现在，在修改问题以包括 Q1 到 Q6 的过渡后，很明显将每个问题建模为不同的状态并不能解决问题。这也不完全正确。大家想想，Q6有两种状态，一种是Q1到达Q6之后，一种是Q4AND5到达Q6之后。如果我们改为将这两个 Q6 分成两个不同的状态，那么很容易适应这个新的转变：

<scxml>
  <state id="Q1">
    <transition event="answer" target="Q6B" cond="q1 == 'BAZ'"/>
    ...
  </state>
  ...
  <state id="Q6A">
    <transition event="back" target="Q4AND5"/>
  </state>
  <state id="Q6B">
    <transition event="back" target="Q1"/>
  </state>
</scxml>

现在的问题是 Q6 由两个状态（Q6A 和 Q6B）表示。这里的解决方案是 decouple 与状态本身的名称，并且 declare 在每个状态中显示哪个问题，通常是通过一个动作或更改某些变量。下面我定义了一个 data 元素，状态图更新为要显示的正确问题的名称。

<scxml>
  <datamodel>
    <data id="question"> <!-- The name of the question to show -->
  </datamodel>
  <state id="Q1">
    <assign location="question" expr="'Q1'"/>
    <transition event="answer" target="Q6B" cond="q1 == 'BAZ'"/>
    <transition event="answer" target="Q2"/>
  </state>
  <state id="Q2">
    <assign location="question" expr="'Q2'"/>
    <transition event="answer" target="Q3"/>
    <transition event="back" target="Q1"/>
  </state>
  <state id="Q3">
    <assign location="question" expr="'Q3'"/>
    <transition event="answer" target="Q4AND5"/>
    <transition event="back" target="Q2"/>
  </state>
  <state id="Q4AND5">
    <transition event="answer" cond="if q1 == 'FOO' and q3 == 'BAR'" target="Q4"/>
    <transition event="answer" cond="if q1 == 'BAR' and q3 == 'FOO'" target="Q5"/>
    <transition event="back" target="Q3"/>
    <state id="Q4">
      <assign location="question" expr="'Q4'"/>
    </state>
    <state id="Q5">
      <assign location="question" expr="'Q5'"/>
    </state>
    <transition event="answer" target="Q6A"/>
  </state>
  <state id="Q6A">
    <assign location="question" expr="'Q6'"/>
    <transition event="back" target="Q4AND5"/>
  </state>
  <state id="Q6B">
    <assign location="question" expr="'Q6'"/>
    <transition event="back" target="Q1"/>
  </state>
</scxml>

这种解耦使得更改状态图变得更加容易，无需更改状态图的每个用户即可四处移动。相反：依赖 statechart/state 机器之外的状态名称会导致状态名称本身成为状态机的 API，这意味着它不能轻易更改。

Answer 2

我会使用 FSM 并记住 Map 或 js 对象中的状态来解决这个问题。然后你可以防止触发转换检查你保存在内存中的状态。

这是我会采用的实用解决方案，您可以使用 FSM 库，但我的建议还使用对象来保存答案。

是否有 FSM 的实现，其中转换可以采用外部状态？如果存在这样的事情，您可以在机器内部编写逻辑，但您必须手动记住答案（以使其成为通用解决方案）

Answer 3

这个问题的解决方案可以通过扩展状态机建模。您不一定需要分层的。您显示的状态和转换可以使用常规状态机处理，但 'memory' 部分可以使用扩展状态机正确处理。

简而言之，您的图形保持不变，只是在每次转换时对扩展状态进行更新。例如，您的扩展状态可以是 {A1, A2. ..., A6, H}，其中 Ax 代表 Qx 的答案，而 H 是机器经历过的状态的历史记录。当您从 Q1 过渡到 Q2 时，您还将 A1 更新为答案，并将 H 更新为 [A1]。您对所有 Q 都这样做。到达 Q6 时，您拥有编写守卫所需的所有信息，根据先前状态的历史记录和答案来决定转换到哪里。

因此，总结一下您的问题的答案：是的，可以有利地使用外部状态，在这种情况下，保存状态历史记录的堆栈将解决您的问题，正如您的直觉。当然，您也可以使用状态图库，因为状态图概括了扩展状态机。

作为附加组件，我还将自己的扩展状态机库添加到您已经提到的优秀库中：https://github.com/brucou/state-transducer。

你会find there a demo这与你刚才描述的问题非常相似。它也是关于一个多步骤问卷，复杂的是它包含错误路径。

Answer 4

现实世界的调查问卷需要将答案保存在某个地方，而这正是外部状态（如一组键值对）被证明有用的地方。由于称为状态爆炸的现象，任何将给定答案存储在图中（其中每个可能的值都是一个单独的节点）的尝试都会立即失败。

但是，获取先前给出的答案然后将它们与条件表达式一起使用以实现转换是一种逃生舱口。作为基于自动机编程的拥护者，我认为 IF 的使用在大多数情况下应该仅限于输入数据，并且不应在这种情况下检查外部状态一种方法，除非无法用合理的图形来表达所需的行为。

为了证明它确实可以工作，我在Rosmaro and pushed to this repository - https://github.com/lukaszmakuch/so-questionnaire. You can see what does the graph look like in the editor here - https://i.stack.imgur.com/uDkh5.png中实现了它。

这是一个完整的工作示例，支持：

阅读当前问题
正在回答当前问题
阅读给出的答案
回到上一个问题

工作原理如下：

git clone https://github.com/lukaszmakuch/so-questionnaire.git
cd so-questionnaire/
npm i
npm start
$ question()
'Q1'
$ answer('baz')
undefined
$ question();
'Q6'
$ answer('anything')
undefined
$ answers();
{ Q1: 'baz',
  Q2: null,
  Q3: null,
  Q4: null,
  Q5: null,
  Q6: 'anything' }
$ back()
undefined
$ question()
'Q1'
$ answer('foo')
undefined
$ question()
'Q2'
$ answer('test')
undefined
$ answers()
{ Q1: 'foo', Q2: 'test', Q3: null, Q4: null, Q5: null, Q6: null }
$ question()
'Q3'
$ answer('bar')
undefined
$ question()
'Q4'
$ answer('fuzz')
undefined
$ question()
'Q6'
$ back()
undefined
$ question()
'Q4'
$

Answer 5

与对 S4 和 S5 使用复合状态不同的方法是对 S6 使用复合状态：

<scxml>
  <state id="Q1">
    <transition event="answer" target="Q6_from_1" cond="q1 == baz" />
    <transition event="answer" target="Q2"/>
  </state>
  <state id="Q2">
    <transition event="back" target="Q1"/>
    <transition event="answer" target="Q3"/>
  </state>
  <state id="Q3">
    <transition event="back" target="Q2"/>
    <transition event="answer" cond="if q1 == 'FOO' and q3 == 'BAR'" target="Q4"/>
    <transition event="answer" cond="if q1 == 'BAR' and q3 == 'FOO'" target="Q5"/>
  </state>
  <state id="Q4"/>
    <transition event="back" target="Q3"/>
    <transition event="answer" target="Q6_from_4"/>
  </state>
  <state id="Q5"/>
    <transition event="back" target="Q3"/>
    <transition event="answer" target="Q6_from_5"/>
  </state>
  <state id="Q6">
    <state id="Q6_from_1"/>
      <transition event="back" target="Q1"/>
    </state>
    <state id="Q6_from_4"/>
      <transition event="back" target="Q4"/>
    </state>
    <state id="Q6_from_5"/>
      <transition event="back" target="Q5"/>
    </state>
  </state>
</scxml>

唯一的特殊状态是 Q6，因为它通过转换到针对特定子状态的状态来记住 "where it came from"。

这可以与 Q4 和 Q5 的复合状态的想法相结合。

状态图/有限状态机是否适合对问卷进行建模

Is a statechart / finite state machine suitable for modelling a questionnaire

graph-theory

state-machine

statechart