匈牙利算法解决整体最优分配问题<未完成>
发布于2024-09-01 23:27:14,更新于2024-09-23 00:10:47,标签:java 文章会持续修订,转载请注明来源地址:https://meethigher.top/blog一、背景
1.1 应用场景
美真是铠甲勇士的指挥官,手下有五个铠甲勇士在闲着。正所谓养兵千日用兵一时,现在有突发预警,三个地方出现了异能兽。
现在美真需要立即安排三个铠甲勇士去现场解决异能兽,但要保证铠甲勇士们整体移动距离最少的情况下到达异能兽目的地。
已知铠甲到达异能兽位置的距离如下,
目的地/与铠甲距离 | 炎龙铠甲 | 风影铠甲 | 地虎铠甲 | 雪獒铠甲 | 黑犀铠甲 |
---|---|---|---|---|---|
恶参兽 | 1 | 2 | 3 | 4 | 5 |
刺木兽 | 2 | 3 | 4 | 5 | 6 |
蚂蚱兽 | 3 | 4 | 5 | 6 | 7 |
1.2 解决思路
这个问题可以被看作是经典的“指派问题” (Assignment Problem),其核心是如何最优分配任务,以使总时间最短。我们可以使用“匈牙利算法”(Hungarian Algorithm)来求解该问题。
下面需要一步步了解概念。
二、图
图是由“顶点”和“边”所组成的集合,通常用G=(V,E)来表示,其中V是所有顶点所组成的集合,而E代表所有边所组成的集合。
图的种类有两种
- 无向图。以(V1,V2)表示其边。
- 有向图。以<V1,V2>表示其边。
2.1 无向图
无向图的基础概念以书中的截图展示如下。
2.2 有向图
有向图的基础概念以书中的截图展示如下。
2.3 图的数据表示法
下面给出一个无向图的示例图片
可以有三种方式来进行表示该图
- 邻接矩阵
- 邻接表
- 边列表
邻接矩阵(Adjacency Matrix)
- 使用一个二维矩阵表示图,矩阵中的每个元素表示节点之间是否有边相连。
- 如果图有
n
个节点,则邻接矩阵是一个n x n
的矩阵。 - 无向图:矩阵是对称的,
A[i][j] = A[j][i]
。 - 有向图:矩阵不一定对称,
A[i][j]
表示从节点i
到节点j
的边。 - 如果有边相连,
A[i][j] = 1
,否则为0
(在加权图中,A[i][j]
可以是权重值)。
优点:查找某两点之间是否有边时非常快速。
缺点:空间复杂度高,需要 O(n^2)
的存储空间,尤其是稀疏图时非常浪费空间。
示例(以上述无向图为例):
1 | A B C |
邻接表(Adjacency List)
- 使用一个列表数组,每个节点对应一个列表,列表中存储与该节点直接相连的其他节点。
- 对于无向图,节点
i
的列表中包含与i
相连的所有节点;对于有向图,节点i
的列表中只包含从i
出发的节点。
优点:节省空间,特别适用于稀疏图;添加边和遍历相邻节点更高效。
缺点:查找两节点是否相邻时不如邻接矩阵高效。
示例(以上述无向图为例):
1 | A -> B, C |
边列表(Edge List)
- 使用一个边的列表,每条边表示两个相连的节点和可能的边权。
- 每个元素表示一条边,例如
(A, B)
表示节点A
和B
相连,如果是加权图,可以表示为(A, B, weight)
。
优点:结构简单,适合表示稀疏图。
缺点:查找两节点是否相邻需要遍历整个边列表。
示例(以上述无向图为例):
1 | [(A, B), (A, C)] |
适用场景:
- 邻接矩阵:适合边数多的图(密集图),因为查找某两点是否相连比较快。
- 邻接表:适合边数少的图(稀疏图),节省空间且遍历邻居高效。
- 边列表:适合简单图的表示或算法实现,特别是需要遍历所有边的情况。
这些表示方法根据不同场景和需求有各自的优缺点,具体选用哪种表示方法取决于图的规模、边的数量和使用场景。
三、经典匈牙利算法
3.1 二分图
一个图G=(V,E),其中V是顶点集,E是边集。如果可以将顶点集V划分为两个不相交的集合V1和V2,并且满足图中的每条边都只连接V1和V2中的一个顶点。这种图G就叫做二分图。
3.2 最大匹配问题
实际场景:假设有一组男、女,每个人都有自己的偏好列表。最大匹配可以帮助找到尽可能多的婚姻组。
示例代码:
1 | import java.util.Arrays; |
五、解决背景问题
背景中的需求是要保证铠甲勇士们整体移动距离最少的情况下到达异能兽目的地。
这其实就是一个二分图最小权完美匹配问题,在加权二分图中找出匹配的总权值最小的完美匹配。