logo标签列表

依赖算法 - 找到安装的最小软件包集合

javapythonalgorithmmathematical-optimizationminimization
15

我正在开发一个算法，目标是找到安装软件包"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)，依此类推......最后，我们可以将每个顶点的可能路径组合在一起，并选择长度最小的路径。
你觉得呢？
需要一个蓝色依赖项和一个红色依赖项吗？ - aioobe
获取软件包所需的所有次要依赖项，您需要所有AND依赖项以及所需的任意数量的OR依赖项。我将为您举个例子。 A = B,C, D|F|G,H|L 因此，为了获得A的最少依赖项，您需要B、C，以及[D F G]中的1个和[H L]中的1个。 在OR之间进行选择的方法是选择最短的路径。 - KLi
我假设这形成了一个DAG？ - aioobe
2
注意，你的颜色代码不足够，它不能告诉你在哪里放置括号。 - user1196549
1
@KLi，我建议您将您的解决方案发布为答案，而不是放在问题中。这样就可以直接对其进行评论了。此外，我认为图片并没有帮助理解您的示例；最好将其删除。 - dened
显示剩余4条评论
10个回答
9

很遗憾，考虑到该问题实际上是NP-hard问题（但不是NP-complete问题），因此很难找到比暴力更好的算法。

证明这个问题是NP-hard的方法是通过将NP-hard的最小顶点覆盖问题（众所周知是NP-hard而不是NP-complete）简化为它：

给定一个图。我们为每个顶点v创建一个包Pv。还要创建一个要求“与”(Pu或Pv)的包X，用于每个图的边(u,v)。查找最小的一组要安装的包，以满足X。然后当且仅当相应的包Pv在安装集中时，v就是图的最小顶点覆盖iff。

即使不允许循环依赖，甚至不允许OR子句中超过两个替代项，这个证明仍然成立。 - dened
1
说最小集合（或顶点）覆盖是NP难问题但不是NP完全问题是正确的，但很可能会不必要地让人们感到困惑。所有这些离散优化问题（“找到最小...”）都可以轻松地转换为等效的决策问题（“是否存在一个...大小<= k？”），这些问题是 NP完全问题。 - j_random_hacker
“Equivalent”在这里的意思是指一个算法可以通过多项式时间转换成另一个算法。例如，将最小化问题转换为多项式数量的决策问题，只需解决k=0、1、2……的决策问题，直到返回YES答案。然后，为了恢复解决方案，从可能性集合中反复删除一个任意项（即对于顶点覆盖，删除1个顶点），并为k'=k-1解决决策问题：如果答案是否定的，则将该顶点包含在解决方案中。 - j_random_hacker
@j_random_hacker，我知道任何离散优化问题都可以通过解决一系列决策问题来解决。这在问题分析中可能很有用，但不能使解决方案的计算或验证变得更容易，即仍然无法将任何非NP完全NP难问题转换为NP完全问题。因此，你的评论对我来说仍然没有意义...还有另一个原因表明该问题既是NP难问题，也不是NP完全问题：如果突然P = NP，则可以在多项式时间内解决任何NP完全问题，但通常情况下，这并不适用于NP难问题。 - dened
我所看到的NPC问题和NPH问题之间唯一的区别是，后者不是NPC问题，但可以转换为多个NPC问题实例的多项式数量，其解决方案从未附带短证书（因为它们取决于找到至少1个NPC问题的NO解）。但是这种“无证书性”是否很重要？每当NPC问题实例恰好具有NO解时，也没有证书--换句话说，大约“一半”的NPC问题答案没有证书！ - j_random_hacker
显示剩余5条评论
2
这里的许多答案都集中在如何解决这个理论上的难题，因为它是NP-hard问题。虽然这意味着您将会经历渐进性能下降来确切地解决问题（考虑到当前的解决方案技术），但您仍然可以快速（足够快）地解决您特定的问题数据。例如，尽管该问题在理论上具有挑战性，我们仍然能够准确地解决巨大的旅行商问题实例。
在您的情况下，解决问题的一种方法是将其制定为混合整数线性规划，其中每个包装物i都有一个二进制变量x_i。您可以将要求"A requires (B or C or D) and (E or F) and (G)"转换为形式约束"x_A <= x_B + x_C + x_D; x_A <= x_E + x_F; x_A <= x_G"，并且您可以要求包装"P"在最终解决方案中包括"x_P = 1"。解决这样的模型相对简单；例如，您可以使用Python中的pulp软件包。
import pulp

deps = {"X": [("A"), ("E", "C")],
        "A": [("E"), ("H", "Y")],
        "E": [("B"), ("Z", "Y")],
        "C": [("A", "K")],
        "H": [],
        "B": [],
        "Y": [],
        "Z": [],
        "K": []}
required = ["X"]

