【图论-匈牙利算法】Hungary Algorithm完整代码（一） 之 matlab实现

=学习参考链接==

博客

分配问题与匈牙利算法

带你入门多目标跟踪（三）匈牙利算法&KM算法

视频

运筹学 | 例题详解指派问题

前言

  • 图论-匈牙利算法原理参见上述参考连接中的博客与BiliBili博主的学习视屏，讲的很好很透彻。强烈建议看完（明白行列变换、找独立零、打勾、划线原理后）再来撸代码。
  • 此处以成本矩阵求解n*n的最优分配问题。

问题描述

在实际中经常会遇到这样的问题，有n项不同的任务，需要 n个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率(或花费的时间或费用)也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成 项任务的总效率最高(或所需时间最少)，这类问题称为分配问题或指派问题。
在这里插入图片描述

matlab代码实现

cost矩阵（n*n）

🔺 mainHA1.m

% 定义成本矩阵
costMatrix=[2,15,13,4;10,4,14,15;9,14,16,13;7,8,11,9];
% 调用匈牙利算法计算分配的结果，已经总成本
[f,D,G]=assign(costMatrix);

匈牙利算法实现主体

🔺 assign.m

function[f,D,G]=assign(B)
% 匈牙利算法实现
% u 和 v 是包含矩阵 B 沿每一行和每一列的最小值的向量
% 从矩阵 B 的相应行和列中减去这些最小值
n=length(B(:,1));
u=min(B,[],2);
f=sum(u);%用于记录最优值
B=B-repmat(u,1,n);
v=min(B,[],1);
f=f+sum(v);%用于记录最优值
B=B-repmat(v,n,1);
C=zeros(n);
while 1
    % 在当前矩阵 B 中找到零元素，并在辅助矩阵 C 中进行标记
    C(find(B==0))=1;
    % 计算辅助矩阵 C 中每行和每列的和，存储在 u 和 v 中。
    E=C;
    u=sum(C,2);
    v=sum(C);
    % 调用 assignz 函数，该函数通过修改 C、D、G、E、u 和 v 来找到零元素的匹配。
    D=zeros(1,n);
    G=zeros(1,n);
    [C,D,G,E,u,v]=assignz(C,D,G,E,u,v);
    num=-1;
    while num<0
        add=find(D==0);
        if isempty(add)
            return;
        end
        % 调用 assignln 函数，该函数寻找未被覆盖的行，并从中找到一条增广路径
        [D,G,E,SP,TP]=assignln(D,G,E,add);
        num=numel(SP)-numel(TP);
    end
    % 更新矩阵 B，通过减去路径中的最小值，并在路径上加上最小值
    add=setdiff(1:n,TP);
    m=min(min(B(SP,add)));
    B(SP,add)=B(SP,add)-m;
    add=setdiff(1:n,SP);
    B(add,TP)=B(add,TP)+m;
    % 更新总成本 f，通过累加路径上的最小值与路径长度的乘积
    f=f+m*num;
end

标记独立零元素

assignz.m

function[C,D,G,E,u,v]=assignz(C,D,G,E,u,v)%标记独立零
while any(u)
    %  % 找到第一个u为1的行
    row=find(u==1,1);
    while row
        % 找到该行中第一个被标记为1的列
        col=find(C(row,:)==1);
        % 更新匹配关系
        D(row)=col;
        G(col)=row;
        E(row,col)=0;
        % 更新u和v
        u=u-C(:,col);
        % 清零相应的行和列
        v(col)=0;
        C(:,col)=0;
        row=find(u==1,1);
    end

    % 找到第一个v为1的列
    col=find(v==1,1);
    while col
        % 找到该列中第一个被标记为1的行
        row=find(C(:,col)==1,1);

        % 更新匹配关系
        D(row)=col;
        G(col)=row;
        E(row,col)=0;
        v=v-C(row,:);
        u(row)=0;
        C(row,:)=0;
        col=find(v==1,1);
    end
     % 如果u仍有非零元素，则找到u和v的非零元素的位置
    if any(u)
        row=find(u,1);
        col=find(C(row,:),1);
        D(row)=col;
        G(col)=row;
        E(row,col)=0;
        u=u-C(:,col);
        u(row)=0;
        v=v-C(row,:);
        v(col)=0;
        C(:,col)=0;
        C(row,:)=0;
    else return;
    end
end

划线（以最少的线覆盖所有的零）—增广路径

assignln.m

