两个人结婚的最快算法 [英] Fastest algorithm for set of two people to marry eachother

问题描述

我想不出一个算法解决这个问题。问题是：
有两套，设置M包含男人名单，设置F包含女人名单。

现在有一套包含允许婚姻的婚姻，假设（a，1）意味着有可能男方 a 与女方 1 和女方 1 结婚结婚男人 a 。

婚姻只能在推荐列表中的合作伙伴匹配时完成。如果来自 M 的每个男人都可以从与名字相对应的推荐列表中结婚，并且与列表<$ c $中的女人相同，我们称之为成功 C>˚F。我们称之为不成功。

---

示例1

 列表M = {a，b，c，d} 
列表F = {1,2,3,4} 
推荐列表（a，4），（b，1），（b，2），（c，3），（c，4），（d，1），（d，4）} 
  

a 可以结婚 1 ， b 可以结婚 2 ， c 可以结婚 3 ， d 可以结婚 4 。
Output =Sucess



示例2



 列表M = {a，b，c，d} 
列表F = {1,2,3,4} 
推荐列表= {（a，1），（ （b，2），（c，3），（c，1），（d，1），（d，2）} 
  

不可能与女人结婚 4 ，因为在推荐列表中有女人 4 作为她的伴侣。

输出=不可用

---

我需要最快的算法来确定成功或不成功

解决方案创建集群，如下所示：

M1 =所有男人都有一场比赛

M2 =所有的男人有两场比赛

W1 =所有的女人都有一场比赛

...

p>

现在，您可以找到来自M1和W1（平凡匹配）的所有匹配，并将它们从集合中取出。现在，让我们计划最低重力（人类聚类指数+女性聚类指数是最小的）对并将它们回溯。处理子案例就像处理主案例一样。

I can't think of an algorithm for this problem.The problem is: There are two sets, set "M" contains List of men, set "F" contains a list of women.

Now there is a set "Marriage" which contains permitted marriages, suppose (a,1) would mean that it is possible for man a to marry woman 1 and woman 1 to marry man a.

Marriages can only be done if partner matches from recommended list. We call it "Success" if from each man from M it is possible to marry someone from the recommended list corresponding to their name, and same for woman from List F. Else we call it "unsuccessful"

---

EXAMPLE 1

List M = {a,b,c,d}
List F= {1,2,3,4}
Recommended List = { (a,1),(a,4),(b,1),(b,2),(c,3),(c,4),(d,1),(d,4) }

a can marry 1, b can marry 2, c can marry 3, d can marry 4. Output = "Sucess"

EXAMPLE 2

List M = {a,b,c,d} 
List F= {1,2,3,4}
Recommended List = { (a,1),(a,3),(b,1),(b,2),(c,3),(c,1),(d,1),(d,2) }

It isn't possible to marry woman 4 because there is no pair possible in the recommended list which has woman 4 as her partner.

Output = "Unsucessful"

---

I need the fastest possible algorithm to determine success or unsuccess

解决方案

Let create clusters, like this:

M1 = All men having a single match

M2 = All men having two matches

W1 = All women having a single match

...

Now, you find all matches from M1 and W1 (trivial matches) and take them out of the set. Now, let's plan the pairs of the lowest gravity (man cluster index + women cluster index is a minimum) and backtrack them. Handle the sub-cases just as you handled the main case.

这篇关于两个人结婚的最快算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！