dynamic-programming
加重アクティビティ選択
サーチ…
加重ジョブスケジューリングアルゴリズム
加重ジョブスケジューリングアルゴリズムは、加重アクティビティ選択アルゴリズムとも呼ばれます。
問題は、開始時間と終了時間を持つ特定のジョブと、仕事を終えたときに得た利益を考慮すると、2つのジョブを並行して実行することはできないので、最大利益はいくらですか？
これは、Greedy Algorithmを使ったActivity Selectionのように見えますが、追加されています。つまり、終了したジョブの数を最大にする代わりに、最大の利益を上げることに集中します。実行されたジョブの数はここで重要ではありません。
例を見てみましょう：
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | A | B | C | D | E | F |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (2,5) | (6,7) | (7,9) | (1,3) | (5,8) | (4,6) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 6 | 4 | 2 | 5 | 11 | 5 |
+-------------------------+---------+---------+---------+---------+---------+---------+
ジョブは、名前、開始時刻と終了時刻、および利益で示されます。数回反復した後、私たちがJob-AとJob-Eを実行するかどうかを調べると、最大利益は17になります。アルゴリズムを使用してこれをどのように見つけるか？
私たちが最初にやることは、仕上げ時間を非降順で並べ替えることです。なぜ我々はこれを行うのですか？終了する時間が短いジョブを選択すると、他のジョブを選択するのに最も時間がかかります。我々は持っています：
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
私たちは、サイズnの追加の一時配列Acc_Profを持つでしょう（ここで、 nはジョブの総数を表します）。これには、ジョブを実行する最大の累積利益が含まれます。それを取得しないでください？待って、見てください。配列の値を各ジョブの利益で初期化します。つまり、 Acc_Prof [i]はi番目の仕事を実行する利益を最初に保持します。
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
さて、 位置2をi 、 位置1をjとする 。私たちの戦略は、 jを1からi- 1まで繰り返し、各反復の後、 iがn + 1になるまで、 iを1だけ増分する。
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
ジョブ[i]と仕事[J]の重複、つまり、 仕事[J]の終了時刻が 仕事よりも大きい場合は、[I]の開始時間は、これら2つのジョブが一緒に行うことができない場合我々は確認してください。ただし、重複しない場合は、 Acc_Prof [j] + Profit [i]> Acc_Prof [i]かどうかを確認します。この場合、 Acc_Prof [i] = Acc_Prof [j] + Profit [i]を更新します。あれは：
if Job[j].finish_time <= Job[i].start_time
if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
Acc_Prof[i] = Acc_Prof[j] + Profit[i]
endif
endif
ここで、 Acc_Prof [j] + Profit [i]は、これらの2つのジョブを累積した利益を表します。私たちの例を見てみましょう：
ここでJob [j]はJob [i]と重複しています 。だからこれらを一緒にすることはできません。私たちのjは I-1に等しいので、我々は3であるI + 1にiの値をインクリメントします。そして、 j = 1とする 。
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
今、 Job [j]とJob [i]は重複しません。これらの2つのジョブを選択することによって得られる利益の総量は、 Acc_Prof [j] +利益[i] = 5 + 5 = 10であり、 Acc_Prof [i]より大きい。そこで、 Acc_Prof [i] = 10を更新します。また、 jを1ずつ増やします。
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
ここで、 Job [j]はJob [i]と重なり、 jもi-1と等しい。したがって、 iを1だけ増やし、 j = 1にします。我々が得る、
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Job [j]とJob [i]は重なり合わないので、 Acc_Prof [i]より大きい累積利益5 + 4 = 9を得る。 Acc_Prof [i] = 9を更新し、 jを1増加させる。
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 9 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
ここでもJob [j]とJob [i]は重複しません。累積利益は、 6 + 4 = 10であり、 Acc_Prof [i]よりも大きい。 Acc_Prof [i] = 10を再び更新する。 jを1ずつ増やします。
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 10 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
このプロセスを続けると、 iを使ってテーブル全体を反復した後、テーブルは次のようになります。
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 14 | 17 | 8 |
+-------------------------+---------+---------+---------+---------+---------+---------+
*ドキュメントを短くするために、いくつかの手順が省略されています。
配列Acc_Profを繰り返し処理すると、最大利益が17になることがわかります。擬似コード：
Procedure WeightedJobScheduling(Job)
sort Job according to finish time in non-decreasing order
for i -> 2 to n
for j -> 1 to i-1
if Job[j].finish_time <= Job[i].start_time
if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
Acc_Prof[i] = Acc_Prof[j] + Profit[i]
endif
endif
endfor
endfor
maxProfit = 0
for i -> 1 to n
if maxProfit < Acc_Prof[i]
maxProfit = Acc_Prof[i]
return maxProfit
Acc_Prof配列を生成する複雑さはO（n 2 ）です。配列トラバースはO（n）をとります。したがって、このアルゴリズムの全体の複雑さはO（n 2 ）である。
我々は最大の利益を得るために実行されたジョブを知りたい場合は今、私たちは逆の順序で配列を横断する必要があるとAcc_Profは maxProfitに一致した場合、我々は、 スタック内のジョブの名前を押しての利益を差し引きますその仕事はmaxProfitから。 maxProfit> 0になるか、 Acc_Prof配列の始点に達するまでこれを行います。擬似コードは次のようになります。
Procedure FindingPerformedJobs(Job, Acc_Prof, maxProfit):
S = stack()
for i -> n down to 0 and maxProfit > 0
if maxProfit is equal to Acc_Prof[i]
S.push(Job[i].name
maxProfit = maxProfit - Job[i].profit
endif
endfor
この手順の複雑さは、 O（n）です。
一つのことを覚えておきましょう。最大の利益をもたらすことができる複数のジョブスケジュールがある場合、この手順では1つのジョブスケジュールしか見つけることができません。