寻找多组对象最优匹配的算法

Question

我对这个长期的问题事先表示歉意，我试着尽可能地对它进行总结。

我正在开发一个武术联盟的应用程序。

应用程序的第一个模块需要开发一个复杂的算法来安排比赛，即将n参与者安排到x大小的括号中(例如，每个括号中有4个参与者)。

在多种情况下，括号必须以最优的方式排列。

每个参与者都有几个参数：

• 腰带(武术的学位等级，可以翻译成一个数字)
• 体重类别(例如60-70公斤，80-90公斤…)
• 年龄类别(例如16-18、18-25、26-36…)
• 学院名称(该参数的目标是使括号内的最大方差)
• 被允许参与对抗在他上面有一个等级的其他参与者(真，假)
• 被允许参加比赛的参与者是他以上的一个体重类别(真，假)
• 被允许参加反对一个年龄级别以上的参与者(真，假)

条件：

每个“最佳”托架都有相同的腰带、体重类别、年龄类别的x参与者，他们都必须拥有学院名称参数的最大方差。

如果有参与者不能适应上述条件，而他们没有括号，或者只能适应x-y大小的括号，则算法必须根据最后3个布尔参数做出最佳(“最佳”将于后描述)的决策，并在“完美”括号内替换参与者。

而且，在所有的替换之后，学院名称之间的差异必须发生。

，我的问题是，解决这个问题的最好方法是什么？，我会感激一些里程碑，或者引用一些数学文献来讨论这样的问题(我不希望有人为我解决这个问题，只是指点)。

我的一般观点是如何解决这个问题：

用一个等级对所有括号进行排序，然后与所有括号的一般等级相关联。

例如，一个由4名参与者组成的“完美”等级将被列为Z，而缺乏学院名称差异的权重将被排列为(请参阅黄色标记段落以获得更多解释)。

–(17X<Z)，因此，如果2名参与者使用相同的学院名称，则成绩将为Z-(17X<Z)，如果3名参与者共享相同的学院名称，Z-2(17X<Z)等，则为…

如果支架在腰带、体重类别或年龄类别之间缺乏匹配，则该等级将随着另一个–(17X<Z)的增加而减少。

重要的规则是，最“差”等级的房子比根本没有支架的房子更好。

(它的17倍，因为与学术条件的最大差异为4倍，年龄类别的最大差异是另外4倍，其余参与者之间的“坏联系”为16，我加1，以产生大于0或小于Z的分数)。

这是容易的部分，但我得出的结论是，如果我想要“最佳”或最优的分数，我将需要递归重复大量和不可能的次数，以达到一个更大的一般等级的所有括号，并最终达到最佳的一般等级。

我一点也不确定，也许需要一种不同的思维方式。

它并不那么重要，但是对于常识来说，开发语言是C#。

非常感谢您的时间和考虑。

Answer 1

好吧，经过调查，我得到了答案。

答案是没有答案，这是P对NP问题。计算机科学中尚未解决的问题之一。在国际象棋比赛中，找到最理想的比赛就等于找到最完美的绝对正确的动作--这是不可能的。

维基百科：

上面使用的非正式术语“快速”是指解决以多项式时间运行的任务的算法的存在，因此完成任务的时间随算法输入的大小(例如，指数时间)而变化为多项式函数。一些算法可以在多项式时间内给出答案的一般问题被称为“P类”或“P类”。对于一些问题，没有已知的快速找到答案的方法，但是如果一个人得到了显示答案的信息，那么就有可能快速验证答案。一类可以用多项式时间验证答案的问题称为NP，它代表“非确定性多项式时间”。

下面是一个关于这个主题的好视频：P对NP与计算复杂性动物园

Answer 2

简单的不完美方法:尝试给每个人分配一个值，以表示他们在寻找匹配时有多麻烦。最麻烦的是体重、腰带和年龄最低而无法匹配，这意味着它们必须与相同腰带/年龄/体重的人匹配。将每个值标准化为0-n标度(所以年龄组5-9 = 0，10-14 = 1，等等).指定一个人的价值作为这些值的之和，因此：

Age 15      +2
Belt Yellow +1
Weight 110  +3
Yes         +.5
Yes         +.5
No          +0
Score=7.0

接下来，定义一个函数来确定两个玩家之间的差异，这将不是简单的减去上面的-你不想有人一个10岁的第4层带匹配一个28第1层带。您的差异函数将类似于：

int diff(Person p1, Person p2)
{
  var diff = 0.0f;
  bool ageDiffAcceptable = p1.Age - p2.Age == 1 && p2.CanPlayerOlder || p2.Age - p1.Age == 1 && p2.CanPlayerOlder;
  var ageDiff = (p1.Age - p2.Age) * (ageDiffAcceptable ? 1 : 1.5);
  diff += pow(agDiff, 2) // Someone that is 2 age groups away will increase at a higher rate; adjust this 2 based on the importance of this particular field

  // Same for weight and belt

  // Account for player score - we want to prefer similarly scored players as a tiebreaker
  diff += abs(p1.Score - p2.Score) / Constants.MaxScore;
  return diff;
}

使用这些方法，从得分最低的Person开始，找到差异最小的x-1 Person实例，这是您的第一个括号。重复，直到所有Person都放在括号中。