-1

依存関係のリストがあります（またはサイクルのないDAGの方が良いです）：

入力（例）：

Item A depends on nothing
Item B depends on C, E
Item C depends on A
Item D depends on E
Item E depends on A

私が探しているのは、「アイテムの最良の*並列注文は何ですか？」です。

*最良の意味：最大同時実行レベル

結果（例）：

[A], [E, C], [D, B]

最善のアプローチは、依存関係に基づいて順序を取得するための擬似コードのようですが、これに関する基本的なアルゴリズムが欠けていると思います。

4

3 に答える 3

1

あなたが実際にあなたが望むような答えを望んでいるかどうかはわかりません。たとえば、シナリオでは、DとEがCよりも速い場合、アイテムCの前にアイテムDを実行する可能性があるため、取得したリストのリストが必ずしも全体像を示すとは限りません。

この種のワークフローを実際に実装する必要がある場合は、ワークフローを事前に予測するだけでなく、最適に実行するのは簡単です。タスクが完了するたびに、残りのすべてのタスクをスキャンして、依存関係が満たされているタスクを並行して実行します。事前に計算したい場合は、結果の構造を再考したいと思うかもしれません。

于 2011-07-20T21:35:00.657 に答える
1

これは、https：//en.wikipedia.org/wiki/Program_Evaluation_and_Review_Techniqueおよびhttps://en.wikipedia.org/wiki/Critical_path_methodによく似ています。

最大の同時実行レベルでできるだけ早く物事を成し遂げたいと仮定すると、クリティカルパスよりも長くはかからないように物事を整理したら、最善の解決策と同様に機能するものがあります。実行できる並列タスクの量に制限はありません。すべての依存関係が完了するとすぐにすべてのアクションをスケジュールするだけで、クリティカルパスを取得できます。

于 2011-07-21T04:13:58.177 に答える
0 
  GetLists(tasks[1..m], depends[1..m])
   1. topological_sort(tasks)
   2. cumulative = set()
   3. lists = queue()
   4. i = 0
   5. while |cumulative| != m do
   6.    temp = set()
   7.    while depends[i] is a subset of cumulative do
   8.       temp = temp union {tasks[i]}
   9.       i = i + 1
  10.    cumulative = cumulative union temp
  11.    lists.enqueue(temp)

そのような何かがうまくいくかもしれません。リンチピンは、確実に終了するように「トポロジカルソート」を実行していることに注意してください。また、このアルゴリズムは、有効な解を持つ入力のセットに対してのみ正しいことに注意してください。解決策がない場合、これは永久にループします。修正は簡単ですが、それを処理できます。

例：Aは何にも依存せず、BとCはAに依存し、EはAとCに依存し、DはCとBに依存します。

  Topological sort: A, B, C, D, E.
  cumulative = {}
  lists = []
  i = 0
  |cumulative| = 0 < 5 so...
     temp = {}
     depends[A] = {} is a subset of {} so
        temp = {A}
        i = 1
     depends[B] = {A} is not a subset of {}, so break
     cumulative = {A}
     lists = [{A}]
  |cumulative| = 1 < 5 so...
     temp = {}
     depends[B] = {A} is a subset of {A}, so
        temp = {B}
        i = 2
     depends[C] = {A} is a subset of {A}, so
  ...

あなたはその考えを理解します。

于 2011-07-20T21:51:58.060 に答える