彼の著書The Algorithm Design Manualで、Steven S. Skiena は次の問題を提起しています。
ここで、次のスケジューリングの問題を考えてみましょう。あなたが非常に需要の高い俳優で、開発中のn 個の異なる映画プロジェクトに出演するオファーが提示されたと想像してください。各オファーには、撮影の初日と最終日が指定されています。この仕事を引き受けるには、この全期間を通じて対応できることを約束する必要があります。したがって、間隔が重複する 2 つのジョブを同時に受け入れることはできません。
あなたのようなアーティストにとって、仕事を受け入れる基準は明確です。できるだけ多くのお金を稼ぎたいということです。これらの各映画は映画ごとに同じ料金を支払うため、これは、2 つの映画が互いに競合しないように、可能な限り最大の一連の仕事 (間隔) を求めることを意味します。
たとえば、図 1.5 [上] の利用可能なプロジェクトを考えてみましょう。「離散」数学、プログラミング チャレンジ、計算された賭け、および Halting State または Steiner's Tree のいずれかの 1 つです。
あなた (またはエージェント) は、次のアルゴリズム スケジューリングの問題を解決する必要があります。
問題:映画のスケジュールの問題
入力:ライン上のn間隔のセットI。
出力: Iから選択できる相互に重複しない区間の最大のサブセットは?
これは TSP のインスタンス (おそらく簡略化されたもの) ですか?