匈牙利法的Matlab代码及测试

这篇具有很好参考价值的文章主要介绍了匈牙利法的Matlab代码及测试。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

代码:

function [z,x_ij]=xiongyalifa(a)
%输出z为最小值,x_ij为最优解;
b=a;
%确定矩阵维数
s=length(a);

%第一步:使指派问题的系数矩阵经变换,在各行各列中都出现0元素。
%减去每行的最小值
ml=min(a');
for i=1:s
  a(i,:)=a(i,:)-ml(i);
end
%减去每列的最小值
mr=min(a);
for j=1:s
  a(:,j)=a(:,j)-mr(j);
end
% 第二步:进行试指派,以寻求最优解。
num=0;
while(num~=s) %终止条件是独立0元素的个数与s相等
%index为独立0元素:若a(i,j)=0,则index(i,j)=1,否则index(i,j)=0
%flag为线:flag=0无线,flag=1有线过,flag=2交点
%x_ij用以记录a中独立0元素的位置
  index=ones(s);
  index=a&index;
  index=~index;
  %循环后重新初始化flag,x_ij
  flag = zeros(s);
  x_ij = zeros(s);
  %一次循环划线全过程,终止条件是所a=有的零元素均被直线覆盖
  while(sum(sum(index)))
    %找出只有一个0元素的行,对其所在列划线
    for i=1:s
      t=0;
      l=0;
      for j=1:s
        if(flag(i,j)==0&&index(i,j)==1)
          l=l&

文章来源地址https://www.toymoban.com/news/detail-514014.html

到了这里,关于匈牙利法的Matlab代码及测试的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 二分图最大匹配——匈牙利算法详解

    关于二分图的基本知识见:二分图及染色法判定 一位红娘近日遇到一群暧昧男女,被请求成全他们,经验丰富的红娘观察到 一名男生可能有多名青睐的女生,一名女生也可能有多名青睐的男生 ,但是出于道德伦理要求,显然只能两两男女配对,为了尽可能使大家满意,她要

    2024年01月21日
    浏览(46)
  • 数学建模(四)整数规划—匈牙利算法

    目录 一、0-1型整数规划问题 1.1 案例 1.2 指派问题的标准形式 2.2 非标准形式的指派问题 二、指派问题的匈牙利解法  2.1 匈牙利解法的一般步骤 2.2 匈牙利解法的实例 2.3 代码实现 投资问题: 有600万元投资5个项目,收益如表,求利润最大的方案? 设置决策变量: 模型: 指派

    2024年02月11日
    浏览(42)
  • DETR | 基于匈牙利算法的样本分配策略

    如有错误,恳请指出。 前不久,沐神对DETR进行了讲解,其实之前也对DETR进行了介绍,见:论文阅读笔记 | 目标检测算法——DETR。现对DETR的核心内容进行重温,也就是其所提出的目标检测的end-to-end框架,输入的是一张图像,输出的直接是最后的预测标注结果,不再需要后处

    2024年02月11日
    浏览(39)
  • AcWing 372. 棋盘覆盖(二分图&&匈牙利算法)

    输入样例: 输出样例: 解析:         n为100,状压肯定爆。         将每个骨牌看成二分图的一个匹配,即查找二分图的一个最大匹配,匈牙利算法。

    2024年02月14日
    浏览(37)
  • 图论及其应用(匈牙利算法)---期末胡乱复习版

    T1:从下图中给定的 M = {x1y4,x2y2,x3y1,x4y5},用 Hungariam算法【匈牙利算法】 求出图中的 完美匹配 ,并写出步骤。 关于匈牙利算法: 需要注意的是,匈牙利算法仅适用于 二分图 ,并且能够找到完美匹配。 什么是 交替路 ?从一个未匹配点出发,依次经过非匹配边–匹配边

    2024年02月01日
    浏览(68)
  • AcWing 379. 捉迷藏(最小路径点覆盖&&匈牙利算法)

    输入样例: 输出样例:

    2024年02月14日
    浏览(38)
  • 数学建模笔记——整数规划类问题之我见(匈牙利算法)

    目录 浅浅叙述匈牙利算法 基本思路 计算步骤 来一道简单例题 1.1 符号规定 1.2目标函数​编辑       1.3约束条件 ​编辑 1.4代码 题目复述 基本假设 问题分析 符号说明  模型的建立与求解 模型建立思路 模型建立的过程 建立0-1整数规划模型  运用匈牙利方法: 代码实现  

    2023年04月11日
    浏览(50)
  • 平衡运输问题及其表上作业法---指派问题及其匈牙利解法

    一、平衡运输问题及其表上作业法 平衡问题及数学建模  平衡运输问题 :  就是生产数量与销售数量相等的 运输问题 。对总产量等于总需求量的运输问题,可直接采用 表上作业法 求最优运输方案  数学模型:  2、表上作业法 表上作业法步骤: 1 :求解初始可行解(最小元

    2023年04月25日
    浏览(35)
  • 【二分图】 二分图上匹配问题 和 匈牙利算法正确性说明

    本文讨论无权图 思维上没什么难度,但是文字量却比自己想的要多…… 什么是二分图上的匹配?什么是匈牙利算法?   “二分图最大匹配概念、匈牙利算法” 这里引用 Pecco 的介绍。这篇文章写的非常通俗易懂,而且揭示了匈牙利算法(或者说增广路)的本质是“朴素的

    2024年02月13日
    浏览(36)
  • 第三章 图论 No.11二分图,匈牙利算法与点覆盖

    257. 关押罪犯 - AcWing题库 最大最小问题,一眼二分 答案的范围在 [ 1 , 1 e 9 ] [1, 1e9] [ 1 , 1 e 9 ] 之间,二分答案,check(mid) check:将所有权值大于mid的边进行二分,若能得到二分图,返回true,否则返回false 最终将得到最优解ans,所有大于ans的边组成的图为二分图,若是图中有边

    2024年02月12日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包