0

我目前正在编写一个算法来通过兼容性分数匹配用户。因此，每个用户与其他每个用户都有一个兼容性分数。目标是最大化总兼容性分数。我正在使用munkres python 包来获取索引，然后过滤重复项。（即如果 user1 与 user2 匹配，我们删除与 user2 和 user1 的匹配）。

这是一个示例矩阵：（在用户无法与自己匹配的地方禁止使用。）

matrix = [[DISALLOWED, 2, 5, 7, 13, 10],
         [2, DISALLOWED, 25, 13, 5, 14],
         [5, 25, DISALLOWED, 21, 100, 17],
         [7, 13, 21, DISALLOWED, 70, 2],
         [13, 5, 100, 70, DISALLOWED, 200],
         [10, 14, 17, 2, 200, DISALLOWED]]

这是我尝试过的。它适用于我给出的这个较小的矩阵示例，但没有给出较大数据集的最佳分数。我知道总分不是最优的，因为非优化算法（简单地对分数进行排序并按顺序匹配每个用户）会产生更高的分数。

def optimize(matrix):
    optimal_matrix = make_cost_matrix(matrix, lambda cost: (sys.maxsize - cost) if
                                    (cost != DISALLOWED) else DISALLOWED)

    m = Munkres()
    indexes = m.compute(optimal_matrix)
    
    matches = []
    for row, column in indexes:
        value = matrix[row][column]
        match = [row, column, value]
        matches.append(match)

    matches.sort(key=thirdValue, reverse=True)

    seen = []
    total = 0
    for match in matches:

        if match[0] not in seen and match[1] not in seen:
            total += match[2]
            seen.append(match[0])
            seen.append(match[1])
    print(total)

是否有某个矩阵会破坏我的代码？任何帮助或指示将不胜感激。

4

1 回答 1

0

匈牙利算法适用于“二分”图，但您没有二分图。二分图是其中您有两组不同的节点的图。例如：为工人分配工作。集合内的节点不相互连接；可以将工人分配给工作，也可以将工作分配给工人，但工人既没有分配给工人，也没有分配给工作。在您的情况下，您正在尝试将用户分配给其他用户。也就是说，您只有一套，而不是两套。

通过标记对角线DISALLOWED，您可以阻止用户与他们自己匹配，但您不会阻止用户与多个其他用户匹配。例如，只有四个具有相同兼容性的用户：
一个 乙 C D
一个 0 0 0
乙 0 0 0
C 0 0 0
D 0 0 0

A 匹配 C
B 匹配 D
C 匹配 B
D 匹配 A

是匈牙利算法的有效结果，但不适用于您的情况。我不知道这是正在发生的事情，但它可能会发生，所以你需要使用不同的算法。

于 2021-02-22T03:30:20.220 回答