# Variables
x = pulp.LpVariable.dicts("x", deps.keys(), lowBound=0, upBound=1, cat=pulp.LpInteger)

mod = pulp.LpProblem("Package Optimization", pulp.LpMinimize)

# Objective
mod += sum([x[k] for k in deps])

# Dependencies
for k in deps:
    for dep in deps[k]:
        mod += x[k] <= sum([x[d] for d in dep])

# Include required variables
for r in required:
    mod += x[r] == 1

# Solve
mod.solve()
for k in deps:
    print "Package", k, "used:", x[k].value()

这将输出最小的软件包集合：

Package A used: 1.0
Package C used: 0.0
Package B used: 1.0
Package E used: 1.0
Package H used: 0.0
Package Y used: 1.0
Package X used: 1.0
Package K used: 0.0
Package Z used: 0.0

对于非常大的问题实例，解决可能需要太长时间。您可以使用超时接受潜在的次优解（请参见此处），或者您可以从默认的开源求解器转向商业求解器，如gurobi或cplex，这将更快。

2

"我不明白“或者”出现问题的原因（图片无法加载）。我的理解是，我们可以使用标准的最短路径算法，如Dijkstra，并使用权重相等来找到最佳路径。以您的示例为例，从以下两个选项中选择最佳的Xr：

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

当Ar = 树A=H（及其后代）或A=Y（及其后代）时，Ar是最佳选择。

首先为每个或选项分配标准权重（因为或选项不是问题）。然后对于每个或选项，我们重复该过程，直到达到没有更多或选项为止。

然而，我们需要先定义什么是最佳选择，假设最少的依赖即最短路径是标准。按照上述逻辑，我们为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 ，在这种情况下，我们可以将这些节点在父节点或叶子节点级别上分配为零，并处理依赖关系。

请确保及时更新我们您的发现。同时，需要考虑到当出现两个或多个选项权重相同的情况时，应该如何处理。在这种情况下，可以应用额外的标准来做出选择。 - mrsachindixit
那么如果 X 依赖于 A 和 (B 或 C)，而 B 又依赖于 D 和 (F 或 G) 呢？算法如何处理才能将 B 视为 A 的依赖项，因为它对于 B 是必需的，所以也必须有 D？ - KLi
这就是为什么我包括了Ar符号。Ar = 是从树A = H（和随后的子节点）或A = Y（和随后的子节点）中选择最佳选项。现在根据您的新情况X = A和Br或Cr，我们的想法是将默认权重1分配给根，直到其完整的子树被解决和计算。之后，根节点获得新的权重而不是原始默认权重。请参见原始问题中E也具有相同的行为。X取决于A和（E或C），A取决于E和（H或Y）。... .. .. - mrsachindixit
所以我们的算法基本上是“对于每个可选节点，即option或ie，分配默认权重，然后在计算出可选节点的实际权重后修正其权重”。在分配和修订周期（或准确地说是分配标志和修订取消标志）的过程中，会有相当多的来回循环/递归。一旦我们计算出这样的权重并找到我们的最短路径，我们就可以将该路径信息用于任何现实世界的用途（例如设置构建路径或下载jar序列）。 - mrsachindixit
2

我认为图表是解决这个问题的适当结构。请注意，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。我认为以下递归算法可以解决问题：
定义：
节点u-当前节点。
S-已访问的节点集合。
children（x）-返回x的出邻居。
算法：
shortestPath u S = 
if (u has no children) {
    add u to S
    return 1
} else if (u is a dummy node) {
  (a,b) = children(u)
  if (a and b are in S) {
    return 0
  } else if (b is in S) { 
    x = shortestPath a S
    add a to S
    return x
  } else if (a in S) {
    y = shortestPath b S
    add b to S
    return y
  } else {
    x = shortestPath a S
    add a to S
    if (b in S) return x
    else {
        y = shortestPath b S
        add b to S
        return x + y
    }
  }
} else {
  min = Int.Max
  min_node = m
  for (x in children(u)){
    if (x is not in S) {
      S_1 = S
      k = shortestPath x S_1
      if (k < min) min = k, min_node = x
    } else {
      min = 1
      min_node = x
    }
  }
  return 1 + min
}

分析： 这是一个完全顺序的算法，（我认为）最多只遍历每条边一次。
1
我建议您先将图形转换为AND-OR Tree。完成后，您可以在树中搜索最佳路径（您可以选择“最佳”的含义：最短、节点中软件包的最低内存占用等）。
我的建议是，假设安装X的条件为install(X) = install(A) and (install(E) or install(C))，则将OR节点（在此情况下为E和C）分组为单个节点（例如EC），并将条件转换为install(X) = install(A) and install(EC)。
另一种选择是基于AND-OR Tree的想法，使用分组思想创建自定义AND-OR Graph。这样，您可以使用graph traversal算法的改编，在某些情况下可能更有用。
还有另一种解决方案是使用Forward Chaining。您需要按照以下步骤进行：

  1. 转换（仅在此处重新编写条件）：

    A和（E或C）=> X

    E和（H或Y）=> A

    B和（Z或Y）=> E

