1

この質問は、プロセスの割り当てに関する別の質問に触発されています。これは、そこで議論されている問題をひねり、強化したものです。

n 個のプロセスがあり、可能な限り少数のプロセッサに割り当てる必要があります。各プロセスにはスケジュールされた開始時刻と終了時刻があり、1 から始まる時間単位で定義します。プロセスは、時間単位の連続したシーケンスで実行されます。プロセッサは、任意の数の非重複プロセスを実行するようにスケジュールできます。

明らかな貪欲なアルゴリズムは次のとおりです。

各ステップで、残りのプロセスの重複しない最大のセットを次のプロセッサにスケジュールします。

重複しない最大のセットはどのように選択されますか? アルゴリズムを非決定論的のままにします。これにより、分析が容易になり、2 つのサブ質問に分割しやすくなります。

基本的に、前の質問は、アルゴリズムが不運な場合の動作に関するものです。このアルゴリズムが最適でない割り当てを生成する可能性がある (つまり、必要以上のプロセッサが必要になる)最小のnは何ですか? 答えはn =4 であることがわかります。2 つのプロセッサで十分な場合もありますが、貪欲なアルゴリズムでは 3 つのプロセッサが必要になる場合があります (運が良ければ、2 つのステップで実行されます)。

この質問は、非決定論が常に幸運である場合に何が起こるかに関するものです。

このアルゴリズムが準最適であることが保証されている最小のnは? つまり、貪欲なアルゴリズムが必要以上のプロセスを使用しなければならない一連のプロセスを見つけることができる最小のnは?

Stack Overflowでは、自分の質問を尋ねて回答することを積極的に奨励しているので、ここでそうします。私の部分的な回答を改善できるかどうか教えてください。

4

1 に答える 1

0

答えはn =7だと思います。n = 7ではうまくいかないことを実証しようと思います。しかし、これは上限を与えるだけです。n =6で問題が発生する可能性はありますか? そうは思いませんが、よくわかりません。

上界

スケジュールする次のプロセスがあるとします。

  • [1](つまり、プロセスは時間単位 1 で実行されます)
  • [2]
  • [4]
  • [5]
  • [1,2,3](つまり、プロセスは時間単位 1 から 3 の間に実行されます)
  • [2,3,4]
  • [3,4,5]

最適な割り当てには、3 つのプロセッサが必要なようです。

  1. [1]、[2,3,4]
  2. [2]、[3,4,5]
  3. [1,2,3]、[4]、[5]

しかし、貪欲なアルゴリズムは次の結果を生成します。

  1. [1]、[2]、[4]、[5]
  2. [1,2,3]
  3. [2,3,4]
  4. [3,4,5]

ここでの重要なポイントは、最初のステップで 4 つをスケジュールし (貪欲であるため)、その後は 3 つのペアワイズ オーバーラップ プロセスが残ることです。

下限

n =6で問題が発生する可能性はありますか? そうは思いませんが、確かではありません。関連するケースは、最適なソリューションに 3 つのプロセッサが必要で、それぞれが 2 つのプロセスを実行しているように思えます。貪欲なアルゴリズムが最初のプロセッサで 3 つをスケジュールし、その後 3 つの重複するプロセスが残り、合計で 4 つのプロセッサが必要になるケースを見つけることができますか?

最適なソリューションを得るには、3 つのペアが必要です。ただし、最初のステップで 3 つのプロセスをスケジュールすると、2 つのステップで完了することができないように、これらのプロセスを構築する必要があります。明らかに、これら 3 つのプロセスにペアの 1 つを含めることはできません。さもなければ、ソリューションはペアの場合と同じように続行できますが、そのうちの 1 つをシングルトンとして残します。したがって、各ペアから 1 つを取得する必要があります。

プロセスが連続していない時間ブロックを必要とする場合、次のようにできます。

  • [1]
  • [2]
  • [3]
  • [1,2]
  • [2,3]
  • [1,3](停止しては再開するため、これは許可されません!)

最適なソリューションは、各シングルトンをその補数とペアにします。貪欲なアルゴリズムは、最初のステップですべてのシングルトンをまとめて処理し、残りのペアワイズ オーバーラップ プロセスにはさらに 3 つのプロセッサが必要になります。しかし、上記の最後のプロセスは連続した時間ブロックに対して実行されないため、ごまかしてしまいました。

[3,4]と同じプロセッサで実行できるため、最後のものを に変更することはできません[1,2]。実際、交点が空でない限り、3 つのペアごとに重なり合う隣接ブロックを持つことはできません。したがって、7 つのプロセスの場合と同様[1,2,3]に、[2,3,4]、 、 のような結果になります。[3,4,5]問題は、一緒にスケジュールできるプロセスをさらに 3 つ追加することは不可能であり、トリプルの 1 つを使用してシングルトンの 2 つをスケジュールする可能性を考慮せずに、3 プロセッサの最適なソリューションを許可することは不可能に思われることです。試してみると

  • [1]
  • [2]
  • [4]
  • [1,2,3]
  • [2,3,4]
  • [3,4,5]

次に、貪欲なアルゴリズムは[1]最初のステップで, [2],をスケジュールし、最適なソリューションに導きます (非決定性が次善のソリューションにつながることが保証さ[3,4,5]れているケースを探しています)。

試してみると

  • [2]
  • [3]
  • [4]
  • [1,2,3]
  • [2,3,4]
  • [3,4,5]

プロセスのうち 4 つで時間単位 3 が必要になるため、3 つのプロセッサでは最適解は得られません。

この熟考のすべては、貪欲なアルゴリズムがn =6 の場合に最適であり、したがってn =7の上限が厳密であることを示唆しています。しかし、それは証明にはほど遠い。n =6に対して常に最適であることをどのように証明できますか?

于 2014-10-18T20:16:17.233 に答える