小编KLi*_*KLi的帖子

我正在研究一种算法,其目标是找到一组最小的软件包来安装软件包"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

解决方案是安装:AEB Y.

这是一个描述示例的图像:

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

我已经阅读了很多关于算法的信息,比如DFS,BFS,Dijkstra等......问题是这些算法无法处理"OR"条件.

UPDATE

我不想使用外部库.

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

UPDATE

一种可能的解决方案是计算每个顶点的所有可能路径,并且对于可能路径中的每个顶点,执行相同的操作.因此,X的可能路径是(AE),(AC).现在,对于这两个可能路径中的每个元素,我们可以做同样的事情:A =(EH),(EY)/ E =(BZ),(BY)等等......最后我们可以结合可能的SET中每个顶点的路径,并选择最小长度的路径.

你怎么看？