void Hungarian::Enlarge() { int x, next; do { x = Trace[finish]; next = matchX[x]; matchX[x] = finish; matchY[finish] = x; finish = next; } while (finish != -1); }
时间: 2023-06-16 17:06:13 浏览: 40
这是一个匈牙利算法的扩充操作,用于增广路径。在匈牙利算法中,我们从未匹配的 X 点开始,尝试去匹配它的相邻 Y 点。如果 Y 点没有被匹配,那么我们就找到了一条增广路径。如果 Y 点已经被匹配,那么我们就需要从这个已匹配的 Y 点出发,去寻找另外一个未匹配的 X 点。这个过程中,我们需要记录每个点的匹配情况,以及从起点到当前点的路径,这些信息存储在 matchX 和 matchY 数组中。
当我们找到一条增广路径时,需要执行这个 Enlarge 操作。它的作用是将这条增广路径上所有的 X 点与 Y 点的匹配关系进行调整,使得这条路径上所有的 X 点变成已匹配状态,而原来与这些 X 点匹配的 Y 点变成未匹配状态。具体来说,它的实现过程是从最后一个点开始,沿着路径逆向遍历,将每个 X 点与它的前一个 Y 点交换匹配关系。这样做的效果是,增广路径上的所有 X 点都被匹配,而原来与这些 X 点匹配的 Y 点变成未匹配状态,同时新的 Y 点被匹配,这样就完成了一次增广。
相关问题
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 } }
这是一个匈牙利算法的实现代码,用于解决二分图最大匹配问题。其大致思路是按顺序遍历二分图的左侧节点,对每个节点进行增广路径查找,如果找到增广路径则进行匹配,否则进行边权重调整,直到所有节点都被匹配为止。其中的函数包括:
- FindAugmentingPath():查找增广路径。
- SubX_AddY():调整边权重。
- Enlarge():根据找到的增广路径进行匹配。
如果您需要更详细的解释,请让我知道。
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 个点的横向和纵向调整值。通过对原始费用和横向、纵向调整值进行加减操作,就可以得到两点间的实际费用。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)