graph-theory - Is a statechart / finite state machine suitable for modelling a questionnaire

Question

I'd like model the above questionnaire which I believe is a directed acyclic graph.

The two libraries I've been looking at are:

A couple of the issues I have are:

The questionnaire relies on previous states e.g. the answers to previous questions are used to transition to another state (question). Am I right in thinking that "external state" could solve this problem?
If I'm at Q6 and I want to transition to the previous question, then depending on the previous answers, this could be either Q1, Q4, or Q5. I think I could use a stack to push each state as the questionnaire progresses and then pop to get back to a previous state.

Does this all sound feasible or is there a better way to model this problem?

score 1 · Accepted Answer

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

简而言之，您的图表保持不变，并在每次转换时添加了对扩展状态的更新。例如，您的扩展状态可能是{A1, A2. ..., A6, H}，其中Ax代表的答案Qx，并且H是机器经历的状态历史。当您从 Q1 过渡到 Q2 时，您还会更新A1到答案H和[A1]. 你对所有Qs 都这样做。到达 Q6 后，您拥有编写警卫所需的所有信息，根据先前状态的历史和答案决定在哪里转换。

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

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

您会在那里找到一个与您刚刚描述的问题非常相似的演示。这也是一个多步骤问卷，复杂的是它包括错误路径。

score 0 · Accepted Answer

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

将其表示为状态机的典型第一种天真方式（也是我最初的方式）使每个问题进入其自己的状态，每个状态在状态机中仅表示一次。使用状态图，您可以将问题 4 和 5 提取为复合状态，这样当 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）表示。这里的解决方案是从状态本身的名称中分离出来，并在每个状态中声明要显示哪个问题，通常通过一个操作或更改某个变量的方式。下面我定义了一个数据元素，状态图更新为要显示的正确问题的名称。

<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>

这种解耦使更改状态图变得更容易，在不改变状态图的每个用户的情况下移动事物。相反：依赖于状态图/状态机之外的状态名称会导致状态名称本身成为状态机的 API，这意味着它不能轻易更改。

score 0 · Accepted Answer

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

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

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

score 0 · Accepted Answer

与对 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，因为它通过转换到针对特定子状态的状态来记住“它来自哪里”。

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

score 0 · Accepted Answer

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

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

为了证明它确实可以工作，我在Rosmaro中实现了它并推送到这个存储库 - https://github.com/lukaszmakuch/so-questionnaire。您可以在此处的编辑器中查看图表的外观 - 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'
$

graph-theory - Is a statechart / finite state machine suitable for modelling a questionnaire

5 回答 5

Related

Reference