最优指派问题匈牙利算法的探讨与C_(++)实现

介绍了匈牙利算法的基本理论,并把这个理论通过实例应用到了最优指派问题的解决方案中,给出了可以实现该方法的C++程序。

一个最优指派问题及其算法

设有n项工作.第j(1≤j≤n)项工作需要b_j个工人共同完成.现有m=sum from j=1 to ? b_j个工人,每人做任一工作的产值为已知.如何安排使总产值最高?这一问题是指派问题和[1]中问题的推广。我们给出了这个问题的算法,本文的算法比[1]中算法简便易学。

最优指派问题的一种新方法

借鉴模糊数学的隶属函数思想,针对最优指派问题建立所求问题的隶属矩阵,通过对隶属矩阵的分析,得到问题的最优指派.

一类最优指派问题的动态规划算法

考虑一类较一般的最优指派问题 :欲把m项工作指派n个人去完成 (m≥n) ,要求每项工作只能由一个人来做 ,第i个人可以同时做bi 项工作 ,其中bi 是待求未知数 ,满足di ≤bi≤ei(ei,di 为第i个人所需工作数的上下限 )及∑ni=1bi =m为已知常数 (i=1,2 ,… ,n) ,第i个人做第j项工作所用的时间为cij≥ 0 (i =1,2 ,… ,n ;j=1,2 ,… ,m) .本文给出了求解上述最优指派问题 (使总耗用时间最小 )的动态规划算法 .

基于改进人工蜂群算法的机器人任务最优指派

为了快速准确地求解机器人任务最优指派问题,本文提出了一种改进的人工蜂群算法。考虑到指派问题解决方案离散性的特点,在应用蜂群算法求解问题的过程中对可行解空间进行离散编码;在采蜜蜂和观察蜂更新解时,采用列状态转移的方法生成候选解,保证解的可行性和多样性。实验结果表明,改进的蜂群算法在求解指派问题模型时,具有良好的收敛速度和求解精度。

关于最优指派问题匈牙利算法的改进与句子语义相似度计算

目前国内已有进行句子语义相似度计算过程中，没有考虑到句子中各个词语在该语句中所处的位置以及所起的作用，而是只运用字符串的匹配方法来进行语句相似度计算，还没有考虑词语之间的顺序。本文采用改进的匈牙利算法求出词语的最优配对，并将一个句子中所有词语的配对相似度累加获得该句子的语义相似度。

一类最优指派问题的动态规划模型

考虑一类指派问题：欲指派m个人去做n项工作(m≥n)，要求每个人只做一项工作，第j项工作可以由b_j个人共同去做，其中，b_j(b_j≥1)是待求的未知数，j=1,2,…,n,满足．假定已知第i人做第j项工作的效益为c_ij≥0,i=1,2,…m;j=1,2,…,n.本文建立了求解上述问题最优指派（即使总的效益最大)的动态规划模型．

关于“一类最优指派问题的动态规划模型”的注记

考虑一类较一般的最优指派问题 :欲指派 m个人做 n项工作 (m≥n) ,要求每个人只做一项工作 ,第j项工作可以由 bj个人共同去做 ,其中 bj是待求未知数 ,满足 dj≤ bj≤ ej(即 ej,dj为第 j项工作所需人数的上下限 )及 ∑nj=1bj=m(即每个人都有工作 ) ,dj,ej为已知常数 ,j =1 ,… ,n.第 i人做第 j项工作的效益为 cij≥ 0 ,i =1 ,… ,m;j =1 ,… ,n.本文建立求解上述最优指派问题 (使总的效益最大 )的动态规划模型 ,并将文 [1]作为本文的特例 .

区间指派问题的研究

在分析传统意义的指派问题存在不足的基础上,文章定义了区间指派问题,证明了区间指派问题存在区间最优指派的充分必要条件,并给出了存在区间最优指派的几种情况;另外,通过定义一般区间指派问题的区间悲观最优指派和区间乐观最优指派,从一个方面解决了没有区间最优指派的区间指派问题。

指派问题的树算法

给出了求解指派问题的树算法.该法将指派方案与树枝建立联系,每种指派方案对应一个树枝,通过画指派树讨论所有可能的指派方案,最后经过比较得到最优指派方案.该算法简单易懂,易于掌握,能够找到全部最优指派方案,并且容易编程实现.

用正行列式解瓶颈指派问题

