algorithm - 资源加载算法

Question

这是我在工作中遇到的经典CS题:我有一个我需要加载的资源列表。每个资源都有一个加载所需的约束列表，加载时满足其他资源可能需要的其他约束。例如:资源 X 具有 a、b、c 作为约束，因此它只能在满足 a、b 和 c 时加载。加载时，X 满足资源 Y 所需的约束 n 和 m，资源 Y 也需要约束 p 才能加载，因此当另一个资源加载并满足 p 约束时，Y 将加载，进而满足其他约束。所有资源所需的约束列表是最终的，这意味着每个资源可能需要多个约束，并且多个资源可能需要每个约束。此外，一个资源需要空约束才能加载，因此必须是第一个加载的。

好的，经过这么长的解释，我的问题是:当我事先知道每个资源需要哪些约束但不知道(提前)加载后资源满足哪些约束时，我如何才能找到资源的最佳加载顺序？

希望我的解释足够清楚...谢谢!

Answer 1

编辑

简单的解决方案:

创建一个有 n 个顶点(资源)和 m 个顶点(约束)的二分图。 - O(n + m)

将约束保存在一些查找表数据结构(即哈希表)中。

每当资源需要约束时，在资源顶点和约束顶点之间绘制边。

创建一个L 资源列表，最初是空的。 (这是加载资源的顺序)。

创建一组 R 资源，最初是空的。 (这是当前可以添加的资源集)。 - O(1)

将具有 0 个约束的资源添加到 R。 - O(1)

当 R 不为空时:

{

从 R 获取一些资源 r - O(1)

将 r 添加到 L - O(1)

设 S 是资源 r 在加载时满足的所有约束的集合。

S 中的 Foreach constraint c 查找约束顶点并删除所有指向该顶点的链接。如果在链接的另一边，没有更多链接(意味着资源顶点现在可以加载)，将该顶点添加到 R。 - O(|S|)

总运行时间:O(n * |S|)，其中 |S|是单个资源满足的最大约束数。