KM算法，C语言版本和Matlab版本

2023-12-02 20:44
文章标签 算法 语言 matlab km 版本

本文主要是介绍KM算法，C语言版本和Matlab版本，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里我们不多介绍原理，直接看代码就好了。

C语言版本

#include<stdio.h>
#include<string.h>
const int maxn=305;
const int INF=(1<<30)-1;
int g[maxn][maxn];
int lx[maxn],ly[maxn];
int match[maxn];
bool visx[maxn],visy[maxn];
int slack[maxn];
int n;
bool dfs(int cur)
{int y,t;visx[cur]=true;for(y=1;y<=n;y++){if(visy[y])continue;t=lx[cur]+ly[y]-g[cur][y];if(t==0){visy[y]=true;if(match[y]==-1||dfs(match[y])){match[y]=cur;return true;}}else if(slack[y]>t)slack[y]=t;}return false;
}
int KM()
{int i,j,x;memset(match,-1,sizeof(match));memset(ly,0,sizeof(ly));for(i=1;i<=n;i++){lx[i]=-INF;for(j=1;j<=n;j++)if(g[i][j]>lx[i])lx[i]=g[i][j];}//对ly[i]置0,对lx[i]取每行的最大值for(x=1;x<=n;x++){for(i=1;i<=n;i++)slack[i]=INF;while(true){memset(visx,false,sizeof(visx));memset(visy,false,sizeof(visy));if(dfs(x))break;int d=INF;for(i=1;i<=n;i++){if(!visy[i]&&d>slack[i])d=slack[i];}for(i=1;i<=n;i++){if(visx[i])lx[i]-=d;}for(i=1;i<=n;i++){if(visy[i])ly[i]+=d;elseslack[i]-=d;}}}int result=0;for(i=1;i<=n;i++)if(match[i]>-1)result+=g[match[i]][i];return result;
}
int main()
{int cost,i,j;while(scanf("%d",&n)!=EOF){for(i=1;i<=n;i++){for(j=1;j<=n;j++){scanf("%d",&cost);g[i][j]=cost;}}printf("%d\n",KM());}return 0;
}

Matlab版本

