0

I apologize in advance for the long question, I tried to summarized it as much as I can.

I am developing an application for a martial arts league.
the first module of the application Requires to develop a complicated algorithm in order to arrange a tournament i.e. arrange n participants into a brackets in the size of x (for example 4 participants in each bracket).
The brackets must be arranged in the most optimal manner against multiple conditions.

Each participant has several parameters:

  • Belt (degree scale in martial art that can be translated into a number)
  • Weight category (for example 60-70 kg, 80-90 kg…)
  • Age category (for example 16-18, 18-25, 26-36…)
  • Academy name (the goal of that parameter is to make the maximum variance inside the brackets)
  • Is allowed to participate against other participant that has one rank of belt above him (true,false)
  • Is allowed to participate against participant that is one weight category above him (true, false)
  • Is allowed to participate against participant that is one age category above him (true,false)

The conditions:

Each "optimal" bracket has x participants that share the same belt, weight category, age category and all of them must have the maximum variance of the academy name parameter.

If there are participants that can not fit into the conditions above and they were left without a bracket or they can fit only to a bracket in the size of x-y, then the algorithm must make the best ("best" will described later) decisions and make replacements of participants inside the "perfect" brackets according to the last 3 Boolean parameters.
Also after all the replacements, variance between academy names must take place.

My question is what is the best approach to solve that problem? I will be grateful for some milestones or a reference to some math literature that discusses issues like that (I don’t expect anyone to solve it for me, just guiding).

my general point of view how to solve it:

Rank all bracket with a grade and then relate to the general grade of all brackets.

for example a "perfect" bracket of 4 participants will be ranked as Z and a weight of lack of academy name variance will be ranked as (please see yellow marked paragraph for more explanation)
–(17X<Z) so if 2 participants share the same academy name the grade will be Z-(17X<Z) and if 3 participants share the same academy name Z-2(17X<Z) and so on…

if the bracket will be or/also with lack of match between their belts, weight category or age category the grade will be lessen with another –(17X<Z).

important rule is that a house with the most "bad" grade is preferable against no bracket at all

(its 17X because maximum variance with academy condition in a bracket of 4 is 4X and maximum difference in age category is another 4X and the rest of "bad connections" between participants is 16 and I add 1 in order to produce a grade that is greater than 0 or smaller than Z).

That’s the easy part but I came to a conclusion that if I want the "Best" or the optimal grade I will need to recursively repeat an enormous and impossible number of times in order to reach for a greater general grade of all brackets and finally reach the optimal general grade.

I am not sure about it at all, maybe a different way of thinking is required.
its not so important but for General knowledge the development language is C#.
Thank you very much for your time and consideration.

Improve this question
5
  • You are almost certainly over complicating this problem. I'd advise that you make it possible to inject in different algorithms and start with a simple one. Commented Jan 22, 2017 at 23:38
  • How large is N likely to be? I ask because once you apply the selection restrictions (related to belt, weight, age), the problem might be amenable to brute force. If so, you just need a scoring function to assign a number to any given set of brackets. Then just iterate over every legal set and pick the best one. Commented Jan 23, 2017 at 0:16
  • @ FMc tnx for your comment, N is ~400 in average , i understand what you mean, but the task is to find the best general combination Commented Jan 23, 2017 at 0:20
  • A simple way to approach this would be to find all possible matches for a given contender, then once you've done this for everyone, sort the contenders in priority so that those with the least number of potential opponents get matched up first. Commented Jan 23, 2017 at 0:22
  • @ mVChr but if a contender has lets say 5 equal best matches but each match that i will choose will impact different on other matches between other contenders, how will i be able to get to the optimal general grade of all brackets? Commented Jan 23, 2017 at 0:34

2 Answers 2

Reset to default
1

Simple imperfect approach: try to assign a value to each person, to represent how troublesome they are to find a match. The most troublesome would be the lowest weight, belt, and age that cannot be matched up, which would mean they must be matched with people of the exact same belt/age/weight. Normalize each value to a 0-n scale (so age group 5-9 = 0, 10-14 = 1, etc). Assign a persons value to be the sum of these, so:

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

Next define a function to determine the difference between 2 players, which will not be the simple subtraction of the above - you don't want someone a 10 year old 4th-tier belt matched with a 28 1st tier belt. Your difference function would be something like:

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

With these, start with the Person with the lowest score, find the x-1 Person instances with the lowest difference, and that's your first bracket. Repeat until all Person are in brackets.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

thank you very much for your time for writing this down! i`m going to use that logic for the first part of the algorithm. but the primary question is how to combine the most optimal combinations of all brackets together - i mean that all brackets will have the most optimal connections between the contenders, but as long as i think about it i am not sure its possible.
0

OK, after some research i got the answer.
the answer is that there is no answer, its the P versus NP problem. one of the unsolved problems in computer science. to find the most optimal match is equal to find the most perfect absolute right move in chess game - it is not possible.

from Wikipedia:

The informal term quickly, used above, means the existence of an algorithm solving the task that runs in polynomial time, such that the time to complete the task varies as a polynomial function on the size of the input to the algorithm (as opposed to, say, exponential time). The general class of questions for which some algorithm can provide an answer in polynomial time is called "class P" or just "P". For some questions, there is no known way to find an answer quickly, but if one is provided with information showing what the answer is, it is possible to verify the answer quickly. The class of questions for which an answer can be verified in polynomial time is called NP, which stands for "nondeterministic polynomial time."

here is a nice video about this topic: P vs. NP and the Computational Complexity Zoo

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.