`
leonzhx
  • 浏览: 791846 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论
阅读更多

1.  Stable Matchings

    --  Consider two node sets U and V ("men" and "women")

    --  For simplicity: Assume |U| = |V| = n.

    --  Each node has a ranked order of the nodes on the other side. (different for different nodes)

        Examples: Hospitals & residents, colleges & applicants.

    --  Stable matching: A perfect matching (i.e., matches each node of U to a distinct node of V) such that: if u in U and v in V are not

matched, then either u likes its mate v' better than v, or v likes its mate u' better than u.

 

2.  Gale-Shapley Proposal Algorithm

    --  While there is an unattached man u

        -- u proposes to the top woman v on his preference list who hasn't rejected him yet

        -- Each woman entertains only the best proposal received so far

           [Invariant: current engagements = a matching]

    --  Terminates with a stable matching after <= n^2 iterations.

        -- Each man makes <= n proposals ==> <= n^2 iterations.

        -- Terminates with a perfect matching.

            -- If not, some man rejected by all women. ==> All n women engaged at conclusion of algorithm ==> All n men engaged at end, as well [contradiction]

        -- Terminates with a stable matching. Consider some u, v not matched to each other.

            -- Case 1: u never proposed to v. ==> u matched to someone he prefers to v.

            -- Case 2: u proposed to v. ==> v got a better offer, ends up matched to someone she prefers to u. 

            

分享到:
评论

相关推荐

    stable matching 算法设计与分析实验报告

    一、 实验目的 (1)通过将稳定匹配算法具体编程实验, 熟悉算法分析与设计的全过程,也即熟悉怎么分析实际问题,怎么设计算法,怎么分析算法。熟悉算法的性能特点及不足之处。从概貌上了解算法分析设计的整个过程。...

    第十章_稳定婚姻匹配问题_tapev1i_marriage_稳定婚姻匹配问题_

    稳定婚姻匹配问题(Stable Marriage Problem,简称SMP)是一个著名的数学问题,源自经济学和博弈论领域,由Gale和Shapley在1962年提出。它旨在解决两个集合之间的配对问题,比如男性和女性之间的婚姻匹配,使得没有...

    稳定匹配算法,贪心算法,动态规划,interval-partitioning算法

    用代码实现stable matching 算法,要求能成功达到稳定匹配效果,尽量降低算法复杂度。 一、实验目的 1.掌握随机快速排序的思想 2.掌握随机快速排序的实现方法 一、实验目的 了解贪心算法的思想,掌握interval-...

    01StableMatching.pdf

    稳定匹配问题(Stable Matching Problem)是算法设计中一个重要的概念,主要应用于资源分配或配对场景,如本文中提到的医学院学生与医院的匹配。该问题的目标是找到一种匹配方式,使得没有医院和学生可以通过互相...

    01StableMatching-2x2.pdf

    稳定匹配问题(Stable Matching)是算法设计中的一个重要概念,主要应用于资源分配、配对问题等领域,例如在本文中给出的实例:将医学院学生与医院进行配对。稳定匹配问题的目标是找到一种分配方式,使得没有医院和...

    Paper 2_resourceallocation_d2d_

    压缩包中的文件“Distributed resource allocation in D2D communication networks with energy harvesting relays using stable matching.pdf”暗示了论文可能采用了分布式的方法来解决资源分配问题,并引入了能量...

    国科大卜东波算法期末考试资料平时作业

    ##### 1.1 Stable Matching Problem (稳定匹配问题) **知识点**: 稳定匹配问题主要探讨如何在一组男人和一组女人之间找到一种稳定的配对方式,使得不存在一对男女,他们相互更愿意与对方而不是当前的配对对象。该...

    稳定匹配GS算法

    GS stable matching的源代码,有一些必要的注释。这份代码采用C++语言,通过了许多OJ的在线测试,正确性可以保证。希望可以帮助到大家。

    贝岭的matlab的代码-Front-End-Sample-Codes:示例代码

    贝岭的matlab的代码###Belle Et Glamour示例代码在我为我们的商店网站所做的工作中 ...头文件 ...样式文件 ###Email ...Matching Algorithm 用 Ja​​va 编码 Advisee.java 顾问.java 修改的GaleShapley.java

    基于稳定匹配的选择和内存增强型MOEA / D用于进化动态多目标优化

    5. 稳定匹配(Stable Matching, STM):这是一种由经济学家提出的方法,具有坚实的理论基础,并已在许多领域得到应用。STM的引入是为了将稳定匹配模型应用到动态多目标优化中,以提高算法性能。 6. 稳定匹配模型...

    An Ultra-Wideband Conformal Capsule Antenna with Stable Impedance Matching

    标题中提到的“An Ultra-Wideband Conformal Capsule Antenna with Stable Impedance Matching”,意指一种具有宽频带特性及稳定阻抗匹配的共形胶囊天线。此类天线的关键特征在于其与胶囊壳体内壁的一体化设计,以及...

    stableMatch:稳定匹配的javacode

    稳定匹配(Stable Matching)是一种在计算机科学和经济学中广泛使用的算法,特别是在分配问题和配对问题中。这个算法主要用于解决两个集合之间的匹配问题,确保没有两个元素更愿意彼此匹配而不是他们当前的匹配。在...

    V2G智能电网中基于匹配理论的旅行计划感知计费算法

    文章中提到的关键词包括“vehicle-to-grid”、“traveling plan aware”、“stable matching”和“online scheduling”。这些关键词揭示了该研究的核心内容,即在智能电网的背景下,如何通过智能调度算法提高电动...

    matching_匹配_

    一对一的匹配理论,又称为稳定婚姻问题(Stable Marriage Problem),最早由Gale和Shapley两位学者提出。这个问题的基本设定是有一群男性和一群女性,每个人都有一份按照喜好顺序排列的异性名单。目标是找到一种匹配...

    matlab精度检验代码-Stable-Matching-In-Social-Network:这是标题为“各种社交网络中的稳定匹配”的论文的源

    matlab精度检验代码社会网络中的稳定匹配 该存储库包含期刊论文“各种社会网络结构中的稳定匹配”的支持材料。 稳定匹配研究了如何将两个不相交集的元素配对,以实现基于所有参与者的偏好列表满足他们的匹配的目的。...

    stable-marriage

    这个项目主要是用Java编程语言实现的,旨在解决大学配对或国家居民匹配计划(NRMP, National Resident Matching Program)所面临的问题。NRMP是一个实际应用稳定婚姻问题的典型例子,主要用于医学毕业生与医院实习...

    matching:解决配对游戏的软件包

    使用pip最容易安装该库: $ python -m pip install matching但是,如果您想从源代码安装它,请继续克隆GitHub存储库: $ git clone https://github.com/daffidwilde/matching.git$ cd matching$ python

    SIFT—matlab代码

    SIFT-based image registration procedure is the SIFT feature matching algorithm for matching feature points at home and abroad a hot area of research and the difficulties in matching their ability to ...

Global site tag (gtag.js) - Google Analytics