依赖关系解析算法

我必须解决依赖关系问题。这种情况如下：依赖关系解析算法

我的包与它们对应的依赖关系列表如下：

pkg1: [] 
pkg2: [pkg1] 
pkg3: [pkg1, pkg2] 
pkg4: [pkg1 | pkg 3] 
pkg5: [pkg1 | pkg2 | pkg3]

注意“|”两个或多个依赖关系之间相当于“或”

我的目标是为每个软件包计算安装它所需的最小依赖关系集。

因此，例如：

minimum_set(pkg)

应该返回

pkg1, pkg2

来源

2015-05-28 geek4079

同样的问题已经在这里打开：http://stackoverflow.com/questions/30429786/dependency-algorithm-find-the-shortest-number-of-packages-to-install#30429786 – Paul

看不到任何改善在迄今为止的答案 – geek4079

仍然毫无意义地打开了完全相同的主题的另一个问题。 – Paul

根据这些包的规模（即假设有没有大量的排列会导致堆栈溢出），你可以做一个递归查看每个分支来获取每个依赖关系的最小值。

伪代码[蟒蛇上下的款式】：

def minimum_set(pkg): 
    pkg_dependencies = pkg.dependencies() 

    if len(pkg_dependencies) < 1: 
     #Package has no dependencies 
     return dict(pkg, 0) 

    min_dps = [] 
    for dp in pkg_dependencies: 
     if isOR(dp): 
      min_dp = min(minimum_set(dp).value()).key() 
      min_dps.extend(min_dp) 

    return min_dps

像你要求为一个特定的软件包需要依赖包的最低金额这应该希望返回一个列表。

来源

2015-05-28 13:11:08 Jakob

所以你是暴力强制的权利？ – geek4079

以及如果没有或依赖项呢？我认为你没有考虑这种情况。我对吗？ – geek4079

如果两个软件包共享一个依赖关系 – Paul

某种蛮力是不可避免的，因为即使这个问题的一个非常有限的形式是NP完全的。

具体而言，即使除了其中一个软件包的依赖项列表仅包含由OR连接的术语，我们也可以平均减少NP完成Hitting Set问题。假设我们有一个Hitting Set的实例，其中X包含元素x_1，...，x_n的地面集合，S是X的k个子集S_1，...，S_k的集合，其中每个i的S_i \ subseteq X，我们想要命中：然后对于地面集合X中的每个元素x_i，生成一个没有依赖关系的包x_i，并且对于每个集合S_j \ subseteq X，生成一个包含s_j的包，其依赖包中的所有包x_k \ ，由OR操作员连接。最后再做一个“根”包r，它有依赖关系的k包s_1，...，s_k，通过AND连接。现在，找到minimum_set(r)将找到原始HS问题的最小尺寸击中集 - 这些是与为安装而选择的软件包x_i的子集对应的地面集元素。所以如果你能以多项式的时间以某种方式实现minimum_set()，你已经在多项式时间内解决了Hitting Set和其他NP-complete问题。

来源

2015-05-28 14:24:04

，那么这将不起作用您能否向我提供一个用蛮力构思的python中的常规实现？ – geek4079

没有抱歉，因为我不知道Python。但是如果你有n个软件包，你可以简单地生成所有可能的2^n软件包组合，测试每个软件包是否满足所有需求，并保持最小的那个。优化是先尝试生成所有的1包装组合，然后是所有的2包装组合，等等，停在第一个工作。可能更好的优化是使用分支和绑定。您可以节省一些时间，通过始终强制所需软件包所需的所有软件包仅具有AND相关性。 –

依赖关系解析算法

回答

相关问题