匈牙利算法最优指派代码

匈牙利算法，也称为Kuhn-Munkres算法，是一种用于解决最优指派问题的经典算法。最优指派问题是指在给定的n个任务和n个执行者之间，找到一种最佳的任务分配方式，使得总成本或总收益最小或最大。

以下是匈牙利算法的最优指派代码示例（使用Python语言）：

import numpy as np

def hungarian_algorithm(cost_matrix):
    # 创建一个副本以避免修改原始矩阵
    cost_matrix = np.array(cost_matrix)

    # 初始化行和列的标记数组
    rows, cols = cost_matrix.shape
    row_covered = np.zeros(rows, dtype=bool)
    col_covered = np.zeros(cols, dtype=bool)

    # 执行步骤1：减去每一行的最小值
    for i in range(rows):
        min_val = np.min(cost_matrix[i])
        cost_matrix[i] -= min_val

    # 执行步骤2：减去每一列的最小值
    for j in range(cols):
        min_val = np.min(cost_matrix[:, j])
        cost_matrix[:, j] -= min_val

    # 执行步骤3：标记零元素并尝试进行指派
    while True:
        # 标记所有包含零元素的行和列
        marked_rows, marked_cols = mark_zeros(cost_matrix)

        # 如果没有更多的零元素，则算法结束
        if len(marked_rows) == 0:
            break

        # 尝试进行指派
        while True:
            # 找到一个未被指派的零元素
            unassigned_zero = find_unassigned_zero(cost_matrix, marked_rows, marked_cols)

            # 如果找不到未被指派的零元素，则进行步骤5
            if unassigned_zero is None:
                step = 5
                min_val = np.inf
                for i in range(rows):
                    for j in range(cols):
                        if not marked_rows[i] and not marked_cols[j]:
                            min_val = min(min_val, cost_matrix[i, j])
                # 执行步骤5：将最小未被覆盖元素减去所有未被覆盖元素，并将其加到被覆盖两次的元素上
                for i in range(rows):
                    for j in range(cols):
                        if marked_rows[i]:
                            cost_matrix[i, j] += min_val
                        if not marked_cols[j]:
                            cost_matrix[i, j] -= min_val
            else:
                # 标记该零元素并找到与之关联的其他零元素
                marked_rows[unassigned_zero] = True
                marked_cols[unassigned_zero] = False

    # 返回最终的指派结果
    assignment = []
    for i in range(rows):
        for j in range(cols):
            if cost_matrix[i, j] == 0:
                assignment.append((i, j))
    return assignment

def mark_zeros(cost_matrix):
    rows, cols = cost_matrix.shape
    marked_rows = np.zeros(rows, dtype=bool)
    marked_cols = np.zeros(cols, dtype=bool)
    for i in range(rows):
        for j in range(cols):
            if cost_matrix[i, j] == 0 and not marked_rows[i] and not marked_cols[j]:
                marked_rows[i] = True
                marked_cols[j] = True
    return marked_rows, marked_cols

def find_unassigned_zero(cost_matrix, marked_rows, marked_cols):
    rows, cols = cost_matrix.shape
    for i in range(rows):
        for j in range(cols):
            if cost_matrix[i, j] == 0 and marked_rows[i] and not marked_cols[j]:
                return (i, j)
    return None

# 示例用法
cost_matrix = [[4, 1, 3],
               [2, 0, 5],
               [3, 2, 2]]

assignment = hungarian_algorithm(cost_matrix)
print("最优指派结果：")
for row, col in assignment:
    print(f"任务 {row+1} 分配给执行者 {col+1}")

这段代码实现了匈牙利算法，通过传入一个成本矩阵来计算最优的任务指派结果。你可以根据自己的需求修改成本矩阵，并根据实际情况进行适当的调整。