实现类似调查程序的算法

Question

我想用Java创建一个程序，它将向用户询问一些问题并报告一些结果。这很像一个调查。为了更好地解释这个问题，考虑下面的例子:假设目前有4个问题，例如Qa, Qb, Qc和Qd。每个问题都有多个可能的选项:

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

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

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

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

此外，还有一些可用的结果将根据用户在上述问题中的回答来报告。我们假设有5个这样的结果，分别是R1, R2, R3, R4和R5。每个结果都有一些特征。这些特点确实是对上述问题的回答。更准确地说应该是:

=> R1的特征是{Qa = a4, Qb = b2, Qc = c2, Qd = d1}的集合这说明R1通过a1选项与Qa相关，Qb通过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}

=>然后尝试三个问题的组合，以此类推…

显然，上面的算法在处理大量问题时会非常慢。是否有任何已知的算法或启发式比上述算法更有效?

Thanks in advance

Answer 1

"Only" 30 Questions?
那么下面这个"愚蠢"的算法可能会比任何高度"智能"和复杂的算法都要快。

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

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

运行时间是size of characteristics * size of questions，而你所描述的算法可以有指数运行时间，最重要的是，无论是编程还是执行(由于分支错误预测的影响)都要复杂得多