当前位置: 首页 > article >正文

匈牙利算法详解与实现

匈牙利算法是一种高效的二分图最大匹配最优分配算法,常用于解决任务分配问题,例如将工人分配给任务以最小化成本。该算法通过多步矩阵操作和调整来寻找最优匹配,保证了分配成本的最小化。


算法概述

1. 矩阵减法

首先对矩阵进行行列减法:

  • 行减法:每行减去该行的最小值,使每行至少有一个零。
  • 列减法:在行减法的基础上,每列再减去该列的最小值,使每列至少有一个零。

2. 划线覆盖零元素

用尽量少的直线(横线或竖线)覆盖矩阵中的所有零元素。如果划线数量等于矩阵维度,则已找到最优解,否则进入下一步。

3. 调整矩阵

找到未被线覆盖的最小元素并调整矩阵:

  • 未被覆盖的元素减去最小值。
  • 交叉线的交点元素加上最小值。
  • 其他已被线覆盖的元素保持不变。

4. 寻找匹配

使用调整后的矩阵寻找最优匹配。优先选择那些行或列中只有一个零的元素进行匹配。

5. 计算最小成本

根据原始成本矩阵,计算匹配方案的总成本。


工人与任务分配问题

例1:3个工人和3个任务(工人任务匹配的情况)

假设有3个工人和3个任务,分配成本如下:

任务1任务2任务3
工人1413
工人2205
工人3322

1. 行和列减法

行减法:
  • 工人1:4, 1, 33, 0, 2
  • 工人2:2, 0, 52, 0, 5
  • 工人3:3, 2, 21, 0, 0

矩阵变为:

任务1任务2任务3
工人1302
工人2205
工人3100
列减法:
  • 任务1列:3, 2, 1,最小值是1
  • 任务2列:0, 0, 0,最小值是0
  • 任务3列:2, 5, 0,最小值是0

减去每列的最小值:

  • 任务1列:3 - 1, 2 - 1, 1 - 12, 1, 0
  • 任务2列:0 - 0, 0 - 0, 0 - 00, 0, 0
  • 任务3列:2 - 0, 5 - 0, 0 - 02, 5, 0

调整后:

任务1任务2任务3
工人1202
工人2105
工人3000

2. 划线覆盖零元素

通过观察,使用两条线就能覆盖所有零:

  • 一条线覆盖任务2列。
  • 一条线覆盖工人3的行。

3. 调整矩阵

最小未覆盖元素为 1。对矩阵调整如下:

  • 未被覆盖的元素减去 1
  • 交点元素加 1

调整后矩阵:

任务1任务2任务3
工人12 - 102 - 1
工人21 - 105 - 1
工人3000

具体调整如下:

  • 工人1的第1列:2 - 1 = 1
  • 工人1的第3列:2 - 1 = 1
  • 工人2的第1列:1 - 1 = 0
  • 工人2的第3列:5 - 1 = 4

交叉线的交点元素(工人3的第2列)加上1:

  • 工人3的第2列:0 + 1 = 1

调整后的矩阵:

任务1任务2任务3
工人1101
工人2004
工人3010

4. 再次划线覆盖零元素

现在我们再次用尽量少的直线覆盖所有的零元素:

  • 一条线覆盖任务2列。
  • 一条线覆盖工人2的行。
  • 一条线覆盖工人3的行。

这次我们用3条直线覆盖了所有的零元素,直线数量等于矩阵的维度(3),说明我们已经找到了最优解。

5. 寻找最优匹配

优先选择那些行或列中只有一个零的元素进行匹配:

  • 工人1的第2列:0
  • 工人2的第1列:0
  • 工人3的第3列:0

匹配结果:

  • 工人1分配任务2
  • 工人2分配任务1
  • 工人3分配任务3

6. 计算最小成本

根据原始成本矩阵,计算匹配方案的总成本:

  • 工人1 → 任务2,成本为 1
  • 工人2 → 任务1,成本为 2
  • 工人3 → 任务3,成本为 2

总成本:1 + 2 + 2 = 5

完整示例代码

import numpy as np
from scipy.optimize import linear_sum_assignment

