欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

匈牙利算法原理与二分图描述

程序员文章站 2022-06-23 11:22:16
*编者. 匈牙利算法[G/OL]. *, 2020(20201109)[2020-11-09]. https://zh.wikipedia.org/w/index.php?title=%E5%8C%88%E7%89%99%E5%88%A9%E7%AE%97%E6%B3%95&oldid=62720282....

匈牙利算法简单来说其实就是一个最优分配的问题,举个例子:
你有三个工人:小明,小红和小亮。 你需要其中一个清洁浴室,另一个打扫地板,第三个洗窗,但他们每个人对各项任务要求不同数目数量的钱。 以最低成本的分配工作的方式是什么? 可以用工人做工的成本矩阵来表示该问题。表内为某个人完成某项工作所需的金额。例如:

. 小明 小红 小亮
W1 2 3 4
W2 3 2 5
W3 4 3 2

以上表格就是一个简单的匈牙利算法应用问题。三个人去分配三个工作,每个人擅长的工作不同,用最少的话费去完成这个匹配。
上表很简单,总花费最低6元可以完成三个工作。

匈牙利算法是怎么做的呢?
给定n 个工人和任务,以及一个包含分配给每个工人一个任务的成本的矩阵,寻找成本最小化分配。

首先把问题写成下面的矩阵形式
匈牙利算法原理与二分图描述
第 1 步

接下来我们对矩阵的行进行操作。将所有行中最小的元素取走,并将该行每个元素都减去刚刚取走的元素。这会让该行至少出现一个零(当一行有两个相等的最小元素时会得到多个零)。对此过程为所有行重复。我们现在得到一个每行至少有一个零的矩阵。现在我们尝试给工人指派任务,以使每个工人只做一项任务,并且每个情况的耗散都为零。说明如下。

0 a2’ a3’ a4’
b1’ b2’ b3" 0
c1’ 0 c3’ c4’
d1’ d2’ 0 d4’

用 0’ 表示的零为已指派的任务。
如果一次操作不能使每一行都有不同列的0元素,则继续重复操作知道有零元素。

匈牙利算法是一个最优组合的问题,比如有5个工人,每个工人不同工作效率不同,如何组合让他们一起工作效率最高,归根结底是个矩阵问题。可用二分图描述

本文地址:https://blog.csdn.net/weixin_42331859/article/details/110224768