打印安装软件包所需的最小包集。

Question

我必须创建一个数据结构来表示包之间的依赖关系。

我想我可以简单地使用一个图表，但问题是有些包可以依赖于其中的一个“可选”包，我们必须选择这些最优的包中哪个更方便安装(基本上，从这些可选的选项中，我们需要安装最好的)。

例如，假设我有以下情况：

1. package1：
2. package2: package1
3. package3: package1，package2
4. package4: package1 = package3
5. package5: package1，package2 = package3

这种情况意味着：

1. 包1没有依赖项。
2. 第2包依赖于包1(我们需要安装包1)。
3. 第3包取决于第1和第2包(我们需要同时安装两者)
4. 第4包取决于软件包1或3(我们可以安装1或3，但我们需要选择最佳选择，这意味着使软件包4依赖于较少软件包的选择)
5. 软件包5取决于软件包1，也取决于软件包2或3(同样，我们需要选择最佳选择)。

现在，问题很明显是我们何时可以在不同的包之间进行选择。

我们如何选择他们？

例如，为什么第4包应该依赖于包1而不是3？

我们可以试着检查包1和包3取决于哪个包，但是如果我们有10000种选择，但是我们只需要1种最佳选择呢？它将需要成千上万的循环和东西太多复杂。也许有件简单的事，但我不知道是什么。

这种试图选择哪个更好的安装似乎会导致递归算法，这已经让我震惊了。

Answer 1

您可以使用两种类型的节点创建有向图：

• package节点，其子节点使用一个和逻辑组合。
• OR节点，其子节点使用OR逻辑组合

从节点开始的所有弧都表示它的依赖项。

对于您的示例，这将创建以下图形：

​

如果必须计算包的最小依赖项集，可以使用深度优先搜索算法访问图形：

• 访问package节点时，可以将其子节点的依赖项数之和。
• 访问OR节点时，要考虑其子节点的最小依赖项数。

示例代码

下面是如何在python中实现这一功能的示例(我使用python的语法与伪代码差不多；您应该能够获得它的要点)：

#!/usr/bin/env python3

class Package:
    # Constructor
    def __init__(self, name, dependencies):
        self.name = name
        self.dependencies = set(dependencies)
    # Needed to print the package
    def __str__(self):
        return self.name
    # This method returns the optimal set of dependencies for this package
    def getOptimalDependencies(self):
        optimalDependencies = set()
        for dependency in self.dependencies:
            optimalDependencies = optimalDependencies.union(dependency.getOptimalDependencies())
        optimalDependencies.add(self)
        return optimalDependencies

class Or:
    # Constructor
    def __init__(self, dependencies):
        self.dependencies = set(dependencies)
    # This method returns the optimal set of dependencies
    # of the packages combined with this 'OR'
    def getOptimalDependencies(self):
        optimalDependencies = set()
        for dependency in self.dependencies:
            alternativeDependencies = dependency.getOptimalDependencies()
            if len(optimalDependencies) == 0 or len(alternativeDependencies) < len(optimalDependencies):
                optimalDependencies = alternativeDependencies
        return optimalDependencies

然后，可以创建示例的包，如下所示：

package1 = Package("package1", [])
package2 = Package("package2", [package1])
package3 = Package("package3", [package1, package2])
package4 = Package("package4", [Or([package1, package3])])
package5 = Package("package5", [package1, Or([package2, package3])])

要获得package5的最佳依赖项列表，可以调用package5.getOptimalDependencies()。

如果我们用：

print(','.join(map(str, package5.getOptimalDependencies())))

我们得到：

package2,package1,package5

如果您有依赖周期，则必须为此插入一些控件。

Answer 2

我们可以把它建模为一个伪布尔优化问题。

假设有k包。定义k个布尔变量x_i，其中x_i是真的当且仅当最后的选择是安装package_i。因此，目标是最小化x_i的总和，其中1 <= i <= k。如果每个包需要不同的“成本”来安装(例如，包大小)，则可以将x_i的加权和最小化。

要对约束"package5: package1，package2 \ package3“建模，我们可以发现”已安装了package5“意味着”已安装了package1“。如果伪布尔优化器支持合合范式表示的约束，那么它可以编写为

(!x_5 + x_1) 

如果只允许线性不等式，那么它就是

(1 - x_5) + x_1 >= 1

另一半，"package5已安装“意味着"package2和/或package3已安装”，可以编写为

(!x_5 + x_2 + x_3)

或

(1 - x_5) + x_2 + x_3 >= 1

最后，必须断言所需的包。

x_k

或

x_k = 1

现在我们已经将问题建模为伪布尔优化问题，您可以调用任何可用的求解器并解决它。您可以参考伪布尔竞争为最先进的解决方案。