为：

(A and E) or (A and C) => X
(E and H) or (E and Y) => A
(B and Z) or (B and Y) => E
  1. 将X设定为目标。
  2. 插入B、H、K、Y、Z作为事实。
  3. 运行正向推理并在第一次出现X（目标）时停止。这应该是在这种情况下实现目标的最短路径（只需记住已使用的事实即可）。

如果有任何不清楚的地方，请让我知道。

1
补充Misandrist的回答：你的问题是NP-hard问题（参见dened的回答）。
编辑：这里是一个Set Cover实例（U，S）到你的“包问题”实例的直接规约：使地面集合U的每个点z成为X的AND要求。使覆盖点z的集合S成为z的OR要求。然后，包问题的解决方案给出最小的集合覆盖。
等价地，您可以询问单调布尔电路的满足赋值中有最少真变量的是哪个，详见这些lecture notes。
1
将一个问题归约到集合覆盖问题并不能证明它是NP完全问题。相反，你需要将一个NP完全问题归约到这个问题上。例如，我可以将2-SAT问题归约到3-SAT问题，但2-SAT问题很容易解决，而3-SAT问题是NP完全问题。 - Paul Hankin
@Valentas，你确定要减少吗？在这种情况下，图形很可能形成一个DAG。 - aioobe
OP确实说过“它不必处理循环”。 - alexis
我所描述的结构是有向无环图，就像问题中的图片一样。 - Valentas
1
这个简化是正确的，但这个问题本身不是NP完全问题，因为最小集覆盖问题本身不是NP完全问题。同时，最小顶点覆盖的简化给出了一个更一般的证明，因为它只需要两个OR替代项；请参见我的答案。 - dened
1
由于图形包含两种不同类型的边缘（AND 和 OR 关系），我们可以将算法分为两个部分：搜索所有必须是节点后继的节点和搜索我们必须从中选择一个单一节点的所有节点（OR）。
节点包含一个包、一个必须是该节点后继的节点列表（AND）、一个可以是该节点后继的节点列表的节点列表（OR）以及一个标记该节点在算法中访问的步骤的标志。
define node: package p , list required , listlist optional , 
             int visited[default=MAX_VALUE]

主程序将输入翻译成图形并从起始节点开始遍历。
define searchMinimumP:
    input: package start , string[] constraints
    output: list

    //generate a graph from the given constraint
    //and save the node holding start as starting point
    node r = getNode(generateGraph(constraints) , start)

    //list all required nodes
    return requiredNodes(r , 0)

requiredNodes 搜索所有需要作为节点后继的节点（通过1个或多个边与 n 以AND关系相连）。

define requiredNodes:
    input: node n , int step
    output: list

    //generate a list of all nodes that MUST be part of the solution
    list rNodes
    list todo

    add(todo , n)

    while NOT isEmpty(todo)
        node next = remove(0 , todo)
        if NOT contains(rNodes , next) AND next.visited > step
            add(rNodes , next)
            next.visited = step

    addAll(rNodes , optionalMin(rNodes , step + 1))

    for node r in rNodes
        r.visited = step

    return rNodes

optimalMin是一种搜索可选邻居的所有可能解中最短解的算法（OR）。该算法为暴力算法，将检查所有可能的邻居选择。

define optionalMin:
    input: list nodes , int step
    output: list

    //find all possible combinations for selectable packages
    listlist optSeq
    for node n in nodes
        if NOT n.visited < step
            for list opt in n.optional
                add(optSeq , opt)

    //iterate over all possible combinations of selectable packages
    //for the given list of nodes and find the shortest solution
    list shortest
    int curLen = MAX_VALUE

    //search through all possible solutions (combinations of nodes)
    for list seq in sequences(optSeq)
        list subseq

        for node n in distinct(seq)
            addAll(subseq , requiredNodes(n , step + 1))

        if length(subseq) < curLen
            //mark all nodes of the old solution as unvisited
            for node n in shortest
                n.visited = MAX_VALUE

            curLen = length(subseq)
            shortest = subseq
        else
            //mark all nodes in this possible solution as unvisited
            //since they aren't used in the final solution (not at this place)
            for node n in subseq
                n.visited = MAX_VALUE

     for node n in shorest
         n.visited = step

     return shortest

