稳定婚姻匹配问题的一个快速枚举算法

稳定匹配问题是算法理论中的典型问题之一,稳定婚姻匹配问题则是一种解决二部图匹配问题的模型。论文对稳定婚姻匹配问题进行了简单的阐述,并介绍了求解典型稳定婚姻问题的Gale-Shapley算法的基本思想及其性质。为了快速求出所有的稳定匹配结果,提出了基于先序遍历森林的快速枚举算法。由Gale-Shapley算法的性质得到一个定理及其推论,利用得到的推论对算法做了进一步改进和优化。在满足推论的特定条件下,提高了算法的执行效率。     

用回跳法求解稳定婚姻问题

介绍了稳定婚姻问题和解决该问题的回溯法;在回溯法的基础上提出了改进算法回跳法;从理论上和实验上证明了回跳法的效率远高于回溯法的效率。     

典型“稳定婚姻问题”的简明矩阵算法实现

对于典型"稳定婚姻问题",本文借助矩阵(二维数组)给出了一种简明的实现方法。在本算法中,所采用的存储结构和实现方法灵活巧妙,通俗易懂,方便实现;而且用于存储所要处理数据的内存空间相对于其他一些算法节省了一半,空间复杂度为O(1);由于存储结构的巧妙性,算法的时间复杂度在最好的情况下为线性时间N,在最坏的情况下为O(N2)。     

基于稳定匹配的容器部署策略的优化

Docker的发展使得操作系统级虚拟化的容器渐渐兴起,容器即服务(CaaS)也越来越普及。随着容器技术的发展,容器将成为云环境中的主要部署模型,但针对容器的整合部署技术还未得到广泛的研究。容器化云环境中的容器数量众多,如何将众多的容器部署到合适的虚拟机以降低 数据中心能耗,成为了一个亟待解决的问题。因此,文中创新性地将机器学习中的几种相似度计算方法作为稳定匹配算法的偏好规则,同时将已经拟分配过容器的虚拟机继续加入偏好列表,从而将一对一的稳定婚姻匹配算法改进为多对一的稳定匹配,解决了将容器整合到虚拟机上的初始化部署问题。仿真实验结果表明 , 采用优化的稳定匹配算法来初始化将部署容器时,不仅SLA违规较低,而且比FirstFit,MostFull以及Random算法分别约节能12.8%,34.6%和30.87%,其中使用欧氏距离作为稳定匹配算法偏好规则的节能效果最好。     

基于接口连接关系的服务组合启发式算法

针对服务组合规划问题,提出了一种基于服务连接关系的启发式算法.该算法首先根据领域本体中概念条件出现概率提出了一种新的服务接口分量关联程度量化指标,再利用二分图稳定匹配算法解决了多输入输出分量接口匹配问题,在此基础上将服务组合规划抽象为与或图搜索,采用启发式算法实现了服务组合.实验结果表明,该算法能够根据用户请求动态的生成复合服务,通过服务连接分析预处理,可以有效解决输入输出接口多分量的服务连接问题,提高了服务组合效率.     

基于稳定区域的形变指纹匹配算法

针对指纹匹配中的非线性形变问题,首次提出了稳定区域的概念,并给出了一种新颖的基于指纹稳定区域的形变指纹匹配算法。通过稳定区域这一概念,巧妙地把指纹匹配问题转化为寻找两幅指纹中对应稳定区域的问题。该算法通过稳定区域的构造、确认和扩张3个步骤,实现了从点到面再到更大区域,从线性形变区域到非线性形变区域的匹配策略。该算法在国际指纹识别竞赛FVC2004的数据库上进行了测试,实验结果表明,该算法有着良好的匹配性能,并有较强的处理非线性形变的能力。     

新型时空众包平台中的在线三维稳定匹配问题

近年来,时空众包平台正逐步走入人们的生活,并受到研究者的广泛关注.在时空众包平台中,任务分配是一个核心问题,即在满足时间和空间的条件约束下,如何为不同用户分配合适的工人来进行服务.现有的工作往往将最大化任务匹配个数或效用值之和作为研究目标,这些方法关注全局的解决方案,但是没有考虑用户和工人的偏好来提高他们对于分配的满意程度.此外,现有工作大多只考虑用户和工人两种角色,即工人移动到用户当前位置进行服务.但是,新型时空众包平台的中往往包含用户、工人和工作点三种角色,即为用户和工人分配一个工作点来进行服务.基于以上不足,三维时空稳定分配问题被提出.但是,此问题只关注了静态场景,而时空众包平台往往是在线的,即工人和用户发出的任务都是实时出现的.因此,提出了面向新型时空众包平台的三维在线稳定匹配问题和一种基础算法.通过分析基础算法的不足,结合人工智能的方法提出一种改进算法来解决这个问题.采用大量的真实数据和合成数据集来验证算法的高效性和有效性.     

