Movie Chain Runner

This wiki documents the progression our group over the course of the semester on this project

Problem Definition

Movie Chain Runner: Given an input list of movies (6561 in size), determine the longest chain of movies. A chain is defined to be a sequence of movies titles where consecutive movie titles overlap. Two movies are said to overlap if there exists an integer x > 0 such that the last x words of the first movie are exactly equal to the first x words of the second movie.

CS Translation

If we model each movie as a vertex and define two movies to share a directed edge if one movie overlaps with the other, then this problem is simply to find the longest path in our generated graph. The longest path problem is NP hard and is difficult to approximate, so smart heuristics are needed to get good results.