0

我需要为此类任务实现匈牙利算法的实现:我有任何矩阵示例(实际上我需要这个用于聚类分析):

X<-matrix(c(-1,1,2,-1,2,3,1,2,3), nrow=3, ncol=3, byrow = TRUE)
X

为了获得这样的结果,我需要对行或列进行一些排列:所有对角线元素都应该是最大的。在这里,我将展示一些照片:矩阵示例,其中我有 3 行和 3 列,然后我必须有一个结果: 矩阵变化

如图所示,有一个排列:第一列变成第三列,之后新的第一列和第二列改变位置。我怎么能用匈牙利算法做这样的事情?

4

2 回答 2

0

我将以您问题中的这个矩阵为例:

 2  7  1
 0  0 10
 8  2  0

首先,匈牙利算法找到最小值,而不是最大值,因此我们需要将所有值乘以 -1,这样当您运行算法并找到最小值时,它实际上是原始矩阵的最大值。

-2 -7  -1
-0 -0 -10
-8 -2  -0

匈牙利算法仅适用于非负数,虽然您使用的代码应该能够处理它们,但您可以通过减去矩阵中的最小数字(在这种情况下为 -10)自己摆脱它们从矩阵中的每个值。

 8  3  9
10 10  0
 2  8 10

现在我们在这个矩阵上运行匈牙利算法并得到算法找到的最小匹配的索引列表。我们想按 x 索引对该列表进行排序。

[(0,2), (1,0), (2,1)]

这个最小匹配也是我们原始矩阵的最大匹配。由于这种匹配是按 x 索引排序的,我们可以使用 y 索引作为原始矩阵的索引。也就是说,第一个索引对是(0,2),所以我们最终矩阵的第一行将是原始矩阵的第三行。

(0,2)->
(1,0)最终矩阵的第一行是原始矩阵的
(2,1)第三行 -> 最终矩阵的第二行是原始矩阵的第一行 -> 最终矩阵的第三行是原始矩阵的第二行

 8  2  0
 2  7  1
 0  0 10

这与您在问题中给出的排列不完全匹配,但它仍然是有效的排列。

于 2021-11-07T03:22:11.550 回答
0

尝试使用 RcppHungarian 函数。但是,这些值必须是非负数,所以我稍微更改了数据!

library(RcppHungarian)
x<-matrix(c(1,2,3,1,2,3,2,2,3), nrow=3, ncol=3, byrow = TRUE)
HungarianSolver(x)
于 2021-10-29T02:29:13.803 回答