function[D,G,E,SP,TP]=assignln(D,G,E,un)%作最少的直线覆盖所有零
S=un;
SP=[];
TP=[];
F=zeros(numel(D));
while ~isempty(S)
    [null,T]=find(E(S,:));
    T=setdiff(T,TP);
    if isempty(T)
        SP=union(SP,S);
        return;
    end
    F(S,T)=E(S,T);
    SP=union(SP,S);
    TP=union(TP,T);
    Stemp=G(T);
    P=find(Stemp==0);
    if ~isempty(P)
        Tun=T(P);
        [r,c]=find(E(S,Tun),1);
        row=S(r);
        col1=Tun(c);
        while 1
            E(row,col1)=0;
            col2=D(row);
            D(row)=col1;
            G(col1)=row;
            if ismember(row,un)
                break;
            end
            E(row,col2)=1;
            row=find(F(:,col2),1);
            col1=col2;
        end
        SP=[];
        return;
    end
    S=Stemp;
end
SP=[];

运行main函数可得最短时间为28

% 输出如下
f =  28

D =  4     2     1     3

G =  3     2     4     1

f为总的时间成本，D为员工，G为任务，即员工4对应3号任务。这是最优的分配结果。

匈牙利算法实例应用

问题描述：n个点从起始位置到目标位置，如何让成本最少？？？

分析：以欧式距离构建成本矩阵cost

计算每个点到目标点的距离，构建权重代价

getDistance.m

function [Distance] = getDistance(Agent,Goal)
    n=length(Agent(:,1));
    m=length(Goal(:,1));
    for i=1:n
        for j=1:m
            Distance(i,j)=(Agent(i,1)-Goal(j,1))^2+(Agent(i,2)-Goal(j,2))^2;
            Distance(i,j)=sqrt(Distance(i,j));
        end
    end
end

修改mainHA1.m函数

mainHA2.m

Agent=[-5,0;0,-1;0,-2;0,-3;-1,0;-1,-1;-1,-2;-1,-3;-2,0;-2,-1;-2,-2;-2,-3;-2,-4;-2,-5];
Goal=[5,5;6,6;7,7;8,8;4,6;3,7;2,8;2,9;8,9;3,10;7,10;4,10;6,10;5,9];

matrix=getDistance(Agent,Goal);

% 执行匈牙利算法，返回分配结果
[f,D,G]=assign(matrix);

% 使用 plot 函数绘制了连接线，同时在图中用蓝色和红色分别标记位置
num=length(D);
for i=1:num
plot([Agent(i,1),Goal(D(i),1)],[Agent(i,2),Goal(D(i),2)])
hold on
plot(Agent(i,1),Agent(i,2),'.','Color','b','MarkerSize',50); 
hold on
plot(Goal(D(i),1),Goal(D(i),2),'.','Color','r','MarkerSize',50); 
hold on
end

set(gca,'XminorGrid','on');
set(gca,'YminorGrid','on');axis equal
hold off

运行main函数可得最短距离为168.3064

  • 下面是各个点的分配结果
f = 
168.3064
D =
8	11	2	4	12	14	5	1	7	10	6	13	9	3
G = 
8	3	14	4	7	11	9	1	13	10	2	5	12	6
  • 结果显示如图
    连线表示各个点的分配结果

图论-匈牙利算法matlab实现

🐑 🐑 🐑 🐑 🐑 🐑 🐑 🐑 🐑 🐑 🐑 🐑 🐑 🐑 🐑 🐑 🐑 🐑 🐑 🐑 🐑 🐑 🐑 🐑 🐑 🐑 🐑 🐑 🐑 🐑 🐑 🐑 🐑 🐑

博文中代码整理后的下载链接

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/240084.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

自定义日志打印功能--C++

自定义日志打印功能--C++

一、介绍 日志是计算机程序中用于记录运行时事件和状态的重要工具。通过记录关键信息和错误情况&#xff0c;日志可以帮助程序开发人员和维护人员追踪程序的执行过程&#xff0c;排查问题和改进性能。 在软件开发中&#xff0c;日志通常记录如下类型的信息&#xff1a; 事件信…
阅读更多...
关于碰撞试验

关于碰撞试验

主要参数&#xff1a; 冲击与碰撞试验的主要参数及调整方法 - 百度文库 碰撞试验的技术指标包括&#xff1a;峰值加速度、脉冲持续时间、速度变化量&#xff08;半正弦波&#xff09;、每方向碰撞次数。 加速度&#xff1a;冲击的强度&#xff0c;单位为g&#xff1b;一般为3…
阅读更多...
Zygote 进程启动过程

