匈牙利匹配

不带权重的二分图匹配

算法核心

把冲突节点的原先匹配的左节点重新连接到它的未被匹配的右节点，不断递归找到空闲的右节点；
如果不存在空闲右节点，则新的左节点不能连接到该冲突节点上，必须连接其他节点。

代码示例

def main():
    count = 0
    m, n, l = input().split(' ')
    m = eval(m)
    n = eval(n)
    l = eval(l)
    map = {}                          # 记录每个左节点匹配的所有右节点
    owner = [-1 for i in range(n+1)]  # 记录右节点匹配的左节点

    # 读入每个节点的链接关系，存到map里
    for _ in range(l):
        x, y = input().split(' ')
        x = eval(x)
        y = eval(y)
        if x not in map:
            map.setdefault(x, [y])
        else:
            map[x].append(y)
    # 
    for left in map:
        used = [False for i in range(n+1)]  # 记录当前左节点遍历过的右节点
        if find(left,map,used,owner): # 表示该右节点是空闲节点，或者可以通过交换空闲出来
            count += 1

    print(count)

def find(left,map,used,owner):
    for right in map[left]:
        if not used[right]:
            used[right] = True  # 标记一下，以后的就不再选这个点。
            # owner[right] < 0 表示该右节点是空闲节点。
            # find(owner[right],map,used,owner) 为True 表示该节点可以通过交换空闲出来。
            if owner[right] < 0 or find(owner[right],map,used,owner):
                owner[right] = left
                return True
    return False

if __name__ == '__main__':
    main()

相关题目：P3386 【模板】二分图最大匹配

带权重的二分图匹配

算法步骤

1. 对于一个代价矩阵，先把每一行减去本行最小值，每一列减去本行最小值。
2. 用最少的直线（横线或竖线）覆盖矩阵中的全部0元素。如果直线数量等于矩阵的秩，则找到最佳的指派方案；否则需要不断调整，直到直线数量等于矩阵的秩。
3. 每个0元素即为独立的指派任务

算法核心

第二步是算法核心，主要包含两个问题

如何用最少的直线覆盖矩阵中的全部0元素

【本节图片来自超详细！！！匈牙利算法流程以及Python程序实现！！！通俗易懂】

1. 找到0元素最少的行，标记第一个，并且把该行和该列都标记，直到没有0元素
   

2. 对没有独立0元素的行打勾；对打勾的行所含0元素的列打勾；对所有打勾的列中所含独立0元素的行打勾。
   

如何调整矩阵

【本节图片来自匈牙利算法原理与Python实现】

1. 在上一步中划过的线记为marked_rows和marked_cols，找到划线之外的元素的最小值
   

2. 划线之外的元素 - 最小值
   

3. marked_rows和marked_cols重叠的元素 + 最小值
   

返回调整后的矩阵

代码实例

【代码来自于匈牙利算法原理与Python实现】在此基础上添加中文注释以方便理解。

import numpy as np

def min_zero_row(zero_mat, mark_zero):
    '''
        1）找到零元素最少的行，以及该行第一个零元素，记录其坐标(min_row[1], zero_index)
        2）将该元素的行和列全部赋为False
    :param zero_mat:  Bool矩阵
    :param mark_zero: 存储标记的0元素的list
    :return: 没有返回值，直接修改bool矩阵
    '''
    '''
    The function can be splitted into two steps:
    #1 The function is used to find the row which containing the fewest 0.
    #2 Select the zero number on the row, and then marked the element corresponding row and column as False
    '''

    # Find the row
    min_row = [99999, -1]

    # 找到零元素最少的行，记为min_row= [0元素个数， 行号]
    for row_num in range(zero_mat.shape[0]):
        if np.sum(zero_mat[row_num] == True) > 0 and min_row[0] > np.sum(zero_mat[row_num] == True):
            min_row = [np.sum(zero_mat[row_num] == True), row_num]

    # Marked the specific row and column as False
    # np.where()返回零元素最少的行中，第一个零元素的下标
    zero_index = np.where(zero_mat[min_row[1]] == True)[0][0]
    # 存储标记0的位置
    mark_zero.append((min_row[1], zero_index))
    # 该标记0元素的这一行和这一列全部置为False
    zero_mat[min_row[1], :] = False
    zero_mat[:, zero_index] = False

