依赖算法 - 找到的最小集合包安装 [英] Dependency Algorithm - find a minimum set of packages to install
问题描述
我工作的一种算法，目标是找到一组最小的包来安装包的X。
I'm working on an algorithm which goal is to find a minimum set of packages to install package "X".
我会解释用一个例子来更好地：
I'll explain better with an example:
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形
The solution is to install: A E B Y.
下面是一个图像描述的例子：
Here is an image to describe the example:
有一个算法来解决问题，而无需使用暴力的方法？
Is there an algorithm to solve the problem without using a brute-force approach?
我已经读了很多关于算法，如DFS，BFS，Dijkstra算法，等等。 问题是，这些算法不能处理的或条件。
I've already read a lot about algorithms such as DFS, BFS, Dijkstra, etc... The problem is that these algorithms are unable to handle the "OR" condition.
更新
我不想使用外部库。
该算法没有处理循环依赖。
The algorithm doesn't have to handle circular dependencies.
更新
一种可能的解决办法是，计算每个顶点的所有可能的路径，并在可能的路径中的每个顶点，做同样的。 因此，对于X中的可能的路径是（A E），（A C）。现在，这两个可能的路径每个元素，我们可以这样做：A =（EH），（EY）/ E =（BZ），（BY），等等... 最后，我们可以将每个顶点的可能路径的设置，并选择一个与最小长度。
One possible solution could be to calculate all the possible paths of each vertex and, for each vertex in the possible path, doing the same. So, the possible path for X would be (A E),(A C). Now, for each element in those two possible paths we can do the same: A = (E H),(E Y) / E = (B Z),(B Y), and so on... At the end we can combine the possible paths of each vertex in a SET and choose the one with minimum length.
你怎么看？
推荐答案
不幸的是，几乎没有希望找到一个算法比蛮力要好得多，考虑到这个问题实际上是的NP-hard （但也不 NP完全问题）。
Unfortunately, there is little hope to find an algorithm which is much better than brute-force, considering that the problem is actually NP-hard (but not even NP-complete).
这个问题的NP-硬度的证据是，最低顶点覆盖问题（众所周知的是NP-硬，而不是NP完全性）是很容易还原到它：
A proof of NP-hardness of this problem is that the minimum vertex cover problem (well known to be NP-hard and not NP-complete) is easily reducible to it:
给定的曲线图。让我们创建包的 P <子> v 的为图中的每个顶点的 v 的。还可以创建包的 X 的是什么和 - 需要（ P <子> U 或 P <子> v ）为图的每个边缘的（U，V）的。找到最小设置软件包被安装在为了满足的 X 的。随后的 v 的是，在图的最小顶点覆盖当且仅当相应的包的点<子> v 的是，在安装集。
Given a graph. Let's create package Pv for each vertex v of the graph. Also create package X what "and"-requires (Pu or Pv) for each edge (u, v) of the graph. Find a minimum set of packages to be installed in order to satisfy X. Then v is in the minimum vertex cover of the graph iff the corresponding package Pv is in the installation set.
这篇关于依赖算法 - 找到的最小集合包安装的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
