Alc*_*ott 5 c++ algorithm parallel-processing graph
问题描述:
还有n tasks,在这些任务one might be dependent on the others,这意味着如果A依赖于B,那么B必须之前被完成完成.
1.找到一种尽快完成这些任务的方法？
2. take parallelism into account如何设计程序来完成这些任务？
题:
显然,第一个问题的答案是拓扑 - 排序这些任务,然后按顺序完成它们.
但如果考虑到并行性,如何完成这项工作？
我的回答是,首先对这些任务进行拓扑排序,然后选择那些独立的任务并首先完成它们,然后在其余的任务中挑选并完成那些独立的任务......
我对吗？
拓扑排序算法可能会给出各种不同的结果顺序，因此您不能只采用前几个元素并假设它们是独立的。
我建议不要按拓扑排序，而是按传入依赖边的数量对任务进行排序。因此，例如，如果您的图表有 A --> B、A --> C、B --> C、D-->C，您会将其排序为 A[0]、D[0]、B[1] , C[3] 其中 [i] 是传入边的数量。
通过拓扑排序，你还可以得到A、B、D、C。在这种情况下，要发现可以并行执行 A 和 D 并不容易。
请注意，任务完全处理后，您必须更新剩余的任务，特别是依赖于已完成任务的任务。但是，如果进入任务的依赖项数量限制为相对较小的数量（例如数百个），您可以轻松依赖基数/桶排序之类的东西，并保持排序结构在恒定时间内更新。
通过这种方法，一旦单个并行任务完成，您还可以轻松启动新任务。只需更新依赖项计数，然后启动现在具有 0 个传入依赖项的所有任务。
请注意，此方法假设您有足够的处理能力来同时处理没有依赖关系的所有任务。如果您的资源有限并且关心处理时间方面的最佳解决方案，那么您将不得不投入更多的精力，因为问题变得 NP 困难（正如阿恩已经提到的）。
因此，回答您最初的问题：是的，您基本上是对的，但是，您缺乏解释如何有效地确定这些独立任务（请参阅上面的示例）。