由网友(巷尾の樱花)分享简介：我工作的一种算法，目标是找到一组最小的包来安装包的X。I'm working on an algorithm which goal is to find a minimum set of packages to install package "X".我会解释用一个例子来更好地：I'll explain bett...

我工作的一种算法，目标是找到一组最小的包来安装包的X。

I'm working on an algorithm which goal is to find a minimum set of packages to install package "X".

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

I'll explain better with an example:

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形

The solution is to install: A E B Y.

下面是一个图像描述的例子：

Here is an image to describe the example:

有一个算法来解决问题，而无需使用暴力的方法？

Is there an algorithm to solve the problem without using a brute-force approach?

我已经读了很多关于算法，如DFS，BFS，Dijkstra算法，等等。 问题是，这些算法不能处理的或条件。

I've already read a lot about algorithms such as DFS, BFS, Dijkstra, etc... The problem is that these algorithms are unable to handle the "OR" condition.

更新

我不想使用外部库。

该算法没有处理循环依赖。

The algorithm doesn't have to handle circular dependencies.

更新

一种可能的解决办法是，计算每个顶点的所有可能的路径，并在可能的路径中的每个顶点，做同样的。 因此，对于X中的可能的路径是（A E），（A C）。现在，这两个可能的路径每个元素，我们可以这样做：A =（EH），（EY）/ E =（BZ），（BY），等等... 最后，我们可以将每个顶点的可能路径的设置，并选择一个与最小长度。

One possible solution could be to calculate all the possible paths of each vertex and, for each vertex in the possible path, doing the same. So, the possible path for X would be (A E),(A C). Now, for each element in those two possible paths we can do the same: A = (E H),(E Y) / E = (B Z),(B Y), and so on... At the end we can combine the possible paths of each vertex in a SET and choose the one with minimum length.

你怎么看？

推荐答案

不幸的是，几乎没有希望找到一个算法比蛮力要好得多，考虑到这个问题实际上是的