algorithm - java - 有效地比较两组对象

Question

我有两组对象，每组包含 4 个对象。目标是计算这两组之间的相似度。两个对象之间的比较结果是一个 int 数字。这个数字越小，对象就越相似。这些对象在组内的顺序与组相等性无关。

所以我必须做的是将第 1 组的每个对象与第 2 组的每个对象进行比较，这将给我 16 个不同的对象之间的比较结果。我将这些存储在一个名为 costs 的 4x4 int 表中。

int[][] costs= new int[4][4];
for(int i=0;i<4;i++){
     for(int j=0;j<4;j++){
         costs[i][j]=compare(objectGroup1[i],objectGroup2[j]);
      }
 }

现在我有 4 组 4 个比较结果，我必须从每组中选择一个结果，以便将它们相加并计算组之间的总距离度量。这就是我卡住的地方。我必须尝试四个的所有组合并获得最小总和，但存在仅使用一次对象的限制。

示例:如果要添加的四个值中的第一个是 objectGroup1[1] - objectGroup2[1] 之间的比较结果，那么我不能在这个四人组中使用使用 objectGroup1[1] 的任何其他比较结果，同样如此对于 objectGroup2[1]。

有效示例:group1[1]-group2[2]、group1[2]-group2[1]、group1[3]-group2[3]、group1[4]-group2[4]---->每个组中的每个对象只出现一次

我可以在这里使用什么样的算法？

Answer 1

听起来您正在尝试查找 permutation将项目配对时，第 1 组的项目与第 2 组的项目最相似。

Eric Lippert 在 producing permutations 上发表了一系列精彩的博文.所以基本上你所要做的就是迭代它们，通过配对项目计算分数，并返回最好的分数。基本上只是 Zip-ing 和 MinBy-ing:

groupSimilarity =
    item1.Groups

    // (you have to implement Permutations)
    .Permutations()

    // we want to compute the best score, but we don't know which permutation will win
    // so we MinBy a function computing the permutation's score
    .MinBy(permutation =>
        // pair up the items and combine them, using the Similarity function
        permutation.Zip(item2.Groups, SimilarityFunction)
        // add up the similarity scores
        .Sum()
     )

以上代码是 C#，以“Linqy”函数式风格编写(如果您对此不熟悉，请见谅)。 MinBy是 MoreLinq 中的一个有用函数, Zip是标准的 Linq 运算符。