基本思路如下：从起始节点开始搜索必须是解决方案的所有节点（只通过遍历AND关系可以到达的节点）。现在对于所有这些节点，算法搜索可选节点（OR）所需的最少节点组合。
注意：到目前为止，这个算法并没有比暴力搜索更好。我找到更好的方法后会进行更新。
但是如果一个节点被两个其他节点共享作为依赖项，会发生什么呢？以我的例子为例：A 有两个依赖项，Y 和 H。最短路径是 A E B Y 而不是 A E B H，因为 A 和 E 共享相同的依赖项。实际上，如果你选择 H 而不是 Y，你的最短路径是 A E B H Y。如何处理这种情况？希望你能理解我。 - KLi
你说得对，我的解决方案只适用于树。我会修复它。 - user4668606
1
我的代码在这里。 场景： 表示约束条件。
X : A&(E|C)
A : E&(Y|N)
E : B&(Z|Y)
C : A|K

准备两个变量 target 和 result。 将节点 X 添加到 target 中。
target = X, result=[]

将单个节点 X 添加到结果中。 将节点 X 替换为其在目标中的依赖项。
target = A&(E|C), result=[X]

将单个节点A添加到结果中。 用其依赖项替换目标中的节点A。
target = E&(Y|N)&(E|C), result=[X, A]

单个节点 E 必须为真。 因此 (E|C) 总是为真。 从目标中移除它。

target = E&(Y|N), result=[X, A]

将单个节点 E 添加到结果中。 在目标中，用其依赖项替换节点 E。
target = B&(Z|Y)&(Y|N), result=[X, A, E]

将单个节点 B 添加到结果中。 用其依赖项替换目标中的节点 B。
target = (Z|Y)&(Y|N), result=[X, A, E, B]

现在已经没有单个节点了。 然后扩展目标表达式。

target = Z&Y|Z&N|Y&Y|Y&N, result=[X, A, E, B]

将 Y&Y 替换为 Y。

target = Z&Y|Z&N|Y|Y&N, result=[X, A, E, B]

选择具有最小节点数量的术语。 将术语中的所有节点添加到目标中。
target = , result=[X, A, E, B, Y]
这个算法看起来是正确的，但效率非常低。瓶颈在于扩展步骤。即使输入不是很大（例如100个不同的(A|B)），程序也不仅会永远运行（这是预期的），而且还会消耗yottabytes的内存用于扩展target。 - dened
@dened 是的，你说得对。问题是找到节点数量最少的术语。我认为有捷径算法。至少，有算法可以在多项式时间内找到更好（可能不是最好）的解决方案。这只是我的直觉。 - user4910279
0

解决这个问题的另一种（有趣的）方法是使用遗传算法。

遗传算法非常强大，但您必须使用许多参数并找到更好的参数。

遗传步骤如下：

a. 创建：随机生成一些个体，即第一代（例如：100个）

b. 变异：对其中低百分比的个体进行变异（例如：0.5%）

c. 评估：对所有个体进行评估（也称为适应度）

d. 繁殖：选择（使用适应度）一对个体并创建子代（例如：2个子代）

e. 选择：选择父母和子代以创建新一代（例如：每代保留100个个体）

f. 循环：返回步骤“a”并重复整个过程一定次数（例如：400代）

g. 挑选：从最后一代中选择一个适应度最高的个体。该个体将成为您的解决方案。

以下是您需要决定的内容：

  1. 找到一个个体的基因编码

您必须将问题的可能解决方案（称为个体）表示为基因编码。

在您的情况下，它可以是一组字母，表示遵守约束OR和NOT的节点。

例如：

[ A E B Y ]，[ A C K H ]，[A E Z B Y] ...

  1. 找到评估个体的方法

要知道个体是否是一个好的解决方案，您必须对其进行评估，以便与其他个体进行比较。

在您的情况下，这可能非常容易：个体评分=节点数-个体节点数

例如：

[ A E B Y ] = 8-4 = 4

[ A E Z B Y] = 8-5 = 3

[ A E B Y ]比[ A E Z B Y ]具有更好的评分

  1. 选择

由于个体的评分，我们可以选择它们的一对进行繁殖。

例如，通过使用遗传算法轮盘赌选择。

  1. 繁殖

从一对个体中创建一些（例如2个）子代（其他个体）。

例如：

从第一个节点中取出一个节点并将其与第二个节点交换。

进行一些调整以适应“或、和”约束。

[ A E B Y ]，[ A C K H ] => [ A C E H B Y ]，[ A E C K B Y ]

注意：这不是繁殖的好方法，因为子代比父代更差。也许我们可以交换一段节点。

  1. 突变

您只需更改所选个体的基因代码即可。

例如：

  • 删除节点

  • 进行一些调整以满足“或”和“与”的约束条件。

正如您所看到的，它并不难实现，但需要做出很多选择来针对特定问题进行设计，并控制不同的参数（变异百分比、速率系统、繁殖系统、个体数量、世代数量等）。

0

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

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接