Zygote 进程启动过程

首语 在Android系统中&#xff0c;DVM(Dalvik虚拟机)和ART、应用程序进程以及运行系统的关键服务的SystemServer进程都是由Zygote进程创建的&#xff0c;也可以将其称之为孵化器&#xff0c;它通过fork(复制进程)的形式来创建应用程序进程和SystemServer进程。 Zygote进程是在…
阅读更多...
记录一次chatGPT人机协同实战辅助科研——根据词库自动进行情感分析

记录一次chatGPT人机协同实战辅助科研——根据词库自动进行情感分析

有一个Excel中的一列&#xff0c;读取文本判断文本包含积极情感词.txt和消极情感词.txt的个数&#xff0c;分别生成两列统计数据 请将 ‘your_file.xlsx’ 替换为你的Excel文件名&#xff0c;Your Text Column’替换为包含文本的列名。 这个程序首先读取了积极和消极情感词&…
阅读更多...
（第68天）DBCA 克隆 PDB

（第68天）DBCA 克隆 PDB

介绍 在前面课程我们讲过使用 DBCA 创建数据库以及搭建 DataGuard 等功能，在多租户这章节，要讲下如何使用 DBCA 克隆 PDB。 18C 开始支持使用 DBCA 在本地 CDB 中克隆 PDB19C 升级支持使用 DBCA 克隆 PDB 到远端 CDB 中19C 升级支持使用 DBCA 重定向迁移 PDB 到远端 CDB 中本…
阅读更多...
2023/12/12作业

2023/12/12作业

思维导图 作业&#xff1a; 成果图 代码 #include "widget.h" #include "ui_widget.h" Widget::Widget(QWidget *parent) : QWidget(parent) , ui(new Ui::Widget) { speechernew QTextToSpeech(this); ui->setupUi(this); //一直获取当前时间 idst…
阅读更多...
海思越影系列3516DV500/3519DV500/3519AV200/SD3403平台的AI一体化工业相机设计思路

海思越影系列3516DV500/3519DV500/3519AV200/SD3403平台的AI一体化工业相机设计思路

随着工业自动化的发展&#xff0c;生产线对机器视觉的数量要求越来越多&#xff0c;由于数量的增加&#xff0c;视觉系统占的空间也越来越大&#xff0c;给生产线的布局带来困扰。 另一方面随着视觉SOC的发展&#xff0c;越来越多的视觉SOC都逐渐带有一定的算力&#xff0c;一体…
阅读更多...
AI全栈大模型工程师(二十八)如何做好算法备案

AI全栈大模型工程师(二十八)如何做好算法备案

互联网信息服务算法 什么情况下要备案&#xff1f; 对于B2B业务&#xff0c;不需要备案。 但在B2C领域&#xff0c;一切要视具体情况而定。 如果我们自主训练大型模型&#xff0c;这是必要的。 但如果是基于第三方模型提供的服务&#xff0c;建议选择那些已获得备案并且具有较大…
阅读更多...
DevOps - Spug 自动化运维平台

DevOps - Spug 自动化运维平台

关于Spug 官网&#xff1a;https://spug.cc/ Spug&#xff1a;麻雀&#xff0c;麻雀虽小&#xff0c;五脏俱全。 Spug是面向中小型企业设计的轻量级无Agent的自动化运维平台&#xff0c;整合了主机管理、主机批量执行、主机在线终端、文件在线上传下载、应用发布部署、在线任…
阅读更多...
[Angular] 笔记1：开发设置 ， 双向绑定

[Angular] 笔记1：开发设置 ， 双向绑定

1 设置开发环境 1.1 安装 node 下载 node&#xff0c;因为要使用 npm 工具&#xff0c;教程中使用 Angualr 14, 最新版 node 20 用不了&#xff0c;安装 node 16 就可以。 1.2 安装 Angular CLI Angular CLI 是用于创建 Angular 工程的工具集&#xff0c;使用如下命令&…
阅读更多...
redis的深度理解

redis的深度理解

上篇博客我们说到了redis的基本概念和基本操作&#xff0c;本篇我们就更深入去了解一些redis的操作和概念&#xff0c;我们就从red的主从同步、redis哨兵模式和redis集群三个方面来了解redis数据库 一、主从同步 像MySQL一样&#xff0c;redis是支持主从同步的&#xff0c;而…
阅读更多...
面试 JVM 八股文五问五答第二期

