アルゴリズム設計マニュアルの第 2 版を読んでいます。ShortestJobFirst アルゴリズムと OptimalScheduling アルゴリズムの違いを説明してください。与えられたアルゴリズムは次のとおりです。
ShortestJobFirst(I) {
- 一方 (I = ∅) は
- I から最短の仕事 j を受け入れる.
- j と、j と交差する間隔を I から削除します。
}
最適スケジューリング(I)
- 一方 (I = ∅) は
- 完了日が最も早い I からジョブ j を受け入れます。
- j と、j と交差する間隔を I から削除します。
「私 たちのスケジューリングの問題とロボット工学の問題との違いは、映画のスケジューリングを正確かつ効率的に解決するアルゴリズムがあることです。最初に終了するジョブについて考えてみてください。つまり、一番左のポイントが一番右のポイントを含む間隔 x です。すべての間隔の間で. この役割は、図 1.5 の「離散」数学によって果たされます. 他のジョブは x より前に開始されている可能性がありますが、これらのすべては少なくとも部分的に互いに重複する必要があるため、グループから多くても 1 つを選択できます.これらのジョブのうち最初に終了するのは x であるため、オーバーラップするジョブのいずれかが、その右側の他の機会をブロックする可能性があります。明らかに、x を選択することによって決して失うことはありません。これは、次の正確で効率的なアルゴリズムを示唆しています----"
例は、アルゴリズム設計マニュアル(この PDF の 10/11 ページ)にあります。