基于改进KAZE的无人机航拍图像拼接算法

为了更好地解决航拍图像易受光照、旋转变化、尺度变化等影响,KAZE算法实时性较差以及基于K近邻的特征匹配算法耗时较长等问题,该文提出了一种基于改进KAZE的无人机航拍图像拼接算法.该方法首先利用加速的KAZE算法提取图像的特征点,采用二进制特征描述子FREAK（Fast retina keypoint）进行特征点描述,然后使用Grid-KNN算法进行特征点粗匹配,利用随机一致性算法对匹配的特征点进一步提纯并计算几何变换模型,最后采用加权平均算法对图像进行融合.实验结果表明,该文所提算法使图像在光照变化、旋转变化及尺度变化下具有较好的性能,且处理速度较KAZE算法与K近邻特征匹配算法有较大提升,是一种稳定、精确度高、拼接效果良好的无人机航拍图像拼接方法.     

多重序列比对的蚁群算法

序列多重比对是生物信息学特别是生物序列分析中的一个重要的操作.提出了一种解决多重序列比对的蚁群算法,利用了人工蚂蚁逐个选择各个序列中的字符进行配对.在算法中,蚂蚁根据信息素、字符匹配得分以及位置偏差等信息决定选择各序列中的字符的概率,通过信息素的更新与调节相结合的策略,以及参数的动态自适应调节方法,较为有效地解决了局部收敛的问题,加强了算法寻求全局最优解的能力.实验显示,该算法可以有效解决多重序列比对问题.     

稳定匹配在高考录取中的运用

现代信息技术对人类社会各个方面都产生了巨大影响。该文较全面的介绍了稳定匹配和G-S算法,并对其在高考录取中的运用做了一定的探索。     

Manipulation complexity and gender neutrality in stable marriage procedures

The stable marriage problem is a well-known problem of matching men to women so that no man and woman who are not married to each other both prefer each other. Such a problem has a wide variety of practical applications, ranging from matching resident doctors, to hospitals to matching students to schools. A well-known algorithm to solve this problem is the Gale–Shapley algorithm, which runs in quadratic time in the number of men/women. It has been proven that stable marriage procedures can always be manipulated. Whilst the Gale–Shapley algorithm is computationally easy to manipulate, we prove that there exist stable marriage procedures which are NP-hard to manipulate. We also consider the relationship between voting theory and stable marriage procedures, showing that voting rules which are NP-hard to manipulate can be used to define stable marriage procedures which are themselves NP-hard to manipulate. Finally, we consider the issue that stable marriage procedures like Gale–Shapley favour one gender over the other, and we show how to use voting rules to make any stable marriage procedure gender neutral.     

A Polynomial-Time Algorithm to Find von Neumann-Morgenstern Stable Matchings in Marriage Games

This paper considers von Neumann-Morgenstern (vNM) stable sets in marriage games. Ehlers (Journal of Economic Theory 134: 537–547, 2007) showed that if a vNM stable set exists in a marriage game, the set is a maximal distributive lattice of matchings that includes all core matchings. To determine what matchings form a vNM stable set, we propose a polynomial-time algorithm that finds a man-optimal matching and a woman-optimal matching in a vNM stable set of a given marriage game. This algorithm also generates a modified preference profile such that a vNM stable set is obtained as the core of a marriage game with the modified preference profile. It is well known that cores of marriage games are nonempty. However, the nonemptiness of cores does not imply the existence of a vNM stable set. It is proved using our algorithm that there exists a unique vNM stable set for any marriage game.     

基于稳定匹配的电子中介匹配研究

介绍了稳定性双边匹配的概念,概括了Gale-Sharply和H-R算法求解1-1和1-k的计算过程.考虑商品的多属性,给出了交易者按综合满意程度对满足自己约束对方的排序计算方法.将Gale-Sharply和H-R算法从理论上扩展到"p-k"情况,用来解决电子中介处理稳定的多对多双边匹配问题.最后证明了扩展算法所得结果的稳定性,并给出了算例.     