面试 JVM 八股文五问五答第二期

面试 JVM 八股文五问五答第二期 作者&#xff1a;程序员小白条&#xff0c;个人博客 相信看了本文后&#xff0c;对你的面试是有一定帮助的&#xff01; ⭐点赞⭐收藏⭐不迷路&#xff01;⭐ 1.JVM运行时数据区有几部分?&#xff08;JVM内存布局&#xff09;虚拟机栈和本地方…
阅读更多...
nodejs微信小程序＋python＋PHP社区居民信息管理及数据分析系统-计算机毕业设计推荐django

nodejs微信小程序＋python＋PHP社区居民信息管理及数据分析系统-计算机毕业设计推荐django

目 录 摘 要 I ABSTRACT II 目 录 II 第1章 绪论 1 1.1背景及意义 1 1.2 国内外研究概况 1 1.3 研究的内容 1 第2章 相关技术 3 2.1 nodejs简介 4 2.2 express框架介绍 6 2.4 MySQL数据库 4 第3章 系统分析 5 3.1 需求分析 5 3.2 系统可行性分析 5 3.2.1技术可行性&#xff1a;…
阅读更多...
SQL数列

SQL数列

SQL数列 1、数列概述2、SQL数列2.1、简单递增序列2.2、等差数列2.3、等比数列3、SQL数列的应用3.1、连续问题3.2、多维分析1、数列概述 数列是最常见的数据形式之一，实际数据开发场景中遇到的基本都是有限数列。常见的数列例如：简单递增序列、等差数列、等比数列等 如何充分…
阅读更多...
汽车IVI中控开发入门及进阶（十一）：ALSA音频

汽车IVI中控开发入门及进阶（十一）：ALSA音频

前言 汽车中控也被称为车机、车载多媒体、车载娱乐等，其中音频视频是非常重要的部分，音频比如播放各种格式的音乐文件、播放蓝牙接口的音乐、播放U盘或TF卡中的音频文件，如果有视频文件也可以放出音频，看起来很简单，在windows下音乐播放器很多，直接打开文件就能播放各…
阅读更多...
记录 | linux安装Manim

记录 | linux安装Manim

linux 安装 Manim sudo apt update sudo apt install build-essential python3-dev libcairo2-dev libpango1.0-dev ffmpeg sudo apt install xdg-utilsconda create manim_py39 python3.9 conda activate manim_py39pip install manim安装好环境后来测试一个例程&#xff0c;…
阅读更多...
多维时序 | MATLAB实现BWO-CNN-BiGRU-Multihead-Attention多头注意力机制多变量时间序列预测

多维时序 | MATLAB实现BWO-CNN-BiGRU-Multihead-Attention多头注意力机制多变量时间序列预测

多维时序 | MATLAB实现BWO-CNN-BiGRU-Multihead-Attention多头注意力机制多变量时间序列预测 目录 多维时序 | MATLAB实现BWO-CNN-BiGRU-Multihead-Attention多头注意力机制多变量时间序列预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 MATLAB实现BWO-CNN-B…
阅读更多...
向ChatGPT提特殊问题，可提取原始训练数据！

向ChatGPT提特殊问题，可提取原始训练数据！

随着ChatGPT等模型的参数越来越大&#xff0c;预训练数据也呈指数级增长。谷歌DeepMind、华盛顿大学、康奈尔大学等研究人员发现,无论是开源还是闭源模型&#xff0c;在训练过程中皆能记住一定数量的原始训练数据样本。 如果使用特定的恶意攻击&#xff0c;便能轻松地从模型中…
阅读更多...
Pytorch中Group Normalization的具体实现

Pytorch中Group Normalization的具体实现

Group Normalization (GN) 是一种用于深度神经网络中的归一化方法&#xff0c;它将每个样本划分为小组&#xff0c;并在每个小组内进行标准化。与批归一化&#xff08;Batch Normalization&#xff09;不同&#xff0c;Group Normalization 不依赖于小批量数据&#xff0c;因此…
阅读更多...
论文阅读——ScanQA

论文阅读——ScanQA

ScanQA: 3D Question Answering for Spatial Scene Understanding 输入&#xff1a;点云P和问题Q&#xff0c;输出&#xff1a;答案A 点云p由三维坐标点组成。本文模型使用额外的点云特征&#xff1a;点云高度、颜色、法线和多视图图像特征&#xff0c;这些特征将 2D 外观特征投…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站