0

给定两个大小为 N 的集合 A 和 B，以及为叉积 AxB 的 N^2 个条目中的每一个分配一个实数的权重，我们希望形成 A 和 B 的匹配，使得最低权重最大化.

举个例子，我们正在组织一场赛马，我们有 10 名骑师和 10 匹马，每个骑师骑着每匹马的预期速度都不同。我们必须选择哪位骑师骑哪匹马，以使这场比赛中最慢的骑师/马尽可能快。

拿

    i  j  k
a   9  1  2
b   4  3  1
c   7  3  5

这里的“最大最小匹配”是 { (a,i), (b,j), (c,k) }，值为 3。

计算这种匹配的算法是什么，它的复杂性是多少？

4

2 回答 2

1

此答案指导如何为此问题创建O(n^2 * sqrt(n) * log(n))解决方案。

朴素慢速算法：
首先，请注意，朴素在对问题建模的二分图上O(n^4 * sqrt(n))迭代地使用匹配算法，并寻找无法去除的“最高边集”。（意思是：寻找匹配中最小的最大边）。

该图是G= (V,E), whereV = A [union] B和E = A x B。

算法是：

sort the edges according to the weighted value
while there is an unweighted match match:
   remove the edge with smallest value
return the match weight of the last removed edge

正确性解释：
很容易看出该值不小于最后一个删除的边 - 因为有一个匹配使用它而不是“更小”的边。
它也不是更高，因为当这个边缘被移除时 - 没有匹配。

复杂性：
运行O(n^2)匹配算法，O(|E|sqrt(|V|)) = O(n^2 * sqrt(n))总共产生O(n^4 * sqrt(n)

我们想减少这个O(n^2)因素，因为可能应该使用匹配算法。

优化：
请注意，该算法实际上是在寻找“剪切”已排序边列表的位置。我们实际上是在寻找必须在列表中的最小边才能获得匹配。
这里可以暗示二进制搜索，其中每个“比较”实际上是在检查是否存在匹配，并且您正在寻找产生匹配的“最高”元素。这将导致O(log(n^2)) = O(logn)匹配算法的迭代，给你总共O(n^2 * sqrt(n) * log(n))

高级优化算法：

//the compare OP
checkMatching(edges,i): 
   edges' <- edges 
   remove from edges' all the elements with index j < i
   check if there is a match in the graph
   return 1 if there is, 0 otherwise.
//the algorithm:
find max_min(vertices,edges):
   sort edges according to weight ascending
   binary search in edges for the smallest index that yields 0
   let this index be i
   remove from edges all the elements with index j < i
   return a match with the modified edges
于 2012-06-06T15:18:33.333 回答
0

这个问题是典型的二分匹配问题。您可以查看匈牙利方法或 KM 算法来解决它。

于 2012-06-06T15:15:21.553 回答