用正行列式作为工具,给出了瓶颈指派问题新的解法,并利用正行列式的值求出了瓶颈指派问题的全部最优解。最后通过一个实例说明该算法的实用和有效性。

指派问题的解法及其在教学分工中的应用

论述了指派问题的数学模型的建立方法和求解过程．指出模型的最优解即问题的最优指派方案有利于更合理地分工以取得最优的综合工作效益．

指派问题的数学模型在食品理化检验工作中的应用

指派问题在管理上应用较广,如何将它应用于食品理化检验还是新课题,对此我们做了初步探讨,使平均报检时间缩短了1.76天,每年人均检验件数增加了2.85倍,人均检验项目数增加了3.36倍。指派问题通过简单的矩阵变换,使各行各列出现零元素,即可得到最优指派方案。本法简单易行,不仅提高了工作效率,而且减少了劳动强度,收到了事半功倍之效。

Fuzzy条件下指派问题的决策研究与计算机处理

Ｆｕｚｚｙ条件下指派问题的决策研究与计算机处理李福俊一、问题的提出：对于给定的ｍ项工作任务，要求ｎ个工作者去完成，在已知每个工作者完成各项不同任务的考核量值的条件下希望得到一个最优方案．这类问题称为经典指派问题。上述指派中要求得到的考核量值是明确的，...

基于云计算的数据查找与加密方案研究

云计算环境下的数据查找与加密技术是目前的研究热点。针对现有方案的不足,提出了一种改进的数据查找与加密方案。在数据查找方面,首先建立了身份管理模型,然后提出了基于权限的身份鉴别算法来实现从系统资源到身份数量之间的最优指派;在数据加密方面,提出了一种可计算加密方案CES,该方案能支持云数据的模糊检索和基本算术运算,有效地对用户的敏感数据进行隐私保护。仿真实验结果表明,方案是有效的,在加、解密性能以及存储与通信开销等方面要优于传统的方法。

SAR景象匹配中边缘特征基准图的制备方法

针对SAR景象匹配基准图制备适应性差及自动化程度低的缺点,提出了一种基于边缘特征的基准图制备方法。首先,组合多种SAR边缘检测算法进行边缘检测;其次,通过对边缘检测点的密度统计分析,得到不同级别的边缘等级图;再次,通过匈牙利法求解边缘点对一一映射的最优指派问题,计算出不同级别的边缘等级图与边缘检测结果图集之间的相似测度值;最后,根据最小相似测度值得到最佳边缘检测级别,并将其对应的边缘检测结果作为边缘特征基准图。实验结果表明,文中方法具有很强的开放性与场景目标适应性,自动化程度高,能有效地提高景象匹配的匹配概率与匹配精度。

匈牙利算法与分枝定界法解决调色问题之比较

通过实例分析了匈牙利算法和分枝定界法的算法特征和过程,讨论了以这两种算法求解具体优化问题时所要采取的算法策略.指出在实际应用算法时,根据问题的局部信息,模型与算法的选择是极其重要的,并进一步提出了借用分枝定界法处理哈密尔顿回路问题的设想.

基于学习的斑马鱼检测与跟踪

群体行为吸引了各个领域众多科学家的兴趣,而斑马鱼作为一种模式生物,被广泛运用为研究群体行为的对象。近年来,由于照相机系统和跟踪算法的发展,使通过分析鱼的运动轨迹来研究群体行为成为了可能。但是,怎样从视频中准确鲁棒地恢复鱼的轨迹仍然是一件非常具有挑战性的问题。为了解决该问题,提出根据鱼的头部特点和成像特征,设计一个基于统计学习的鱼头检测器,从而减少身体形变对跟踪的影响;同时,通过给斑马鱼的运动建模,结合全局匹配算法,使跟踪算法对漏检、错检和短暂的遮挡有很强的容忍性。大量的实验表明所提出的鱼头检测和跟踪算法的准确性和鲁棒性。

基于最优线性指派的多指标群体决策在战时工程保障中的应用

在多指标群体决策问题中 ,如何将个体的偏好评判值集结为群体综合评判值是决策的关键一步。本文给出一种基于最优线性指派模型的多指标群体决策法 。

缩阵分析法——求解指派问题的新方法

本文对缩减矩阵中零位的相关情况和可指派零位的缺额以及矩阵缩减时目标函数最优值的变化进行了分析,提出了有关可指派零位缺额的定理,建立了效率较匈牙利法高的算法。