我需要一种有效的算法来实现最佳匹配 [英] I need an efficient algorithm for best matching

问题描述

例如，我有10个团队，我需要匹配它们。



标准是;



1 - 两支球队只匹配一次。

2 - 必须匹配最近分的球队。



可能是最多迭代9（n-1）次，这是我尝试做的，尽我所能。



每次迭代结束时，团队积分随机增加。



我用随机数据填充了我的清单。

I have, for instance, 10 teams and I need to match them.

Criteria are;

1 - Two teams are matched only one time.
2 - Teams with closest points must be matched.

It could be iterated 9 (n-1) times max and this is what I try to do, go further as I can.

At the end of each iteration, points of teams increase randomly.

I populated my list with random data.

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);
}

我的团队课程;

My team class;

public class Team
{
    private string _name;
    private double _point;
    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 Point
    {
        get { return _point; }
        set { _point = value; }
    }

   public Team(string name, double point)
    {
        _matchedTeams = new List<Team>();
        _name = name;
        _point = point;
    }

    public override string ToString()
    {
        return _name + " - (" + _point + ")";
    }
}

这是我的扩展方法得到最接近的匹配;

And here's my extension method to get closest match;

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.Point - team.Point));
    return orderedItems.FirstOrDefault();
}

  var nearestMatch = _teams.FindClosest(_teams.ElementAt(0));

我更喜欢像回溯而不是蛮力或随机试用的算法 - 和 - 错误。



你能给我一个算法，一个解决我问题的方法吗？



非常感谢任何帮助。

谢谢。

I prefer an algorithm like backtracking instead of brute force or random trial-and-error.

Can you suggest me an algorithm, a method to solve my problem?

Any help would be much appreciated.
Thank you.

推荐答案

为什么不按点值对列表进行排序然后再取2一次。

通过排序，最接近的值将是相邻的。

Why not just sort the list by Point value and then take them 2 at a time.
By sorting, the closest values will be adjacent.

据我所知，你将有9个！有10个队伍的比赛，每个队伍迟早会和其他队员比赛。

我注意到你在算法中使用

As far as I understood, you are going to have 9! games with 10 teams as sooner or later each team will play a match with others.
I noticed that in your algorithm you are using

for (int i = 1; i <= 10; i++)
 {
   _teams.Add(new Team("Team "+i,MyExtensions.RandomNumber(31)));
 }

如果空间复杂性不成问题，目前我建议如下：

0.创建一个HashSet数组（size = n-1，在你的情况下为9）。在这些哈希集中，我们将保留team_index与其匹配的team_number。 （注意：当第4组和第5组之间存在匹配时，我们执行arrayHashset [4] .add（5）并且我们从不执行arrayHashset [HighNumber] .add（SmallerNumber），因为此条目将在arrayHashset [SmallNumber]中提供给我们] .add（HighNumber）。

1.此阵列的索引是团队编号，1 - 9（团队10不会有任何哈希集作为其最高编号，因此团队10的所有匹配将是保存在其他散列集中。

2.在上述循环中对列表进行排序。

3.取这个列表的前两个并进行匹配。无论哪个数字更小。做ArrayHashSet [SmallerNumber] .add（greaterNumber）。

4.随机增加点数，对其进行排序。取两个以上，找到那些团队的最小值。如果数字较大，请查看最小数字的哈希集是否存在。如果没有匹配，则选择排序数组中的团队，然后再重复。



您可以做的两个小优化：

1.一旦参加比赛，就从名单中删除一支队伍获得所有其他团队，这将减少剩余匹配的排序复杂性。您可以维护一个数组，以保持由team_number索引的匹配计数器。

2.当您随机增加点数时，如果可能，首先增加最新排序的第0个索引的团队点数列表，然后是第一个索引，然后是第二个等等......通过这样做，您有机会检查增加点后该团队是否有资格进行索引更改（因此您可以避免不必要的排序动作）。 />


现在，我无法想到任何其他解决方案。希望你能找到一些更好的解决方案。

If space complexity is not a problem, currently, I suggest following:
0. Create an array of HashSet (size = n-1, in your case 9). In these hashsets, we will keep the team_number with which the team_index has player a match. (Note: When there is a match between team 4 and 5, we do arrayHashset[4].add(5) and we never do arrayHashset[HighNumber].add(SmallerNumber) because this entry will be avilable to us in arrayHashset[SmallNumber].add(HighNumber).
1. The index of this array is the team number, 1 - 9 (Team 10 wont have any hashset as its the highest number thus all matches of team 10 will be saved in other hashsets).
2. Sort the list during the above loop.
3. Take first two of this list and make a match. Whichever number is smaller. Do ArrayHashSet[SmallerNumber].add(greaterNumber).
4. Increase the points randomly, sort it. Take above two, find min of those team. Look in the hashset of min number if the higher number is present or not. If not make the match else choose the team in sorted array which is just below and repeat again.

Two minor optimization you can do is:
1. Eliminate a team from the list once it has played matches against all other teams this would reduce the sorting complexity a bit for remaining matches. You can maintain an array to keep the match counter indexed by the team_number.
2. When you increase the points randomly, if possible, first increase points of the team which is at 0th index in the latest sorted list, then 1st index, then 2nd and so on... By doing so, you have the opportunity to check if after increasing points this team is eligible for index change or not (thus you can avoid unnecessary moves for sorting).

Right now, I am unable to think of any other solution. Hope you would post me back some better solution once found.

这篇关于我需要一种有效的算法来实现最佳匹配的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！