表示条件调查问题列表的最佳数据结构是什么？

Question

在我工作的当前域中，我们可以发送包含问题列表的调查。在设计调查时，您可以为每个问题创建条件，以确定接下来要问的问题。问题可以有多个条件。有些问题可能根本没有任何条件。

所以一个例子可能是：

如果 Q1 的答案 > 5，则转到 Q3，否则转到 Q2。

使用 ID，我可以制作问题对象的列表或地图，但如果我想从头开始遍历以找出某人通过调查所采用的路径，这就不太好了。所以我想知道人们可能对另一种数据结构有什么建议来解决这个问题。

到目前为止，我考虑过树或有向无环图（具有条件边）。我还没有找到任何使用树根据动态表达式有条件地选择路径的好例子。

表示为树：

     Q1
    / \
   Q2  Q3
  / \   |
Q4  Q5  Q5
|    |  |
Q6  Q7  Q7

表示为 DAG：

     Q1
     /\
   Q2  Q3
  / \  /
Q4   Q5  
|    | 
Q6   Q7

Answer 1

数据结构将始终取决于问题域的细节。如果每个规则都是您显示的形式：if f(Q_n) then Qi else Qj，那就很简单了。每个问题都有该形式的关联 if。除非 Qi 和 Qj 可以是什么人为限制，否则您想要的数据结构是 DAG 或有向无环图。非循环部分是因为您可能永远不想让用户回到他们已经回答过的问题的“循环”。

DAG 的节点将是问题，每个节点将有 2、1 或零 out-edges。

表示 DAG 的方法有很多种，但您可能想要一些简单的方法。一个节点将是一个元组

(question, condition, trueChild, falseChild)

条件编码由您决定。只有一个继任者的问题没有问题。把对应的tuple

(question, TRUE, trueChild, null)

如果你想允许更复杂的规则，事情会变得更复杂，但上面的方案应该很简单，实施起来也很有趣。

使其健壮需要检查周期。

跟踪用户的历史记录将是从答案序列引导的根开始的遍历。使用用户的答案评估每个节点的条件并采取相应的分支。

最简单的方法可能是将节点存储在数组中，索引可能对应于（问题编号 - 1）。然后子指针可以是索引。

所以你的例子：

     Q1
     /\
   Q2  Q3
  / \  /
Q4   Q5  
|    | 
Q6   Q7

看起来像（在 C 中）

typedef struct node {
  int number; // Not absolutely needed, but probably handy.
  CONDITION condition; // up to you
  int trueChild, falseChild;
} QUESTION;

typedef QUESTION SURVEY[MAX_SURVEY_LENGTH];

#define EMPTY (-1)
#define INDEX(Number) ((Number) - 1)

SURVEY survey = {
  { 1, {...}, INDEX(2), INDEX(3) },
  { 2, {...}, INDEX(4), INDEX(5) },
  { 3, True, INDEX(5), EMPTY },
  { 4, True, INDEX(6), EMPTY },
  { 5, True, INDEX(7), EMPTY },
  { 6, N_A, EMPTY, EMPTY },
  { 7, N_A, EMPTY, EMPTY },
}

现在假设您有一串某人做出的回复。遍历 DAG 以找到他们看到的问题的算法是：

LIST *get_questions(int question_number, LIST *responses)
{
  LIST *result = create_empty_list();
  int nextIndex = INDEX(question_number);
  while (nextIndex != EMPTY && !is_empty(responses)) {
    QUESTION *q = survey + nextIndex;
    add(result, q);
    nextIndex = get_condition_value(&q->condition, first(responses))) 
        ? q->trueChild 
        : q->falseChild;
    responses = all_but_first(responses);
  }
  return result;
}

表示条件调查问题列表的最佳数据结构是什么？

What is the best data structure to represent a conditional list of survey questions?

tree

directed-acyclic-graphs

data-structures