A unified approach to finding good stable matchings in the hospitals/residents setting

The hospitals/residents (HR) problem is a many-to-one generalization of the stable marriage (SM) problem. Researchers have been interested in variants of stable matchings that either satisfy a set of additional contraints or are optimal with respect to some cost function. In this paper, we show that broad classes of feasibility and optimization stable matching problems in the HR setting can be solved efficiently provided certain tasks (such as checking the feasibility of a stable matching or computing the cost of a stable matching) can also be done efficiently. To prove our results, we make use of an HR instance’s meta-rotation poset to explore its stable matchings. An algorithm that can discover all the meta-rotations of the instance serves as a starting point for all our algorithms.     

异构网络资源分配：改进多对一转移匹配

随着无线业务的急剧增长,短缺的频谱资源正面临着巨大挑战。采用无线异构网络被视作解决此问题,提高频谱利用率的一种有效手段。但是,由于宏蜂窝和微蜂窝共享相同频谱资源,同层和跨层干扰非常严重,这时如何合理进行资源分配成了一个棘手的问题。针对该问题,根据匹配理论提出了一种改进多对一转移匹配算法进行资源分配。该算法在满足交换条件下,通过微蜂窝用户不断地交换其匹配资源,最终形成稳定转移匹配。仿真结果表明,所提改进转移匹配算法较传统转移匹配算法和改进Gale-Shapley匹配算法性能更易收敛到最优解,同时提高了频谱利用率,降低了计算复杂度。     

An algorithm for a super-stable roommates problem

In this paper, we describe an efficient algorithm that decides if a stable matching exists for a generalized stable roommates problem, where, instead of linear preferences, agents have partial preference orders on potential partners. Furthermore, we may forbid certain partnerships, that is, we are looking for a matching such that none of the matched pairs is forbidden, and yet, no blocking pair (forbidden or not) exists.To solve the above problem, we generalize the first algorithm for the ordinary stable roommates problem.     

基于三视图的自适应加权迭代匹配筛选算法

针对基于三视图的传统三维重建时特征点匹配后保留正确匹配点对数量过少、由图像噪声、拍摄照片时遮挡和震动等因素引起的匹配误差较大等问题,文章提出了一种自适应加权迭代算法,该算法通过给匹配点对加权进行迭代筛选来实现,可以稳定的获得数量较多、结果较准确的匹配点对,从而精确求解三视图空间约束矩阵三焦点张量.实验证明,文章提出自适...     

Stable Marriage with General Preferences

We propose a generalization of the classical stable marriage problem. In our model, the preferences on one side of the partition are given in terms of arbitrary binary relations, which need not be transitive nor acyclic. This generalization is practically well-motivated, and as we show, encompasses the well studied hard variant of stable marriage where preferences are allowed to have ties and to be incomplete. As a result, we prove that deciding the existence of a stable matching in our model is NP-complete. Complementing this negative result we present a polynomial-time algorithm for the above decision problem in a significant class of instances where the preferences are asymmetric. We also present a linear programming formulation whose feasibility fully characterizes the existence of stable matchings in this special case. Finally, we use our model to study a long standing open problem regarding the existence of cyclic 3D stable matchings. In particular, we prove that the problem of deciding whether a fixed 2D perfect matching can be extended to a 3D stable matching is NP-complete, showing this way that a natural attempt to resolve the existence (or not) of 3D stable matchings is bound to fail.     

Antibody-based computing

An application of the antibody’s flexible recognition (i.e. multi-reactivity) to antigenic epitopes to a combinatorial computing is just getting started. The present study discusses an antibody-based computation algorithm to solve a combinatorial problem: the stable marriage problem. The stable marriage problem supposes n men and n women, and each person ranks all members of the opposite sex in a strict order of preference. Under given preference lists, to detect all of “stable” n couples including no affair pairs means to solve this problem. Our algorithm replaces a man and a woman with an antigenic epitope and an antibody respectively, and re-scales a man (woman)’s preference to a woman (man) as strength of a binding affinity between an epitope to the man and an antibody to the woman. Under these settings, we demonstrate a parallel progression of immune reactions can solve the stable marriage problem. This work was presented in part at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008