def mark_matrix(mat):
    '''
    模拟划线过程，具体步骤为
    # 2-1 把所有零元素全部标记
    # 2-2 计算最小画线次数，即marked_rows为划横线，marked_cols为划竖线
        1）标记不包含被标记的0元素的行，并在non_marked_row中存储行索引；
        2）搜索non_marked_row元素，并找出相应列中是否有未标记的0元素；【找出未标记的独立0元素所在的行，加到non_marked_row，*打勾*】
        3）将列索引存储在marked_cols中；【上述行中把独立0元素包含的列都marked，*打勾*，这是之后要划的竖线】
        4）比较存储在marked_zero和marked_cols中的列索引；【4、5步是找出（3）中划的列线包括的marked_0元素，把这行加到non_marked_row，*打勾*】
        5）如果存在一个匹配的列索引，那么相应的行索引就会被保存到non_marked_rows中；
        6）接下来，不在non_marked_row中的行索引被保存在marked_rows中
    :param mat:
    :return: (marked_zero, marked_rows, marked_cols)
    【返回没有打勾的行，和打勾的列】
    '''


    # Transform the matrix to boolean matrix(0 = True, others = False)
    # 原矩阵中元素为0的地方标记为True，其他都为False
    cur_mat = mat
    zero_bool_mat = (cur_mat == 0)
    zero_bool_mat_copy = zero_bool_mat.copy()

    # Recording possible answer positions by marked_zero
    # marked_zero 记录了标记0的位置，按顺序存储
    marked_zero = []
    # 模拟划线过程
    while (True in zero_bool_mat_copy):
        # 每执行一次min_zero_row()函数
        # 就找到零元素最少的那一行，找到该行第一个零元素
        # 将这个零元素的行和列全部置为False
        # 直到所有零元素都被标记过
        min_zero_row(zero_bool_mat_copy, marked_zero)

    # Recording the row and column indexes seperately.
    # 记录被标记过的行和列（也就是划过线的行和列）
    marked_zero_row = []
    marked_zero_col = []
    for i in range(len(marked_zero)):
        marked_zero_row.append(marked_zero[i][0])
        marked_zero_col.append(marked_zero[i][1])
    # step 2-2-1

    # 找到没被标记过的行（即没有独立0元素的行）
    non_marked_row = list(set(range(cur_mat.shape[0])) - set(marked_zero_row))

    marked_cols = []
    check_switch = True
    while check_switch:
        check_switch = False
        for i in range(len(non_marked_row)):
            row_array = zero_bool_mat[non_marked_row[i], :]
            for j in range(row_array.shape[0]):
                # step 2-2-2
                # 找到没被标记的行中，是否有没被标记的0元素（也就是被迫被划线经过的列）
                # 在没有独立0元素的行中，找到所含0元素的列，加入到marked_cols中
                if row_array[j] == True and j not in marked_cols:
                    # step 2-2-3
                    marked_cols.append(j)
                    check_switch = True
        # 对所有marked_cols中，独立的0元素所在的行取出来加到non_marked_row中
        for row_num, col_num in marked_zero:
            # step 2-2-4
            # 前面标记的独立0元素出现在独立0元素所在的列上
            if col_num in marked_cols and row_num not in non_marked_row:
                # step 2-2-5
                non_marked_row.append(row_num)
                check_switch = True

    # step 2-2-6
    marked_rows = list(set(range(mat.shape[0])) - set(non_marked_row))
    # 最后划线最少的方式是把打勾的列和没打勾的行划出来
    return (marked_zero, marked_rows, marked_cols)


