依赖算法寻找ins的最小包集

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的可能路径是（ae），（ac）。现在，对于这两个可能路径中的每个元素，我们可以做同样的事情：A=（eh），（ey）/E=（bz），（by），等等。。。 最后，我们可以将每个顶点的可能路径组合在一个集合中，并选择长度最小的一个。在

你觉得怎么样？在

Answer 1

我实际上认为图表是解决这个问题的合适结构。请注意 A和（E或C）<；==>；（A和E）或（A和C）。因此，我们可以用以下一组有向边来表示X=A和（E或C）：

A <- K1
E <- K1
A <- K2
C <- K2
K1 <- X
K2 <- X

本质上，我们只是分解语句的逻辑，并使用“虚拟”节点来表示and。在

假设我们以这种方式分解所有的逻辑语句（and的伪Ki节点，否则是有向边）。然后，我们可以将输入表示为DAG并递归遍历DAG。我认为下面的递归算法可以解决这个问题：

定义：
Node u-当前节点。
S-访问的节点集。
children（x）-返回x的外邻居

算法：

^{pr2}$

分析： 这是一个完全连续的算法（我认为）最多遍历每条边一次。在

Answer 2

不幸的是，考虑到问题实际上是NP-hard（但甚至不是NP-complete），找到一个比暴力强得多的算法几乎没有希望。在

这个问题的NP硬度的一个证明是最小vertex cover问题（众所周知是NP难而不是NP完全的）很容易被简化为：

给出一个图表。让我们为图的每个顶点创建包P_v。同时为图的每个边（u，v）创建“and”所需的包（P_u或P_v）。找到要安装的最小软件包集，以满足X的要求。那么v在图的最小顶点覆盖中iff相应的包P_v在安装集中。在

Answer 3

“我不知道”或“的问题”（图像没有为我加载）。 这是我的理由。假设我们使用标准的最短路径算法，比如Dijkstras，然后使用相等的权重来找到最佳路径。 以你为例 从以下2个选项中选择最佳Xr

Xr= X+Ar+Er
Xr= X+Ar+Cr

其中Ar=是树A=H（和后续子项）或A=Y（以及后续子项）中的最佳选项

其思想是首先为每个or选项指定标准权重（因为and选项不是问题）。 稍后，对于每个or选项，我们对其子节点重复该过程，直到没有更多的or选项。在

然而，我们需要首先定义，什么是最佳选择，假设最小的依赖数量，即最短路径是标准。 根据上面的逻辑，我们给X指定了1的权重

^{pr2}$

希望这件事能澄清。 此外，我们还需要处理循环依赖关系X=>；Y=>；Z=>；X，在这里，我们可以在父节点或叶节点级别指定这些节点为零，并处理依赖关系。”