% 带权二部图匹配（KM算法）
clc
clear
close allglobal N
global adj_matrix
global label_left
global label_right
global match_right
global visit_left
global visit_right
% 左右各有N个点
% KM算法要求左右两边的节点数相等，可以通过添加虚拟节点的方法实现
N = 5;
adj_matrix = [3 4 6 4 9;6 4 5 3 8;7 5 3 4 2;6 3 2 2 5;8 4 5 4 7];
% N = 9;
% adj_matrix = round(rand(N)*100);
% adj_matrix(adj_matrix<70) = 0;
% 初始化顶标
label_left = max(adj_matrix, [], 2);
label_right = zeros(N, 1);
% 初始化匹配结果
match_right = ones(N, 1) * nan;
% 初始化辅助变量
visit_left = ones(N, 1) * false;
visit_right = ones(N, 1) * false;
res = KM();% KM主函数
function res = KM()
global N
global adj_matrix
global label_left
global label_right
global match_right
global visit_left
global visit_rightgraph_num = 1;
display_graph(graph_num, '原始二部图');
% 对左边的点依次进行处理
for i = 1: Nwhile 1% 重置辅助变量visit_left = ones(N, 1) * false;visit_right = ones(N, 1) * false;% 能找到可行匹配if find_path(i)break;end% 不能找到可行匹配，修改顶标% (1)将所有在增广路中的X方点的label全部减去一个常数d% (2)将所有在增广路中的Y方点的label全部加上一个常数dd = Inf;for j = 1: Nif visit_left(j)for k = 1: Nif ~visit_right(k)% 左边的点中已经访问过的点，即已经匹配过的点可能需要重新匹配以得到更大的总权值，% 所以修改顶标，往子图中添加一条边，重新寻找增广路看能不能增广% 取与左边的点相邻的未匹配边中跟当前存在子图中的以该点为端点的边相差最小的两条边% 这样才能保持总权值最大d = min(d, label_left(j) + label_right(k) - adj_matrix(j, k));endendendendfor k = 1: Nif visit_left(k)label_left(k) = label_left(k) - d;endif visit_right(k)label_right(k) = label_right(k) + d;endendendgraph_num = graph_num + 1;display_graph(graph_num, ['第' num2str(i) '步']);
endgraph_num = graph_num + 1;
display_graph(graph_num, '最终结果');res = 0;
for j = 1: Nif match_right(j) >=0 && match_right(j) < Nres = res + adj_matrix(match_right(j), j);end
end
end% 寻找增广路，深度优先
function result = find_path(i)
global N
global adj_matrix
global label_left
global label_right
global match_right
global visit_left
global visit_right
visit_left(i) = true;
for j = 1: length(adj_matrix(i, :))match_weight = adj_matrix(i, j);if visit_right(j)% 已被匹配（解决递归中的冲突）continue;endgap = label_left(i) + label_right(j) - match_weight;% 当 gap == 0 时 x_i 和 y_j 之间存在一条边，且该边是当前 x_i 可以匹配的权值最大的边if gap == 0% 找到可行匹配visit_right(j) = true;% j未被匹配，或虽然j已被匹配，但是j的已匹配对象有其他可选备胎% 此处同匈牙利算法if isnan(match_right(j)) || find_path(match_right(j))match_right(j) = i;result = true;return;endend
end
result = false;
return;
endfunction display_graph(graph_num, title_name)
global N
global adj_matrix
global label_left
global label_right
global match_right
global visit_left
global visit_right
figure(graph_num);
set(gcf, 'Position', [100, 100, 1000, 500]);
subplot(1,2,1);
cla
set( gca, 'XTick', [], 'YTick', [] );
set( gca, 'TickLength', [0 0]);
box on
hold on
xlim([-1, 2]);
ylim([-N, 1]);
temp = N - 1;
% 绘制匹配边
for j = 1: length(match_right)if ~isnan(match_right(j))plot([0, 1], [(match_right(j) - 1) * -temp/(N-1), (j - 1) * -temp/(N-1)], 'r', 'LineWidth', 2); end
end
% 绘制点
scatter(zeros(1, N), 0:-temp/(N-1):-temp, 20, [217/255 83/255 25/255], 'filled');
scatter(ones(1, N), 0:-temp/(N-1):-temp, 20, [0 114/255 189/255], 'filled');
for j = 1: Ntext(-0.2, (j - 1) * -temp/(N-1), ['x_' num2str(j)]);
end
for j = 1: Ntext(1.1, (j - 1) * -temp/(N-1), ['y_' num2str(j)]);
end
for j = 1: Ntext(-0.5, (j - 1) * -temp/(N-1), num2str(label_left(j)), 'Color', [217/255 83/255 25/255], 'FontSize', 15);
end
for j = 1: Ntext(1.4, (j - 1) * -temp/(N-1), num2str(label_right(j)), 'Color', [0 114/255 189/255], 'FontSize', 15);
endtitle(title_name);% 边权重
subplot(1,2,2);
cla
set( gca, 'XTick', [], 'YTick', [] );
set( gca, 'TickLength', [0 0]);
box on
hold on
xlim([-1, N]);
ylim([-N, 1]);
for j = 0 : N-1plot([j, j], [-N, 1], 'k') ;
end
for j = -N+1 : 0plot([-1, N], [j, j], 'k') ;
end
for j = 1: Ndisplay_text(j, 0, ['x_' num2str(j)], 0);
end
for j = 1: Ndisplay_text(0, j, ['y_' num2str(j)], 0);
end
for i = 1: Nfor j = 1: Nif match_right(j) == idisplay_text(i, j, num2str(adj_matrix(i,j)), 1);elsedisplay_text(i, j, num2str(adj_matrix(i,j)), 0);endend
end
% saveas(gcf, [num2str(graph_num) '.png']);
end% 在x行y列显示t文本
function display_text(x, y, t, bold)
if boldtext(y - 0.5, -x + 0.5, t, 'FontSize', 15, 'FontWeight', 'bold', 'Color', 'r');
elsetext(y - 0.5, -x + 0.5, t, 'FontSize', 15, 'FontWeight', 'normal', 'Color', 'k');
end
end

有需要再matlab中改代码的联系我。私信支持付费。！

蜂窝用户匹配问题！等等！

这篇关于KM算法，C语言版本和Matlab版本的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/446749。

相关文章

