### 匈牙利算法的手动实现 匈牙利算法的核心在于通过一系列调整操作来寻找最优匹配。以下是基于 Python 的手动实现版本及其逐行解释。 #### 手动实现代码 ```python def hungarian_algorithm(cost_matrix): n = len(cost_matrix) # 获取矩阵大小 marked = [[False] * n for _ in range(n)] # 创建标记矩阵用于记录匹配状态[^1] def find_augmenting_path(row, seen_cols): # 寻找增广路径函数 for col in range(n): # 遍历列 if cost_matrix[row][col] == 0 and not seen_cols[col]: # 如果当前单元格为零且未访问过 seen_cols[col] = True # 将其标记为已访问 if matched_to_col[col] == -1 or find_augmenting_path(matched_to_col[col], seen_cols): # 若目标列未被匹配或能找到新的增广路径 matched_to_col[col] = row # 更新匹配关系 return True # 返回成功找到增广路径的结果 return False # 否则返回失败 def clear_markings(): # 清除标记以便重新计算 nonlocal marked marked = [[False] * n for _ in range(n)] def mark_zeroes(): line_count = 0 rows_covered = [False] * n cols_covered = [False] * n while True: clear_markings() # 每次循环前清除旧标记 for i in range(n): zero_found = False for j in range(n): if (not rows_covered[i]) and (not cols_covered[j]) and (cost_matrix[i][j] == 0): marked[i][j] = True zero_found = True rows_covered[i] = True cols_covered[j] = True break if zero_found: continue else: break done = True for i in range(n): for j in range(n): if (not rows_covered[i]) and (not cols_covered[j]): done = False if done: return line_count line_count += cover_zeros() def cover_zeros(): min_rows = set() min_cols = set() for i in range(n): for j in range(n): if not marked[i][j]: min_rows.add(i) break for j in range(n): for i in range(n): if not marked[i][j]: min_cols.add(j) break uncovered_val = float('inf') for i in range(n): if i not in min_rows: for j in range(n): if j not in min_cols: uncovered_val = min(uncovered_val, cost_matrix[i][j]) for i in range(n): for j in range(n): if i in min_rows and j in min_cols: cost_matrix[i][j] += uncovered_val elif i not in min_rows and j not in min_cols: cost_matrix[i][j] -= uncovered_val return 1 reduced_cost_matrix = [] for i in range(n): min_in_row = min(cost_matrix[i]) reduced_cost_matrix.append([val - min_in_row for val in cost_matrix[i]]) transposed_reduced = list(map(list, zip(*reduced_cost_matrix))) for j in range(n): min_in_col = min(transposed_reduced[j]) for i in range(n): reduced_cost_matrix[i][j] -= min_in_col matched_to_col = [-1] * n # 初始化每列的匹配情况 for row in range(n): # 对每一行尝试寻找增广路径 seen_cols = [False] * n # 记录哪些列已被访问 find_augmenting_path(row, seen_cols) result = [] # 存储最终匹配结果 total_cost = 0 # 总成本初始化为0 for col in range(n): # 构建最终匹配列表并计算总成本 if matched_to_col[col] != -1: result.append((matched_to_col[col], col)) total_cost += cost_matrix[matched_to_col[col]][col] return result, total_cost # 测试用例 if __name__ == "__main__": matrix = [ [4, 2, 7], [5, 3, 6], [8, 1, 9] ] matching, cost = hungarian_algorithm(matrix) print(f"Matching: {matching}, Total Cost: {cost}") ``` --- ### 代码说明 上述代码实现了匈牙利算法的主要逻辑： 1. **输入处理**: 输入是一个二维数组 `cost_matrix`，表示任务分配的成本矩阵。 2. **初始简化**: 减去每行和每列中的最小值以减少复杂度[^2]。 3. **核心逻辑**: - 使用布尔矩阵 `marked` 来跟踪可能的匹配项。 - 利用递归方法 `find_augmenting_path` 查找增广路径。 - 调整覆盖线直到满足条件为止。 4. **输出结果**: 输出最佳匹配方案以及对应的最低总成本。 ---