匈牙利算法相关问题

aimisiyou

wrf610051 发表于 2020-2-15 20:03
由大师7楼的数据(setq jzlst '((0 1 4 15 1)(4 1 12 27 0)(0 0 17 26 5)(2 0 14 12 0)(0 0 0 0 0)))
得到 ...

你这结果是配对关系吧。我那里得到的结果是覆盖所有0的四条线，不是最后的配对关系。

wrf610051

如图，已知最少要用5条直线才能覆盖所有的0，5条直线为（（0，1）（0，3）（0，5）（4，0）（5，0）），如何得到三角形所在的坐标（（0，0）（1，4）（2，2）（3，3）（4，1））？

我认为三角形所在的坐标正好是配对关系。我想问大师能否从配对关系，推出覆盖所有0的线条呢？

aimisiyou

wrf610051 发表于 2020-2-16 06:34
我认为三角形所在的坐标正好是配对关系。我想问大师能否从配对关系，推出覆盖所有0的线条呢？

是的，三角形所在的坐标正好就是最大匹配情况。你所指的配对关系是指已知的连线情况吧(要从中选取最大匹配问题吧)？如果你所指的是最终结果，即最大匹配结果，那么每个坐标在每行每列是唯一的，所以该坐标所在的行或列就是一条覆盖线。我们要找的就是最少的坐标（即最少的覆盖线条数）覆盖所有的0。

aimisiyou

aimisiyou 发表于 2020-2-9 22:09
对于《匈牙利算法质疑》中的反例（非0元素可取1），检测运行确实会出现死循环情况，因为选定c11为0*（正确 ...

针对特例情况，选取0作为0*的条件稍作修改：1、如果某行或某列只有一个0，则选取该0作为0*；若无此情况执行2：2、若某行或某列中的0即是行最小值也是列最小值，则选择该0作为0*（注意0之间也有大小之分，一行或一列中靠后的0比靠前的0小），若无此情况则执行3：3、一个0所在的行和列上的0个数之和最少的，则选择该0作为0*。如图，第一步选择0（6，6）作为0*；第二步，可得到0（3，2)和0(5，5）都是行和列中的最小值，任选一个作为0*；余下的仍按3条规则选取0*。



不知道是否还存在反例？

aimisiyou

仔细想了下，若某个0处于独行独列，那么该0也是属于第2种情况，即是同时是该行和该列的最小值，另外每行每列都至少有1个0时，最后一个0一定是该行该列的最小值。即先用匈牙利算法得到最大覆盖线条数，然后按条件2规则选取0*。

aimisiyou

另外一种算法，先将矩阵转换为每行每列都至少有1个0，选取最后一个0为0*，同时删除最后一个0所在的行和列，剩下的矩阵再转换为每行每列都至少有一个0，选取最后一个0为0*，同时删除该0*所在行和列；……直至选取最后一个0*。

aimisiyou

不对，将特例倒过来，仍是一个反例。看来真是迈不过去啊。