«Sling Blade Runner»: эффективный алгоритм поиска цепочки перекрывающихся названий фильмов?

Question

Эта проблема связана с архивированной загадкой от ITA Software , так как загадка устарела, я думаю, это нормально обсуждать.

Как долго цепочка перекрывающихся названий фильмовКак, например, «Живи и дай умереть еще одному дню общества мертвых поэтов», вы можете найти?

Я хотел бы знать, каков наилучший подход / алгоритм для решения такой головоломки.

Answer 1

Это проблема графика.

Сначала вы строите график, где каждая вершина представляет фильм. Существует край (a, b), если фильм заканчивается тем же словом, что и фильм, с которого начинается фильм.

Теперь вы хотите найти самый длинный путь на графике. Это NP-полная задача, поэтому она не имеет полиномиального решения. ( википедии )