实现类似调查程序的算法

Question

我想用 Java 创建一个程序，它会向用户提出一些问题并报告一些结果。这很像一项调查。为了更好地解释问题，请考虑以下示例:假设当前有 4 个可用问题，例如 Qa、Qb、Qc 和 Qd。每个问题都有许多可能的选项:

=> 问题 A 有 4 个可能的选项 a1、a2、a3 和 a4。

=> 问题 B 有 3 个可能的选项 b1, b2 和 b3

=>问题C有5个可能的选项c1,c2,c3,c4和c5

=> 问题 D 有 2 个可能的选项 d1 和 d2

此外，还有一些可用的结果将根据用户在上述问题中的回答进行报告。假设有 5 个这样的结果，分别称为 R1、R2、R3、R4 和 R5。每个结果都有许多特征。这些特性实际上是对上述问题的回答。更准确地说:

=> R1的特征是{Qa=a4,Qb=b2,Qc=c2,Qd=d1}的集合这表示 R1 通过 a1 选项与 Qa 相关，通过 b2 选项与 Qb 相关，依此类推

=> R2: {Qa = a3, Qb = b3, Qc = c3, Qd = d2}

=> R3: {Qa = a4, Qb = b1, Qc = c1, Qd = d2}

=> R4: {Qa = a2, Qb = b2, Qc = c5, Qd = d1}

=> R5: {Qa = a1, Qb = b3, Qc = c4, Qd = d2}

假设用户 U 提供了以下问题的答案{Qa = a4, Qb = b1, Qc = c1, Qd = d1}

该程序的目的是报告更接近用户答案的​​结果以及接近程度的百分比。例如，由于没有任何结果与用户回答的结果 100% 匹配，因此程序应报告尽可能多的答案匹配的结果(高于某个阈值，例如 50%)。在这种特定情况下，程序应报告以下结果:

=> R3 有 75%(因为 4 个问题有 3 个匹配项)

=> R1 有 50%(因为 4 个问题有 2 个匹配项)

请注意，R4 有一个匹配项(因此为 25%)，而 R2 和 R5 根本没有匹配项(因此为 0%)。实现上述程序的主要问题是有很多问题(大约 30 个)，每个问题都有很多答案(每个问题有 3-4 个答案)。我不知道可以检索更接近用户答案的​​结果的有效算法。请注意，这些结果的存储方式根本不重要。您可以假设结果存储在关系数据库中，并且使用 SQL 查询来检索它们。

我能想到的唯一解决方案是执行详尽搜索，但这根本没有效率。换句话说，我正在考虑执行以下操作:

=> 首先尝试检索与用户答案完全匹配的结果:{Qa = a4, Qb = b1, Qc = c1, Qd = d1}

=> 如果不存在结果，则更改问题的选项(例如 Qa)并重试。例如尝试:{Qa = a1, Qb = b1, Qc = c1, Qd = d1}

=> 如果仍然没有，则尝试 Qa 的其余可能选项，例如 a2、a3

=> 如果仍然没有任何结果，则给 Qa 初始用户答案(即 a4)，然后转到 Qb 做类似的事情。例如尝试这样的事情:{Qa = a4, Qb = b2, Qc = c1, Qd = d1}

=> 如果在对所有问题一一尝试所有可能的选项后有任何结果，请尝试更改问题组合的选项。例如尝试同时更改两个问题的选项(例如 Qa 和 Qb):{Qa = a1, Qb = b2, Qc = c1, Qd = d1}

=> 然后尝试三个问题的组合等等......

显然上述算法在处理大量问题时会非常慢。有没有比上述算法更有效的已知算法或启发式算法？

提前致谢

Answer 1

“只有”30 个问题？
那么下面的“愚蠢”算法可能比任何高度“智能”和复杂的算法都要快。

iterate over characteristics
    score = 0
    iterate over questions
        if questions's answer is right in current characteristic
            score++

然后添加一个跟踪最大值和匹配特征的变量，您就设置好了。

运行时间是特征大小 * 问题大小，而您所描述的算法可能具有指数运行时间，最重要的是编程和执行都复杂得多(由于效果作为分支预测错误)