java - 依赖算法 - 找到要安装的最小包集

Question

我正在研究一种算法，其目标是找到安装包“X”的最小包集。

我会用一个例子更好地解释:

X depends on A and (E or C)
A depends on E and (H or Y)
E depends on B and (Z or Y)
C depends on (A or K)
H depends on nothing
Y depends on nothing
Z depends on nothing
K depends on nothing

解决方案是安装:A E B Y。

这是描述示例的图像:

是否有一种算法可以在不使用蛮力方法的情况下解决问题？

我已经阅读了很多关于 DFS、BFS、Dijkstra 等算法的资料...问题在于这些算法无法处理“或”条件。

更新

我不想使用外部库。

该算法不必处理循环依赖。

更新

一种可能的解决方案是计算每个顶点的所有可能路径，并针对可能路径中的每个顶点执行相同的操作。因此，X 的可能路径是 (A E),(A C)。现在，对于这两个可能路径中的每个元素，我们可以执行相同的操作:A = (E H),(E Y)/E = (B Z),(B Y)，依此类推...最后，我们可以将每个顶点的可能路径组合成一个 SET，并选择长度最小的路径。

你怎么看？

Answer 1

不幸的是，考虑到问题实际上是NP-hard，几乎没有希望找到比蛮力好得多的算法。 (但甚至不是 NP-complete )。

这个问题的 NP 难证明是最小值 vertex cover问题(众所周知是 NP-hard 而不是 NP-complete)很容易归结为它:

给定一个图表。让我们为图的每个顶点 v 创建包 P_v。同时创建包 X 什么“和”- 需要(P_u 或 P_v) 对于图的每条边(u, v)。找到要安装的最小软件包集以满足 X。那么v在图的最小顶点覆盖iff中相应的包 P_v 在安装集中。