匹配算法

 

我正在编写一个应用程序，将用户的人口分成两对，以便共同完成一项任务。 每个用户可以指定关于其伴侣的各种偏好，例如

  • 性别
  • 语言
  • 年龄
  • 位置（通常，距离用户居住的X英里/公里内）

    • 理想情况下，我希望用户能够指定这些偏好中的每一个是“很好拥有”还是“必须拥有”，例如“我希望与英语母语人士匹配，但我绝不能与女性相配“。

    我的目标是最大限度地提高比赛的整体平均质量。 例如，假设系统中有4个用户，A，B，C，D。这些用户可以通过3种方式进行匹配： 

    Option 1     Match Score
A-B           5
C-D           4
---
Average       4.5

Option 2     Match Score
A-C           2
B-D           3
---
Average       2.5

Option 3     Match Score
A-D           1
B-C           9
---
Average       5

    因此，在这个人为的例子中，第三个选项将被选中，因为它具有最高的整体匹配质量，尽管A和D根本不匹配。

    有没有一种算法可以帮助我：

  • 计算上面显示的“比赛分数”
  • 选择最大化平均匹配分数的配对（同时尊重每个用户的绝对约束）

    • 每个用户都不是绝对必要的匹配，所以如果选择显着降低比赛的整体质量，并留下一些没有匹配的用户，我会选择后者。

    显然，我希望计算匹配的算法尽快完成，因为系统中的用户数量可能非常大。

    最后，这个计算匹配分数和最大化整体平均值的系统只是我自己提出的一个试探。 如果有更好的方法来计算配对，请让我知道。

    更新

    我所描述的问题似乎与有着众所周知的解决方案的稳定婚姻问题类似。 但是，在这个问题中，我不需要所选对稳定。 我的目标是选择对，以便平均“匹配分数”达到最大化

    你在看什么最大匹配算法？ 我首先匆匆读过你的问题：看起来你并不一定只限于一个二部图。 这似乎更棘手。

    我相信这个问题可以表示为线性规划问题。 然后你可以使用Simplex方法来解决它。

    要在任意图中找到最大匹配，可以使用Edmond匹配算法的加权变体：

    http://en.wikipedia.org/wiki/Edmonds's_matching_algorithm#Weighted_matching

    看到那里的脚注。

    链接地址: http://www.djcxy.com/p/50459.html

    上一篇: matching algorithm

    下一篇: Inheriting behaviours for set and frozenset seem to differ