void Hungarian::SubX_AddY() { int i, j, t; double Delta; set<int> VisitedX, VisitedY; /* Để ý rằng: VisitedY = {y \ Trace[y] khác -1} VisitedX = {start} giao match(VisitedY) = {start} giao {matchY[y] Trace[y] khác -1} */ VisitedX.insert(start); for (j = 0; j < k; j++) { if (Trace[j] != -1) { VisitedX.insert(matchY[j]); VisitedY.insert(j); } }
时间: 2023-06-16 11:06:22 浏览: 62
这段代码是匈牙利算法中的子图相交增广函数的一部分。在这段代码中,首先初始化了一些变量和数据结构,包括 VisitedX 和 VisitedY 两个集合,它们分别表示已经访问过的 X 点和 Y 点。接着,将起点 start 加入 VisitedX 集合中。然后遍历所有的 Y 点,如果这个点已经匹配过,即 Trace[j] 不等于 -1,那么将它的匹配点 matchY[j] 加入 VisitedX 集合中,并将这个点 j 加入 VisitedY 集合中。这样就得到了两个集合 VisitedX 和 VisitedY,它们的交集表示子图中已经访问过的点,即匈牙利算法中的增广路。
相关问题
void Hungarian::SubX_AddY() { int i, j, t; double Delta; set<int> VisitedX, VisitedY; /* Để ý rằng: VisitedY = {y \ Trace[y] khác -1} VisitedX = {start} giao match(VisitedY) = {start} giao {matchY[y] Trace[y] khác -1} */ VisitedX.insert(start); for (j = 0; j < k; j++) { if (Trace[j] != -1) { VisitedX.insert(matchY[j]); VisitedY.insert(j); } }Delta = maxC; for (i = 0; i < k; i++) { if (VisitedX.find(i) != VisitedX.end()) { for (j = 0; j < k; j++) { if ((VisitedY.find(j) == VisitedY.end()) && (GetC(i, j) < Delta)) Delta = GetC(i, j); } } }for (t = 0; t < k; t++) { //trừ trọng số những cạnh liên thuộc với VisitedX đi Delta if (VisitedX.find(t) != VisitedX.end()) Fx[t] = Fx[t] + Delta; //Cộng trọng số những cạnh liên thuộc với VisitedY lên Delta if (VisitedY.find(t) != VisitedY.end()) Fy[t] = Fy[t] - Delta; } }
这段代码是匈牙利算法中的"SubX_AddY"步骤,用于更新节点权值。具体来说,它的作用是从未被匹配的点中找出与已被匹配的点相邻且边权最小的点,然后更新所有与这些点相邻的点的权值。这个过程会涉及到两个向量Fx和Fy,它们分别表示未被匹配的点和已被匹配的点的权值。在这个过程中,我们先将所有与已被匹配的点相邻的点加入VisitedX和VisitedY中,然后遍历VisitedX中的所有点,找到与之相邻且未被匹配的点中边权最小的点,记为Delta,然后更新所有与VisitedX和VisitedY相邻的点的权值。具体来说,对于VisitedX中的点,我们将它们的权值加上Delta,对于VisitedY中的点,我们将它们的权值减去Delta。这样做的目的是为了使已被匹配的点的权值尽量小,从而使匹配的代价最小化。
double Hungarian::GetC(int i, int j) { return c[i][j] - Fx[i] - Fy[j]; }
这段代码是匈牙利算法中计算两点间费用的函数。在匈牙利算法中,需要寻找二分图中的最大权匹配,其中每个点都有一个权重(或费用),而 GetC(i,j) 函数就是用来计算第 i 个点和第 j 个点之间的费用。其中,c[i][j] 表示第 i 个点和第 j 个点之间的原始费用(即没有经过任何调整的费用),而 Fx[i] 和 Fy[j] 分别表示第 i 个点和第 j 个点的横向和纵向调整值。通过对原始费用和横向、纵向调整值进行加减操作,就可以得到两点间的实际费用。