依赖关系算法 - 查找要安装的最小包集

algorithm python java mathematical-optimization minimization

2022-09-03 14:04:31

我正在研究一种算法，其目标是找到一组最小的软件包来安装软件包“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等算法的信息。问题是这些算法无法处理“OR”条件。

更新

我不想使用外部库。

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

更新

一种可能的解决方案是计算每个顶点的所有可能路径，并针对可能路径中的每个顶点执行相同的操作。因此，X的可能路径是（A E），（A C）。现在，对于这两个可能路径中的每个元素，我们可以做同样的事情：A = （E H），（E Y） / E = （B Z），（B Y），依此类推...最后，我们可以将每个顶点的可能路径组合到SET中，并选择具有最小长度的路径。

你觉得怎么样？

答案 1

不幸的是，找到一种比蛮力好得多的算法的希望渺茫，考虑到这个问题实际上是NP-hard（但甚至不是NP-complete）。

这个问题的NP硬度的证明是最小顶点覆盖问题（众所周知是NP-hard而不是NP-complete）很容易被简化为它：

给定一个图表。让我们为图形的每个顶点 v 创建包 P v。还要为图形的每个边（_u，_v）创建“and”-require（P u或P v）的包X。找到要安装的最小包集以满足 X。则 v 位于图的最小顶点覆盖中，而相应的包 P_v 位于安装集中。

答案 2

“我没有遇到”or“的问题（图像没有为我加载）。这是我的推理。假设我们采用像Dijkstras这样的标准最短路线算法，然后使用等值权重来找到最佳路径。以您的示例从以下2个选项中选择最佳Xr

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

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

这个想法是首先为每个或选项分配标准权重（因为和选项不是问题）。稍后，对于每个或选项，我们用其子节点重复该过程，直到我们不再达到或选项。

但是，我们需要首先定义，最佳选择的含义，假设最小数量的依赖关系即最短路径是标准。根据上述逻辑，我们为 X 分配权重 1。从那里开始

X=1
X=A and E or C hence X=A1+E1 and X=A1+C1
A= H or Y, assuming H and Y are  leaf node hence A get final weight as 1
hence , X=1+E1 and X=1+C1

Now for E and C
E1=B1+Z1 and B1+Y1 . C1=A1 and C=K1.
Assuming B1,Z1,Y1,A1and K1 are leaf node 

E1=1+1 and 1+1 . C1=1 and C1=1
ie E=2 and C=1

Hence
X=1+2 and X=1+1 hence please choose X=>C as the best route

希望这能清除它。此外，我们需要注意周期依赖关系 X=>Y=>Z=>X，在这里我们可以在父节点或叶节点级别分配这样的节点为零，并处理依赖性。