Thought Clutter

Since I posted my "Sling Blade Runner" answer, I've been in discussion with Benjamin Meyer about the puzzle, my solution, and other general topics. During this discussion, he shared his solution with me, and as a collaboration, we found a set of movie titles that is 326 movies long. The original list of 318 movies was generated by my program, but was expanded to 326 by his. (My algorithm is good at finding long lists, his algorithm is good at optimizing long lists.)

I've decided that since I've shared much of the algorithm with him (not my code), that I would publish my answer here as well.

The algorithm I used is called Ant Colony Optimization (ACO). ACO is a randomized algorithm where virtual ants walk a graph of the problem space developing answers. Once a number of ants have walked the problem, they lay a "pheromone" on the "paths" that were particularly good. The algorithm then has more virtual ants walk the problem space, but this time they "slightly favor" paths that have pheromone on them. Once the second round of ants finishes, all pheromones on the problem are faded, and the best ants from the second run lay their pheromone. A simple state machine describes ACO's operation:

1. Allow N ants to randomly walk your problem. The probability that an ant will take a certain turn in the path is a combination of an apriori probability and a weighting probability from the pheromones laid on the particular edge.
2. Fade all pheromones on the edges.
3. For the M best ants, allow them to lay the pheromones.
4. Goto (1) until you think you've got a good path.

ACO is devilishly simple in its implementation, develops surprisingly good answers to this problem, and is highly threadable. But, ACO does come with its own set of drawbacks -- in particular there are a number of "magically tuned" parameters that affect its operation:

1. What is a good number of M and N?
2. What is appropriate amount of pheromone for "good" ants to lay?
3. What is a good way to combine the apriori and pheromone probabilities?
4. What is a good apriori probability?
5. And finally, How much do you fade all the different pheromones between steps?

Unfortunately, ACO doesn't give us much help with many of the above problems. That didn't phase me, I just charged ahead and threw some ants at my problem.

In my source directory, you will find a copy of my source code that implements Ant Colony Optimization of Sling Blade Runner. There are a number of different comments I'd like to make:

1. Unlike Ben's clever solution, I didn't bother to thread it. It would be easy enough to do, I didn't bother.
2. There are a number of optimizations in this code. Namely, I stripped out ACO's call to the pow function, and made them lookup tables, and rejiggered things to minimize copying things to and from the stack.
3. There are a number of optimizations I didn't make. Namely, I call new (through push_back/push_front) in my main loop. That's just plain silly, but I didn't bother to strip it out.
4. My magical parameters were tuned by trial and error. Most of them are #defines, and if you read the ACO literature, you can understand my nomenclature.
5. The code isn't the most readable. I coded it quickly, and have tweaked it. It's only a personal project, so don't hate me because it ain't beautiful.

Having implemented ACO, I can say that it's an interesting idea, and one I'm happy to have in my arsenal. It codes up quickly, and I have already used it to solve a couple of other problems of varying complexity.

Edited to add:
You'll need the movies data to run my program.