SimpleMin (aka GameMin, DayMin)

This algorithm was by far the easiest to come up with, and code. The smallest distance in the table is chosen. The represents the game with the least "cost." All choices involving the chosen home or road team were blocked out. In the table this meant marking out the entire row and column of each team.. draw 1 horizontal and 1 verticle line that intersect on the chosen road team (rows), then 2 more lines on the home team(columns).

Next pick the smallest of the remaining entries in the array. This is the second game. Again mark out all games involving this road and home team. Then simply repeat the process until all game are chosen.

This algorithm insures that the lowest cost game is picked, however in some cases, it can force very poor choices later on, if the best choices are all in the same rows and/or columns. It is, however, VERY quick and simple. (Essentially O(x^3))

Max-Min

This algorithm attacks the problems of the SimpleMin method head on. instead of looking for the smallest cost, you find the largest cost. You want to avoid this cost, so look in the row and column this entry is in and find the smallest. Essentially you are making a "trade" of the current biggest cost for the smallest related cost. Avoiding the longest distance by choosing the short distance either team is involved in.

As before, once you have selected a game, you mark out all of the games involving either team, using the 4 lines and 2 X's method. Then repeat the selection for the next Max-Min pair.

This algorithm that the worst distance is not chosen, however, in some cases it can still force very poor choices, again if the best choices all tend to be in the same row and column. It is also a quick algorithm, also O(x^3) but due to the 3 step nature (instead of 2 step in SimpleMin) the Max-Min algorithm is alsightly slower.

Perfect

This algorithm solves the problem to find the perect solution. It does this through brute force and checking every possible solution. It essentially works its way through the table, trying each home team for a road team. After making that temporary selection it finds a home team for the next road team. Every selection is followed by the same 4 line mark out of the associated games.

I coded this program using recursive techniques to make the code cleaner. Normally recursive programming robs the system of resources and slows it down, but since almost all of the parameter passing is pointers, not full arrays, this time should be minimal.

This algorithm is extremely slow. Of course it will return the perfect choice of games, but at O(x^4) you begin to wonder if it is worth the time expense.

I have included data from one of the test runs I made. This data is taken after 24797 sets of data were used. The data was realistic (random points on a 700x700 grid were chosen and their distances were calculated to build the 65000 tables). The following table is a summary of how close each of the above methods came to the perfect solution. The numbers in the table are the total distances required for the 10 teams to pair up for 5 games.

The Average line shows that MaxMin came closer to the perfect solution on average. MaxMin was within 6.93% of the perfect solution, while SimpleMin was off by 13.44%. The Worst Case Scenerio appears to show MinMax with better results. Further investigation showed that MaxMin was too high by almost 100% while SimpleMin was off by 95.7% These two errors were on different data sets, showing that on some sets, SimpleMin was better than MaxMin.

Counting the number of Perfect selections made by the two algorithms, we see that MaxMin found the perfect choice 46% of the tie, but SimpleMin found it only about 30% of the time. After running several test sets, these percentages remain fairly constant.

The time analysis of the 65000 set test run shows clearly the differences between the 3 methods. Several jobs were run sequentially in a batch job (so there was no competition for resources among the programs). The 65000 tables were created, the 3 different programs were run on all of the sets, and then the file (milage.dat) was deleted because it was several hundred megabytes in size.

From looking at the table you can see that the creation of the 6500 data sets took 13 seconds, the SimpleMin algorithm took 13 seconds to run, as expected. The MaxMin algorithm took 14 seconds. This is slightly larger than SimpleMin, though not much, as expected. Both are O(x^3) but MaxMin has an extra loop inside to make a slight difference.

Perfect however took a stunning 3 days, 16 hours, 43 minutes, and 20 seconds. This is 88 hours, 43 minutes or 24569 times longer than either of the two other methods.

First reaction is that you should NEVER use the Perfect algorithm as it takes entirely too long. However this is actually only about 5 seconds for each data set. The worst case Scenerio for 1 season of hockey would be 180 days. This would take 15 minutes if 1 set of 10 games happened every day of the season. This worst case would never actually happen, due to league days off, and days with only 1 game, so the choice of opponent would be obvious.