0

サイズNが等しい2つのセットAとB、および外積AxBのN ^ 2エントリのそれぞれに実数を割り当てる重みが与えられた場合、最小の重みが最大になるようにAとBのマッチングを形成します。 。

例として、競馬を開催しており、10人の騎手と10頭の馬がいます。各騎手は、各馬に乗る予想速度が異なります。この対戦で最も遅い騎手/馬ができるだけ速くなるように、どの騎手がどの馬に乗るかを選択する必要があります。

取った

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

ここで、「max-min-matching」は{（a、i）、（b、j）、（c、k）}で、値は3です。

このマッチングを計算するためのアルゴリズムとは何ですか？また、その複雑さは何ですか？

4

2 に答える 2

1

この回答O(n^2 * sqrt(n) * log(n))は、この問題の解決策を作成する方法を示しています。

ナイーブな遅いアルゴリズム:
まず、ナイーブは、問題をモデル化する 2 部グラフでマッチング アルゴリズムをO(n^4 * sqrt(n))繰り返し使用し、削除できない「エッジの最高セット」を探していることに注意してください。(意味: マッチングで最小になる最大エッジを探します)。

グラフはG= (V,E)、どこでV = 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 に答える