2

vectors2つのAでマッチング問題を解いていますclass

class matching
{
public:
    int n;
    char match;
};

これは私が実装しようとしているアルゴリズムです:

int augment(vector<matching> &left, vector<matching> &right)
{
   while(there's no augmenting path)
     if(condition for matching)
        <augment>
  return "number of matching";
}

大まかなマッチングでは、 、 、 、および と一致する場合、および一致しleft[i]ないものにはメンバーがあり、right[j]left[i].n = jleft[i].match ='M'right[j].n = iright[j].match = 'M'n = -1match = 'U'

拡張パスを見つけている間、別の (i, j) に 1 つ存在する場合、一致しmatchないもののメンバーを から'M'に'U' 変更n = -1 し、拡張パスと一致する 2 つのメンバーmatchを 'A' に変更します。nインデックスに応じたメンバー。

これがこれを解決するための正しいアプローチであるかどうかはわかりません。これは最大一致の最初の試みであり、オンラインで多くの記事を読み、チュートリアルを見てきましたが、「コード」を適切に機能させることができません。

コードは必要ありません。コードを書くことができます。このアルゴリズムを段階的に理解したいだけです。上記で試したようなアルゴリズムを誰かが教えてくれたら、ありがたいです。また、それ以来間違った方向に進んでいる場合は、修正してください。

4

1 に答える 1

4

拡張パスを正しく見つけているかどうかはわかりません。次のアプローチをお勧めします。

  1. 貪欲な方法で最初の一致を見つけます。これを取得するために、左側のすべての頂点を移動し、貪欲に右側の空いている (一致しない) 頂点と一致させようとします。

  2. グラフで増加パス P を見つけようとします。このためには、左側のすべての自由な頂点から始めて、一致するエッジと一致しないエッジを交互に検索する幅優先検索を行う必要があります。(つまり、2 番目のレベルにはレベル 1 の頂点に隣接するすべての右側の頂点が含まれ、3 番目のレベルにはレベル 2 の頂点に一致するすべての左側の頂点が含まれ、4 番目のレベルにはレベル 3 に隣接するすべての右側の頂点が含まれます。頂点など）。任意の将来のレベルの自由頂点にアクセスしたときに検索を停止し、これまでに計算された幅優先検索ツリーを使用して拡張パス P を計算します。

  3. 前のステップで拡張パス P が見つかった場合: P の一致エッジと不一致エッジをそれぞれ不一致エッジと一致エッジに変更し、ステップ 2 に進みます。

  4. Else: 得られた結果の一致は最大です。

このアルゴリズムでは、すべての拡張に対して幅優先検索が必要になるため、最悪の場合の複雑さはO(nm). Hopcroft-Karp アルゴリズムは、幅優先検索ごとに複数の拡張を実行でき、最悪の場合の複雑さが改善されますが、実際には高速ではないようです (ウィキペディアの記事から)。

于 2012-10-10T01:29:34.570 に答える