double Hungarian::GetC(int i, int j) { return c[i][j] - Fx[i] - Fy[j]; }
时间: 2023-06-16 17:06:25 浏览: 39
这段代码是匈牙利算法中计算两点间费用的函数。在匈牙利算法中,需要寻找二分图中的最大权匹配,其中每个点都有一个权重(或费用),而 GetC(i,j) 函数就是用来计算第 i 个点和第 j 个点之间的费用。其中,c[i][j] 表示第 i 个点和第 j 个点之间的原始费用(即没有经过任何调整的费用),而 Fx[i] 和 Fy[j] 分别表示第 i 个点和第 j 个点的横向和纵向调整值。通过对原始费用和横向、纵向调整值进行加减操作,就可以得到两点间的实际费用。
相关问题
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时的默认最大值的作用。
void Hungarian::FindAugmentingPath() { queue<int> q; int i, j, first, last; for (i = 0; i < MAX;i++) { Trace[i] = -1; } ///memset(Trace, -1, sizeof(Trace)); //chạy thuật toán BFS để tìm đường mở q.push(start); first = 0; last = 0; do { i = q.front(); q.pop(); for (j = 0; j < k; j++) { if (Trace[j] == -1 && GetC(i, j) == 0.0f) { Trace[j] = i; if (matchY[j] == -1) { finish = j; return; } q.push(matchY[j]); } } } while (!q.empty()); }
这是一个匈牙利算法中寻找增广路径的函数。具体来说,该函数使用广度优先搜索(BFS)来在二分图中寻找增广路径。
输入:无
输出:无,但是函数会更新Trace数组,该数组用于记录增广路的路径。
算法步骤如下:
1. 将Trace数组初始化为-1。
2. 将起始节点start加入队列q中,并将first和last初始化为0。
3. 在一个do-while循环中,从队列q中取出一个节点i,然后遍历与该节点相邻的所有节点j。
4. 如果节点j尚未被访问过(即Trace[j]为-1),并且从节点i到节点j的边权值为0,那么就更新Trace[j]为i,并将与节点j相邻的右部节点加入队列q中。
5. 如果节点j已经匹配了一个左部节点(即matchY[j]不为-1),那么就将其所匹配的左部节点加入队列q中。
6. 当队列q为空时,表示已经遍历完所有可能的增广路径,函数结束。如果找到了一条增广路(即在遍历过程中找到了一个未匹配的右部节点),那么就将该右部节点记录在finish变量中,然后函数返回。