依赖性算法 - 找到要安装的最小程序包集

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

解决方案是安装:AEB Y.

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

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

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

UPDATE

我不想使用外部库.

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

UPDATE

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

你怎么看？

Answer 1

不幸的是,考虑到问题实际上是NP难的(但甚至不是NP完全的),没有希望找到比蛮力更好的算法.

这个问题的NP-硬度的证明是最小的顶点覆盖问题(众所周知的是NP-hard而不是NP-complete)很容易减少到它:

给出一个图表.让我们为图的每个顶点v创建包P _v.还要为图X的每个边(u,v)创建包X,"和" - 需要(P _u或P _v).查找设置包的最小安装在为了满足X.然后,如果相应的包P _v在安装集中,则v位于图的最小顶点覆盖中.

Answer 2

这是约束满足问题的一个例子。许多语言都有约束求解器，甚至有些语言可以在通用 3SAT 引擎上运行，从而可以在 GPGPU 上运行。