java - 递归方法的数学公式

Question

我需要实现当前公式。它用于对分类法中的节点进行评分。基本上，节点的分数取决于子节点的数量及其分数((nodes(h+1)) 是下一级节点的数量，Cl(concept) 是一组 child )。

在我的用例中，术语频率目前仅针对叶子定义。我已经实现了，但问题是当节点有 2 个子节点时，实现只会转到一侧。

对于给定的分类法:

     1
    / \
   2   3
   |   |
   4   17
  / \
 11 13

给出了频率:freq(11) = 3、freq(13) = 5 和 freq(17) = 10。当我尝试获取 node(1) 的分数时，结果是 0.0，因为递归不会进入后代 node(4)，它只检索 freq(17)，仅此而已。通常，结果应该是 7。

这里是实现:

public static float calcScore(int keyID, Map<Integer, Integer> frequencies, Map<Integer, Integer> subTaxonomy) {
    float res = 0f;
    int nodes = 0;
    if (frequencies.containsKey(keyID)) {
        return frequencies.get(keyID) + 0f;
    }

    for (Map.Entry<Integer, Integer> entry : subTaxonomy.entrySet()) {
        if (entry.getValue() - 1 == subTaxonomy.get(keyID)) {
            nodes++;
            res += calcScore(entry.getKey(), frequencies, subTaxonomy);
        }
    }
    return 1 / nodes * res;
}

注意:

subTaxonomy - 存储 nodeID 及其在分类法中的级别

frequencies - 存储叶节点的频率。

我还在 Ideone 创建了一个片段:Source

我应该如何编辑代码，以便它遍历给定节点的所有子节点？

更新

所以现在，在更新的源代码中，它遍历了整个分类，但结果仍然是 0.0。

Answer 1

你的问题出在这行代码

if (entry.getValue() - 1 == subTaxonomy.get(keyID)) {

树的左侧部分不符合您的预期约定，即 childs id(不是树的叶子)遵循公式 childs id = parents id - 1

我建议更改您的实现，包括在您的分类中使用 parents id 而不是 node level。级别可以在递归期间计算并作为另一个参数传递。

新签名可能如下所示:

public static float calcScore(int keyID, Map<Integer, Integer> frequencies, Map<Integer, Integer> subTaxonomy, int level)

此外，如果 level 信息对您的最终结果没有帮助，您还可以考虑从代码中删除它!