我需要一个有效的算法来进行最佳匹配

本文关键字：算法 最佳 有效 一个 | 更新日期: 2023-09-27 18:00:03

例如，我有10个团队，我需要匹配它们。匹配的标准是：

  1. 两支队伍只匹配一次
  2. 分数最接近的团队必须匹配（分数是团队类的属性，类型为双）

它可以最大迭代9（n-1）次，这就是我试图做的，尽我所能走得更远。在每次迭代结束时，团队的点数随机增加。我用随机数据填充了我的列表。

List<Team>  _teams = new List<Team>();
for (int i = 1; i <= 10; i++)
{
    _teams.Add(new Team("Team "+i,MyExtensions.RandomNumber(31)));
}
private static readonly Random Rand = new Random();
public static int RandomNumber(int max)
{
    return Rand.Next(max);
}

我的团队级别：

public class Team
{
    private string _name;
    private double _score;
    private List<Team> _matchedTeams;
    private Team _currentMatch;
    public Team CurrentMatch
    {
        get { return _currentMatch; }
        set { _currentMatch = value; }
    }
    public List<Team> MatchedList
    {
        get { return _matchedTeams; }
        set { _matchedTeams = value; }
    }
    public string Name
    {
        get { return _name; }
        set { _name = value; }
    }
    public double Score
    {
        get { return _score; }
        set { _score = value; }
    }
   public Team(string name, double score)
    {
        _matchedTeams = new List<Team>();
        _name = name;
        _score = score;
    }
    public override string ToString()
    {
        return _name + " - (" + _score + ")";
    }
}

这里是我的扩展方法，以获得最接近的匹配；

public static Team FindClosest(this List<Team> list, Team team)
{
    var orderedItems =
        list.Where(p => p != team && !p.MatchedList.Contains(team)).OrderBy(x => Math.Abs(x.Score - team.Score));
    return orderedItems.FirstOrDefault();
}
var nearestMatch = _teams.FindClosest(_teams.ElementAt(0));

事实上，我正在尝试制作一个桥牌游戏的固定计算器。每轮比赛必须匹配不同的球队，匹配的球队应该实力相等（或相近）。但在接下来的几轮比赛中，由于团队比赛的唯一性是第一标准，而且我们必须为人们安排比赛，我们必须改变比分（分）接近的规则。

所以它会产生类似的结果；

算法正在运行。。。

第一轮；第1组第2组；第三小组第四小组；第5组第6组。。。。。

分数由用户在第1轮结束时更新算法正在运行。。。

第二轮；第1组—第7组；第三组第八组；第4组第9组。。。。。

分数由用户在本轮结束时更新8算法正在运行。。。

第九轮；Team1-Team9；第二组——第七组；第三组第五组。。。。。

分数由用户在本轮结束时更新9算法正在运行。。。

不再匹配。

我更喜欢像回溯这样的算法，而不是暴力或随机试错。你能给我一个算法，一个解决我问题的方法吗？任何帮助都将不胜感激。

我需要一个有效的算法来进行最佳匹配

按点数对团队进行排序，然后从排序列表的开头开始抽取成对的团队。显然，第二名球队是唯一一支在积分上与第一名球队最接近的球队。如果你不把第一名和第二名配对，而是把第二名和第三名配对，那么第一名的最佳匹配将是第四名。按顺序排列的队伍只会增加积分差距。

为了说明，假设有4个团队，分别命名为A、B、C、D。各队之间的积分差为d1、d2、d3

A    B    C    D
  d1   d2   d3

如果配对是AB和CD，则差集是{d1，d3}
如果配对是BC和AD，则差集是{d2，（d1+d2+d3）}
我不知道第二套比第一套更可取。

您需要明确地说明您试图优化的目标函数。如果要找到成对的点之间差异的绝对值之和的最小值，那么我同意另一个答案，你只需按点对团队进行排序，然后从左到右一次将他们从两个团队中配对，你可以证明这是最佳配对。如果你的目标函数不同，那么它可能更难优化，甚至可能是NP难优化，这取决于你的目标功能是什么。但关键是，如果你只是说"点最接近的团队必须配对在一起"，我们也无能为力，因为有可能有一个团队的两个邻居在相反的一侧，在点上同样接近，使得两个邻居中的其他邻居相距较远，然后您只能将团队与其一个近邻配对。

您将需要这门课程。动态编程可能太慢。也许Local search或其他方法会更有效。您可以先阅读有关Local Search的视频。

相关文章：