"Sling Blade Runner"：オーバーラップする映画タイトルのチェーンを見つけるための効率的なアルゴリズム？

"Dead Poet's Societyの生きたままもう一度死ぬ"のような重複映画のチェーンはどれくらいの長さですか？

私はそのようなパズルを解決するための最良のアプローチ/アルゴリズムが何であるか知っています。

2011-07-14 Avinash

元の質問には、ここでは言及していないより微妙な内容があります。「Mockingbirdを抹消するライセンス」のように複数単語の重複が許されています。効率性と最適性の合理的な妥協点を追求することで、常に最大のタイトルを生むとは限りません。 –

これはグラフの問題です。

まずあなたは、各頂点が映画を表し、グラフを構築します。映画が映画bが始まる単語と同じ単語の終わりであれば、エッジ（a、b）があります。

今、あなたは、グラフ内の最長パスを見つけたいです。これはNP完全な問題であるため、多項式解はありません。（wikipedia）

2011-07-14 09:04:03

これは有向グラフですが、非周期的であれば、多項式時間で解くことができます。 – Patrick

真が、それはそれは、サイクルが含まれているならば、最長チェーンが無限大であるので、プログラムは多項式時間を維持しながら、最長パスを検索する前に、ベルマン・フォードを使用してサイクルを確認することができ、明らかに –

が、この特定のケースでは、非環式ではありません。 – Patrick

答えて