# 成本矩阵
cost_matrix = np.array([
    [4, 1, 3],
    [2, 0, 5],
    [3, 2, 2]
])

# 求解最优分配
row_ind, col_ind = linear_sum_assignment(cost_matrix)

# 输出结果
print("工人分配到任务的对应关系:")
for i, j in zip(row_ind, col_ind):
    print(f"工人 {i + 1} 分配到任务 {j + 1}")

# 计算总成本
total_cost = cost_matrix[row_ind, col_ind].sum()
print(f"总成本: {total_cost}")

输出结果:

工人分配到任务的对应关系:
工人 1 分配到 任务 2
工人 2 分配到 任务 1
工人 3 分配到 任务 3
总成本: 5

例2:4个工人和3个任务(工人任务不匹配的情况)

当工人多于任务时,可以通过向矩阵添加虚拟任务来平衡工人和任务的数量。虚拟任务的成本可以设为0,以确保虚拟任务不会被实际分配。

假设我们有4个工人和3个任务,分配成本如下:

任务1任务2任务3
工人1413
工人2205
工人3322
工人4643

为了平衡,我们添加一个虚拟任务4,成本设为0:

任务1任务2任务3任务4 (虚拟任务)
工人14130
工人22050
工人33220
工人46430

1. 矩阵减法

行减法:
  • 工人1:4, 1, 3, 04 - 0, 1 - 0, 3 - 0, 0 - 04, 1, 3, 0
  • 工人2:2, 0, 5, 02 - 0, 0 - 0, 5 - 0, 0 - 02, 0, 5, 0
  • 工人3:3, 2, 2, 03 - 0, 2 - 0, 2 - 0, 0 - 03, 2, 2, 0
  • 工人4:6, 4, 3, 06 - 0, 4 - 0, 3 - 0, 0 - 06, 4, 3, 0

矩阵变为:

任务1任务2任务3任务4
工人14130
工人22050
工人33220
工人46430
列减法:
  • 任务1列:4, 2, 3, 6,最小值是2
  • 任务2列:1, 0, 2, 4,最小值是0
  • 任务3列:3, 5, 2, 3,最小值是2
  • 任务4列:0, 0, 0, 0,最小值是0

减去每列的最小值:

  • 任务1列:4 - 2, 2 - 2, 3 - 2, 6 - 22, 0, 1, 4
  • 任务2列:1 - 0, 0 - 0, 2 - 0, 4 - 01, 0, 2, 4
  • 任务3列:3 - 2, 5 - 2, 2 - 2, 3 - 21, 3, 0, 1
  • 任务4列:0 - 0, 0 - 0, 0 - 0, 0 - 00, 0, 0, 0

调整后:

任务1任务2任务3任务4
工人12110
工人20030
工人31200
工人44410

2. 划线覆盖零元素

通过观察,使用三条线就能覆盖所有零:

  • 一条线覆盖任务4列。
  • 一条线覆盖工人2的行。
  • 一条线覆盖工人3的行。

3. 调整矩阵

最小未覆盖元素为 1。对矩阵调整如下:

  1. 未被覆盖的元素减去最小值

    • 工人1的第1列:2 - 1 = 1
    • 工人1的第2列:1 - 1 = 0
    • 工人1的第3列:1 - 1 = 0
    • 工人4的第1列:4 - 1 = 3
    • 工人4的第2列:4 - 1 = 3
    • 工人4的第3列:1 - 1 = 0
  2. 交点元素加最小值

    • 交点元素是被两条或多条直线同时覆盖的元素。在这个例子中,交点元素是:
      • 工人2的第4列:0 + 1 = 1
      • 工人3的第4列:0 + 1 = 1

调整后的矩阵:

任务1任务2任务3任务4
工人11000
工人20031
工人31201
工人43300

4. 再次划线覆盖零元素

现在我们再次用尽量少的直线覆盖所有的零元素:

  • 一条线覆盖任务4列。
  • 一条线覆盖工人1的行。
  • 一条线覆盖工人2的行。
  • 一条线覆盖工人3的行。

