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

我正在研究一种算法，其目标是找到安装包“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。

Here is an image to describe the example:

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

我已经阅读了很多关于 DFS、BFS、Dijkstra 等算法的文章... 问题是这些算法无法处理“OR”条件。

UPDATE

我不想使用外部库。

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

UPDATE

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

你怎么认为？

不幸的是，考虑到问题实际上是，找到一种比暴力破解更好的算法的希望不大。NP-hard http://en.wikipedia.org/wiki/NP-hard（但甚至不NP完全 http://en.wikipedia.org/wiki/NP-complete).

该问题的 NP 难度证明是最小顶点覆盖 http://en.wikipedia.org/wiki/Vertex_cover问题（众所周知是 NP 困难而非 NP 完全）很容易简化为：

Given a graph. Let's create package P_v for each vertex v of the graph. Also create package X what "and"-requires (P_u or P_v) for each edge (u, v) of the graph. Find a minimum set of packages to be installed in order to satisfy X. Then v is in the minimum vertex cover of the graph iff http://en.wikipedia.org/wiki/If_and_only_if the corresponding package P_v is in the installation set.