php - 前の終了日に基づいてタスクの開始日を更新する

Question

次のアルゴリズムを念頭に置いてプログラムを開発したいと思います。

タスク A とタスク B は、タスク C の前身です。これらにはすべて、開始日と終了日があります。タスク B の終了日が遅れると、タスク C の開始日も遅れます。これは最も単純なケースです。ただし、ほとんどの場合、グラフはますます複雑になります。

再帰的にチェックするだけでなく、各タスクの開始日と終了日を更新するには、どのアルゴリズムを使用すればよいですか?

ありがとう

Answer 1

http://en.wikipedia.org/wiki/Longest_path#Acyclic_graphs_and_critical_pathsで説明されている問題を解決する必要があります。

プログラムの開始時に、先行タスクが後続タスクの前に来る順序を確立するためにトポロジカル ソートを実行し、タスク タイミングの初期セットを計算します。タスクの終了日が遅れている場合は、トポロジカル ソートの順序を使用して、そのタスクの後続タスクを確認し、次にそれらの後続タスクの後続タスクを確認します。遅れる可能性がある未チェックの後続タスクのリストを保持し、このリストから元の順序で最も早いものをチェックし、タスクの終了日を変更する必要があることが判明した場合は、新しい後続タスクを挿入することができます。このリストが空になった場合、グラフ内のすべてのノードをチェックせずに終了できます。これは、スリップの影響を受けるノードがないことを示しています。