void Hungarian::doHungarian() { int x, y; for (x = 0; x < k; x++) { //khởi tạo điểm bắt đầu và kết thúc của 1 đường mở //finish = -1 nghĩa là chưa tìm thấy đường mở start = x; finish = -1; do { FindAugmentingPath(); // tìm đường mở if (finish == -1) // nếu ko tìm được đường mở thì xoay các trọng số cạnh SubX_AddY(); } while (finish == -1); Enlarge();//tăng cặp dựa trên đường mở tìm được } }
时间: 2023-06-16 14:06:11 浏览: 204
这是一个匈牙利算法的实现代码,用于解决二分图最大匹配问题。其大致思路是按顺序遍历二分图的左侧节点,对每个节点进行增广路径查找,如果找到增广路径则进行匹配,否则进行边权重调整,直到所有节点都被匹配为止。其中的函数包括:
- FindAugmentingPath():查找增广路径。
- SubX_AddY():调整边权重。
- Enlarge():根据找到的增广路径进行匹配。
如果您需要更详细的解释,请让我知道。
相关问题
double Hungarian::Solve(vector<vector<double>>& DistMatrix, vector<int>& Assignment) { Enter(DistMatrix, Assignment); Init(); doHungarian(); //update assignment for (int x = 0; x < m; x++) { Assignment.push_back(matchX[x]); } for (int x = 0; x < m; x++) { for (int y = 0; y < n; y++) { DistMatrix[x][y] = c[x][y]; if (c[x][y] == maxC) DistMatrix[x][y] = 0.f; } } float cost = 0.f; for (int x = 0; x < m; x++) { int y = matchX[x]; if (c[x][y] < maxC) { cost += c[x][y]; } } return cost; }
这段代码实现的是匈牙利算法,用于解决二分图最大权完美匹配问题。它的输入参数包括一个距离矩阵和一个空的分配数组,输出结果为最小权匹配的权值。
其中,Enter函数用于初始化距离矩阵和分配数组,Init函数用于初始化匈牙利算法中的相关数据结构,doHungarian函数用于执行匈牙利算法,得到最小权匹配。最后,更新分配数组和距离矩阵,计算最小权匹配的权值并返回。
需要注意的是,这段代码中的变量命名可能存在一些问题,如变量m和n没有明确定义,而是需要从距离矩阵中获取行数和列数。
void Hungarian::Init() { int i, j; //Khởi tạo ban đầu 2 bộ ghép đều rỗng (các giá trị được gán bằng -1 nghĩa là chưa có // đỉnh X gán với Y hoặc ngược lại) for (i = 0; i < MAX; i++) { matchX[i] = -1; matchY[i] = -1; } //tìm trọng số nhỏ nhất của các cạnh liên thuộc với X[i] for (i = 0; i < k; i++) { Fx[i] = maxC; for (j = 0; j < k; j++) { if (c[i][j] < Fx[i]) { Fx[i] = c[i][j]; } } } //tìm trọng số nhỏ nhất của các cạnh liên thuộc với Y[j] for (j = 0; j < k; j++) { Fy[j] = maxC; for (i = 0; i < k; i++) { if (c[i][j] - Fx[i] < Fy[j]) { Fy[j] = c[i][j] - Fx[i]; } } } }
这段代码是匈牙利算法的初始化函数,主要实现以下几个任务:
1. 初始化匹配数组matchX和matchY,初始时没有顶点被匹配,所以数组中所有值都为-1。
2. 对于每个顶点X[i],计算其与相邻顶点Y[j]之间边的最小权值,并将其保存在Fx[i]中。
3. 对于每个顶点Y[j],计算与相邻顶点X[i]之间边的权值减去Fx[i]的最小值,并将其保存在Fy[j]中。
以上步骤是匈牙利算法的预处理步骤,在找增广路时会用到这些信息。其中,maxC是一个较大的常数,起到初始化Fx和Fy时的默认最大值的作用。
阅读全文