调查流程的算法

Question

我必须编写一个工具，允许业务用户创建调查。 如果填写调查的人以特定方式回答了前面的问题，则只应询问一些问题。但是无论选择什么答案，都应该显示一些问题。

到目前为止，我想出了一个图形结构，这是它的外观的理论示例:

(我只有图论的基础知识所以请原谅用词可能不够准确)

A、B、C等轮次代表问题，链接上的值代表访问问题的前提。

NULL 表示没有前提条件，像“0”或“1”这样的值表示前一个问题必须有值为“0”或“1”的答案才能显示该问题。

具体例子: 我在 A 轮。我有两个可能的答案。第一个的值为“0”。第二个，值为“1”。如果我选择值为“0”的答案，那么我将转到问题 B。

我现在在B轮，不管答案是什么，我都会去E轮，因为没有前提条件。

E 是叶节点，所以我回到 B。B 有另一个没有前提条件的子节点 F，所以我转到问题 F。让我们在那里结束流程。

我也可以有一个有多个前提条件的问题。这由问题 N 表示。只有当问题 F 的答案为“5”和问题 I 的答案为“DE”时才能访问它。在这种情况下，在回答问题 F 后，由于在此状态下只有一个前提条件有效，我们将回到图中，只有在回答问题 I 的“DE”后，我们才能转到问题 N。

我的问题是关于用于此类调查的算法。是否有涵盖此用例的现有算法？我认为这看起来像 DFS 图遍历，但条件让我怀疑。

另外，我是不是把事情复杂化了，可以用更简单的方式表达吗？ 在这个阶段我真的很想得到一些建议。

感谢您的帮助!

Answer 1

根据您的描述，我会将您提出的图表的概念稍微更改为以下内容:

• 将其制成有向图(即每条弧都有源和目标的图)。
• 每个问题有一个节点和每个答案有一个节点(每个问题的每个答案都是一个不同的节点)。每个问题节点需要有一个标志来判断它是“问题类型”还是“答案类型”，还有一个标志来标记它是否被访问过。
• 每个问题节点都将连接到它的每个答案(方向 [问题] -> [答案])。
• 每个答案前提条件(“要达到问题 B，您需要在问题 A 中回答 0”)将由从一个答案(节点 [问题 A 的答案 0])到它“解锁”的问题(节点[问题 B])。如果一个问题需要多个答案，它将有多个传入弧。
• 每个问题的前提条件(“要达到问题 D，您需要回答问题 A，无论选择如何”)都将由从一个问题(节点 [问题 A])到另一个问题(节点 [问题 D)的弧线表示]).

然后算法将遵循以下几行:

1. 有一堆待处理节点P，它最初包含与调查的第一个问题对应的节点。
2. 弹出 P 的第一个元素 Q，它应该始终是一个问题节点，并将其标记为已访问。
3. 获取 Q 的后继列表(通过外向弧连接到当前节点的节点)并将其拆分为“答案后继”、QtoA，以及“问题接类人”，QtoQ。
4. 将 QtoQ 中的所有元素添加到 P(如果有任何方法可以对这些元素进行排序，例如通过某些“问题 ID”，请确保它们是以第一个元素结束于堆栈顶部的方式添加)。
5. 提出问题(您甚至可以将问题存储在图中并从中检索您需要的所有信息)。
6. 从QtoA中获取所选答案A的节点，将其标记为已访问并依次收集其所有后继者列表，AtoQ.
7. 对于 AtoQ 中的每个节点 R(同样，如果有的话，考虑在这里排序)，如果 R 的所有前辈(即通过传入弧连接到 R 的节点)被标记为已访问，然后将 R 添加到 P。
8. 如果P中有任何节点，则转到步骤2。

这应该会重现您描述的顺序。如果你想有几个可能的解锁答案的能力(例如“如果你回答 1 或 2 从 A 你会去 B”)你需要做一些更多的调整(即，在第 6 步你需要更换R 的“答案类型”前辈的“已访问”检查类似于“R 可通过 R")，但它应该仍然可以正常工作。

也许您已经知道了，但是如果您有兴趣使用图作为您唯一的数据源(可能是也可能不是这种情况)，您可能会发现有趣的面向图的数据库，例如 Neo4j .