Java中的雪花算法Snowflake解析与实践技巧

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.
阅读更多...
Go语言中nil判断的注意事项(最新推荐)

Go语言中nil判断的注意事项(最新推荐)

《Go语言中nil判断的注意事项(最新推荐)》本文给大家介绍Go语言中nil判断的注意事项,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1.接口变量的特殊行为2.nil的合法类型3.nil值的实用行为4.自定义类型与nil5.反射判断nil6.函数返回的
阅读更多...
Go语言数据库编程GORM 的基本使用详解

Go语言数据库编程GORM 的基本使用详解

《Go语言数据库编程GORM的基本使用详解》GORM是Go语言流行的ORM框架,封装database/sql,支持自动迁移、关联、事务等,提供CRUD、条件查询、钩子函数、日志等功能,简化数据库操作... 目录一、安装与初始化1. 安装 GORM 及数据库驱动2. 建立数据库连接二、定义模型结构体三、自动迁
阅读更多...
Go语言代码格式化的技巧分享

Go语言代码格式化的技巧分享

《Go语言代码格式化的技巧分享》在Go语言的开发过程中,代码格式化是一个看似细微却至关重要的环节,良好的代码格式化不仅能提升代码的可读性,还能促进团队协作,减少因代码风格差异引发的问题,Go在代码格式... 目录一、Go 语言代码格式化的重要性二、Go 语言代码格式化工具：gofmt 与 go fmt（一）
阅读更多...
使用jenv工具管理多个JDK版本的方法步骤

使用jenv工具管理多个JDK版本的方法步骤

《使用jenv工具管理多个JDK版本的方法步骤》jenv是一个开源的Java环境管理工具,旨在帮助开发者在同一台机器上轻松管理和切换多个Java版本,：本文主要介绍使用jenv工具管理多个JD... 目录一、jenv到底是干啥的？二、jenv的核心功能（一）管理多个Java版本（二）支持插件扩展（三）环境隔
阅读更多...
Go语言中泄漏缓冲区的问题解决

Go语言中泄漏缓冲区的问题解决

《Go语言中泄漏缓冲区的问题解决》缓冲区是一种常见的数据结构,常被用于在不同的并发单元之间传递数据,然而,若缓冲区使用不当,就可能引发泄漏缓冲区问题,本文就来介绍一下问题的解决,感兴趣的可以了解一下... 目录引言泄漏缓冲区的基本概念代码示例：泄漏缓冲区的产生项目场景：Web 服务器中的请求缓冲场景描述代码
阅读更多...
Go语言如何判断两张图片的相似度

Go语言如何判断两张图片的相似度

《Go语言如何判断两张图片的相似度》这篇文章主要为大家详细介绍了Go语言如何中实现判断两张图片的相似度的两种方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 在介绍技术细节前，我们先来看看图片对比在哪些场景下可以用得到：图片去重：自动删除重复图片，为存储空间"瘦身"。想象你是一个
阅读更多...
Go语言中Recover机制的使用

Go语言中Recover机制的使用

《Go语言中Recover机制的使用》Go语言的recover机制通过defer函数捕获panic,实现异常恢复与程序稳定性,具有一定的参考价值,感兴趣的可以了解一下... 目录引言Recover 的基本概念基本代码示例简单的 Recover 示例嵌套函数中的 Recover项目场景中的应用Web 服务器中
阅读更多...
MySQL版本问题导致项目无法启动问题的解决方案

MySQL版本问题导致项目无法启动问题的解决方案

《MySQL版本问题导致项目无法启动问题的解决方案》本文记录了一次因MySQL版本不一致导致项目启动失败的经历,详细解析了连接错误的原因,并提供了两种解决方案：调整连接字符串禁用SSL或统一MySQL... 目录本地项目启动报错报错原因：解决方案第一个：第二种：容器启动mysql的坑两种修改时区的方法：本地
阅读更多...
conda安装GPU版pytorch默认却是cpu版本

conda安装GPU版pytorch默认却是cpu版本

《conda安装GPU版pytorch默认却是cpu版本》本文主要介绍了遇到Conda安装PyTorchGPU版本却默认安装CPU的问题,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的... 目录一、问题描述二、网上解决方案罗列【此节为反面方案罗列！！！】三、发现的根本原因[独家]3.1 p
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2