Algorithm X
Making Algorithm X Smarter About Duplicates
Algorithm X doesn't know that trying Ella's first lesson on Monday at 8 is exactly the same as trying Ella's second lesson on Monday at 8. Remember, Algorithm X is a backtracking algorithm and backtracking involves trying all possibilities, one-by-one. Whenever a dead-end is found (or a solution is found), the algorithm backtracks and tries the next option. In our example, trying Ella’s first lesson on Monday at 8 and trying Ella’s second lesson on Monday at 8 are both options.
The solution is to use AlgorithmXSolver’s built-in memory. We need Algorithm X to remember that it already tried Ella on Monday at 8. In our case, it worked, but even if it didn’t work, we want Algorithm X to make sure it never again tries Ella on Monday at 8.
I used the word “never” and that is a tiny bit misleading. The Algorithm X memory mirrors the process of recursive backtracking. Each level deeper in the recursion adds a new compartment to the memory. Each time Algorithm X backtracks, the most recent compartment is discarded. The closer you get to the root of the recursion, the smaller the size of memory. The deeper Algorithm X goes into the recursion looking for solutions, the more built-up memory it needs to check.
Enough Already, Just Show Me How to Fix It!
AlgorithmXSolver has a method called _process_row_selection(self, row). Your AlgorithmXSolver subclass needs to override this method and direct Algorithm X to “remember” the important details it needs to avoid creating duplicates. In our example problem, each time Algorithm X tries adding a row of the matrix to the solution, we want Algorithm X to remember the (name, day, hour) so that it knows not to try this same combination again at this level of the recursion. It is as simple as this:
def _process_row_selection(self, row):
_, name, instrument, day, hour, lesson_num = row
self._remember((name, day, hour))
That really is all there is to it. If Algorithm X encounters a (name, day, hour) combination that it already has in memory, it will move along to the next option. Of course, because instrument and lesson_num are not used, it is more common to see the unpacking done like this:
def _process_row_selection(self, row):
_, name, _, day, hour, _ = row
self._remember((name, day, hour))
How Important is This?
What if Ella wanted 3 lessons? What if each of the students wanted 2 lessons? The more multiplicity in the problem, the more crazy things can get. In Mrs. Knuth - Part III, all valid solutions need to be found and scored to determine the best schedule for Mrs. Knuth. The following table shows you how many distinct solutions need to be scored for each test case and how many solutions are generated by Algorithm X if multiplicity is not properly handled. I have only included the test cases where multiplicity creates a problem.
| Test Case | Distinct Solutions | Solutions Found if Duplicates Not Avoided |
|---|---|---|
| 1 - 2 Lessons Per Week for Ella | 2 | 4 |
| 2 - 3 Lessons Per Week for Ella | 2 | 12 |
| 3 - 4 Lessons Per Week for Ella | 2 | 48 |
| 4 - Morning is Better | 8 | 192 |
| 10 - Meh | 66 | 792 |
| 11 - Almost Perfect Schedule | 863 | 3,452 |
| 12 - Emma, We Need to Chat | 413 | 9,912 |
| 13 - 4-Day Weekends! | 3,425 | 41,100 |
| 14 - 3-Day Weekends! | 2,755 | 88,160 |
| 15 - Let's Rethink This Ivy | 2,601 | 124,848 |
| 16 - 5 Days of Drums…Ugh! | 1,546 | 148,416 |
| 17 - Monday at 8am…Really? | 1,862 | 178,752 |
| 18 - So Many Options | 12,561 | 200,976 |
| 19 - Here Comes the Weekend | 2,517 | 241,632 |
| 20 - Hump Day! | 8,297 | 265,504 |
As you can see, the numbers can get pretty significant. To finish Mrs. Knuth - Part III, you will need to properly account for multiplicity in your requirements and your actions. For the latter test cases, you will need to account for duplicate solutions if you hope to finish before timing out. In the next section, I will add memory to the solver and make sure only the 2 expected solutions are generated.