最適なタスクの順序

Question

あなたはn個のタスクを持っています。実行時間は以前に実行されたタスクによって異なります。タスクの一部がまだ完了していない場合は、タスクの実行時間が短くなる可能性があります。可能な限り最短時間を要する最適なタスク順序を見つけるアルゴリズムを作成します。

など。

N = 3

タスクA、B、C

T（A | B、C）=実行タスクの時間B、Cは

T（以前に行われたことを考えると|最初のタスク

T（Aとして実行タスクAの）時間= |）= 50

T（A | B）= 40

T（A | C）= 40

T（A | B、C）= 30

T（B |）= 30

T（B | A）= 25

T（B | C）= 20

T（B | A、C）= 15

T（Cは|）= 20

T（C | A）= 15

T（C | B）= 10

T（C | A、B）が10

任意のヒント= 私はDijkstraアルゴリズムについて考えていましたが、この場合は動作していないようです。

助けてください。

Answer 1

既知の開始頂点Aを使用して最小値をHamiltonian path problemとし、このタスク順序問題の入力データを作成しましょう。

T(A|) = 0 
T(i|) = inf, for any i ≠ A 
T(i|j) = edge_weight(i, j), for any i,j 

このタスク順序問題を解くことができれば、NP困難な最小ハミルトニアン経路問題を解くことができます。したがって、この問題を多項式時間で解くアルゴリズムは知られていない。

次に、この問題を比較的小さいnに解決しましょう。タスクの実行のすべてのステップで、既に完了したタスクのセットS（最初は空です）があります。次に、私たちのデータのうち最も利用可能な時間を選択して次のタスクを実行し、それをセットSに追加して次のステップに進みます。これは、自然状態Sと動的計画法に私たちをもたらします - すでに完了したタスク（これはビットマスクで実現することができる）のセット： minTime(S, i)はセットからすべてのタスクのタスクiの最小実行時間である
Sはすでに実行されています。