2

我正在用两个解决一个匹配vectors问题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 = j、left[i].match ='M'、right[j].n = i和right[j].match = 'M'不匹配的有成员n = -1和match = 'U'

在找到增广路径时，如果一个存在另一个（i，j），那么我们将match不匹配的成员从'M'to更改为，'U' 并且n = -1 与增广路径匹配的两个match在我们更改时将其成员更改为“A”他们的成员n根据他们的指数。

我不知道这是否是解决这个问题的正确方法，这是我第一次尝试最大匹配，我已经阅读了很多文章并在线观看了教程，但我无法让我的“代码”正常运行。

我不需要代码，我可以编写我的代码。我只是想一步一步地理解这个算法。如果有人能给我一个像我上面尝试过的算法，我将不胜感激。另外，如果从那以后我一直走错方向，请纠正我。

4

1 回答 1

4

我不确定您是否正确找到了扩充路径。我建议采用以下方法。

  1. 以贪婪的方式找到初始匹配。为了获得这一点，我们遍历左侧的每个顶点，并贪婪地尝试将其与右侧的一些空闲（未匹配）顶点匹配。

  2. 尝试在图中找到一条增广路径 P。为此，我们需要从左侧的所有自由顶点开始进行广度优先搜索，并在搜索中交替通过匹配和不匹配的边。（即第二层包含与level-1顶点相邻的所有右侧顶点，第三层包含与level-2顶点匹配的所有左侧顶点，第四层包含与level-3相邻的所有右侧顶点顶点等）。当我们在任何未来级别访问一个自由顶点时，我们停止搜索，并使用到目前为止计算的广度优先搜索树计算增广路径 P。

  3. 如果我们在上一步中可以找到一条增广路径 P： 将 P 中的匹配边和不匹配边分别更改为不匹配边和匹配边，然后转到步骤 2。

  4. Else：得到的结果匹配是最大的。

该算法需要对每个扩展进行广度优先搜索，因此它的最坏情况复杂度为O(nm). 尽管Hopcroft-Karp 算法可以为每个广度优先搜索执行多次增强，并且具有更好的最坏情况复杂性，但它似乎（来自 Wikipedia 文章）在实践中并没有更快。

于 2012-10-10T01:29:34.570 回答