这次我们用4条直线覆盖了所有的零元素,直线数量等于矩阵的维度(4),说明我们已经找到了最优解。

5. 寻找最优匹配

优先选择那些行或列中只有一个零的元素进行匹配:

  • 工人1的第2列:0
  • 工人2的第1列:0
  • 工人3的第3列:0
  • 工人4的第4列:0

匹配结果:

  • 工人1分配任务2
  • 工人2分配任务1
  • 工人3分配任务3
  • 工人4分配任务4(虚拟任务)

6. 计算最小成本

根据原始成本矩阵,计算匹配方案的总成本:

  • 工人1 → 任务2,成本为 1
  • 工人2 → 任务1,成本为 2
  • 工人3 → 任务3,成本为 2
  • 工人4 → 任务4(虚拟任务),成本为 0

总成本:1 + 2 + 2 + 0 = 5

完整示例代码

import numpy as np
from scipy.optimize import linear_sum_assignment

# 成本矩阵
cost_matrix = np.array([
    [4, 1, 3, 0],
    [2, 0, 5, 0],
    [3, 2, 2, 0],
    [6, 4, 3, 0]
])

# 求解最优分配
row_ind, col_ind = linear_sum_assignment(cost_matrix)

# 输出结果
print("工人分配到任务的对应关系:")
for i, j in zip(row_ind, col_ind):
    if j < 3:
        print(f"工人 {i + 1} 分配到任务 {j + 1}")
    else:
        print(f"工人 {i + 1} 未分配实际任务")

# 计算总成本
total_cost = cost_matrix[row_ind, col_ind].sum()
print(f"总成本: {total_cost}")

输出结果:

工人分配到任务的对应关系:
工人 1 分配到任务 2
工人 2 分配到任务 1
工人 3 分配到任务 3
工人 4 未分配实际任务
总成本: 5

注意事项

  • 匈牙利算法适用于最小化问题:匈牙利算法主要用于最小化成本或代价。如果问题是最大化问题(如求取IOU最大匹配问题),则需要进行适当的转换,例如将最大化问题转换为最小化问题。
  • 调整矩阵:如果直线数量少于矩阵的维度,调整矩阵以增加零的数量,直到找到最优解。

有趣的网站

可以使用以下网站来实验自己的例子,验证匈牙利算法的结果以及中间过程:

  • Hungarian Algorithm Calculator

Code

AI_With_NumPy
此项目汇集了更多AI相关的代码实现,供大家学习使用,欢迎点赞收藏👏🏻

备注

个人水平有限,有问题随时交流~


http://www.kler.cn/a/319428.html

相关文章:

  • [前端]NodeJS常见面试题目
  • -1大于4?负数与无符号整数类型:size_t的比较问题(strlen)
  • 文献解读-DNAscope: High accuracy small variant calling using machine learning
  • MYSQL 库,表 基本操作
  • power bi中的related函数解析
  • adb shell常用命令
  • 【Tomcat】常见面试题整理 共34题
  • 跨站请求伪造(CSRF)漏洞详解
  • 【MySQL】知识总结——索引的类型分类和性质
  • 2023国赛C题 蔬菜类商品的自动定价与补货决策(上)
  • Spring Boot 中实现动态列导入讲解和案例示范
  • element plus上传文件 点击确认后文件上传到接口
  • Java项目实战II基于Java+Spring Boot+MySQL的车辆管理系统(开发文档+源码+数据库)
  • 【Java】将一个List拆分使用线程池多线程运行
  • linux进程间通信——消息队列、信号量、ipc设计原理
  • 梧桐数据库(WuTongDB):向量化查询优化器的一些实现细节
  • 傅里叶变换及其应用笔记
  • 使用dom-to-image截图html区域为一张图
  • Redis --- redis事务和分布式事务锁
  • 全栈杂谈第三期 我们用的网络协议是什么
  • 前端css样式覆盖
  • 我的AI工具箱Tauri版-MicrosoftTTS文本转语音
  • 24.9.23学习笔记
  • “永辉优品”会是中国零售的答案吗?
  • 通信工程学习:什么是WLAN无线局域网
  • Python 从入门到实战28(文件的读操作)