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; } }
时间: 2023-06-16 19:06:12 浏览: 89
Hungarian.rar_hungarian MATLAB_matlab 指派问题_matlab 覆盖_指派算法_覆盖
这段代码是匈牙利算法中的"SubX_AddY"步骤,用于更新节点权值。具体来说,它的作用是从未被匹配的点中找出与已被匹配的点相邻且边权最小的点,然后更新所有与这些点相邻的点的权值。这个过程会涉及到两个向量Fx和Fy,它们分别表示未被匹配的点和已被匹配的点的权值。在这个过程中,我们先将所有与已被匹配的点相邻的点加入VisitedX和VisitedY中,然后遍历VisitedX中的所有点,找到与之相邻且未被匹配的点中边权最小的点,记为Delta,然后更新所有与VisitedX和VisitedY相邻的点的权值。具体来说,对于VisitedX中的点,我们将它们的权值加上Delta,对于VisitedY中的点,我们将它们的权值减去Delta。这样做的目的是为了使已被匹配的点的权值尽量小,从而使匹配的代价最小化。
阅读全文