def adjust_matrix(mat, cover_rows, cover_cols):
    '''
    对矩阵进行调整：具体做法为：
        1）找到未被标记的元素中的最小值
        2）未被标记的元素 - 最小值
        3）标记的行和列中相交的元素 + 最小值
    :param mat: 原先操作过的矩阵
    :param cover_rows:  标记的行
    :param cover_cols:  标记的列
    :return: 调整后的矩阵
    '''
    # 找到未被标记的行和列中的最小值
    cur_mat = mat
    non_zero_element = []

    # Step 4-1 Find the minimum value
    for row in range(len(cur_mat)):
        if row not in cover_rows:
            for i in range(len(cur_mat[row])):
                if i not in cover_cols:
                    non_zero_element.append(cur_mat[row][i])

    min_num = min(non_zero_element)

    # Step4-2  未标记的元素 - 最小值
    for row in range(len(cur_mat)):
        if row not in cover_rows:
            for i in range(len(cur_mat[row])):
                if i not in cover_cols:
                    cur_mat[row, i] -= min_num

    # Step 4-3 标记的行和列 相交的元素 + 最小值
    for row in range(len(cover_rows)):
        for col in range(len(cover_cols)):
            cur_mat[cover_rows[row], cover_cols[col]] = cur_mat[cover_rows[row], cover_cols[col]] + min_num

    return cur_mat

def ans_calculation(mat, pos):
    '''
    计算最小代价
    :param mat: 原成本矩阵
    :param pos: 指派的元素位置
    :return: 最小代价
    '''
    total = 0
    ans_mat = np.zeros((mat.shape[0], mat.shape[1]))
    for i in range(len(pos)):
        total += mat[pos[i][0], pos[i][1]]
        ans_mat[pos[i][0], pos[i][1]] = mat[pos[i][0], pos[i][1]]
    return total, ans_mat


def hungarian_algorithm(mat):
    dim = mat.shape[0]
    cur_mat = mat

    # Step 1 - Every column and every row subtract its internal minimum
    # 每一行-该行最小值，每一列-该列最小值
    for row_num in range(mat.shape[0]):
        cur_mat[row_num] = cur_mat[row_num] - np.min(cur_mat[row_num])

    for col_num in range(mat.shape[1]):
        cur_mat[:, col_num] = cur_mat[:, col_num] - np.min(cur_mat[:, col_num])

    zero_count = 0
    # 用横线或者竖线标记出所有为0的元素，用最少线的次数为zero_count
    # 当zero_count=矩阵的秩时，得到最终指派
    # 否则要调整当前矩阵
    while zero_count < dim:
        # Step 2 & 3
        ans_pos, marked_rows, marked_cols = mark_matrix(cur_mat)
        zero_count = len(marked_rows) + len(marked_cols)

        if zero_count < dim:
            cur_mat = adjust_matrix(cur_mat, marked_rows, marked_cols)

    return ans_pos

def main():
    # The matrix who you want to find the maximum sum
    cost_matrix = np.array([[7, 6, 2, 9, 2],
                            [6, 2, 1, 3, 9],
                            [5, 6, 8, 9, 5],
                            [6, 8, 5, 8, 6],
                            [9, 5, 6, 4, 7]])

    ans_pos = hungarian_algorithm(cost_matrix.copy())  # Get the element position.
    ans, ans_mat = ans_calculation(cost_matrix, ans_pos)  # Get the minimum or maximum value and corresponding matrix.
    # Show the result
    print(f"Linear Assignment problem result: {ans:.0f}\n{ans_mat}")

if __name__ == '__main__':
    main()

参考

1. 匈牙利匹配算法_学习笔记_Python编程实现
2. 超详细！！！匈牙利算法流程以及Python程序实现！！！通俗易懂
3. 匈牙利算法原理与Python实现