每个包都有一个版本列表,每个版本包含以下信息：
>可比ID
>依赖关系(包的列表和每个包一组可接受的版本)
>冲突(软件包列表和每个软件包一组版本,与此版本一起导致问题)
>提供(一个软件包列表,并为每个软件包提供此软件包还提供/包含的一组版本)
对于当前状态,我有一个软件包列表及其当前版本.
我现在想给出可用包的列表和当前状态,可以在包列表中获取每个包的版本,将给定的约束考虑在内(依赖,冲突的包,其他包提供的包)和获取每个这些软件包的版本列表.循环依赖是可能的.
如果无法达到有效状态,则可能会更改现有软件包的版本,尽管这只能在必要时进行.如果不可能达到有效的状态,因为应该有可能的原因(告诉用户“如果你删除X,它可以工作”).
如果可能,也可以将包“锁定”到特定版本,在这种情况下,包的版本可能不会更改.
我想要完成的工作非常类似于现有的软件包管理器已经做的工作,不同之处在于,不一定需要使用最新版本的软件包(大多数软件包管理员都认为这样做).
到目前为止,我唯一的想法是构建所有可能状态的结构,所有可能的版本的软件包,然后删除无效状态.我真的希望这不是唯一的解决方案,因为它感觉非常“强力”.保持在几秒钟〜约500个可用的软件包,每个〜100个版本,和〜150个安装的软件包将是一个好的目标(尽管越快越好).
我不相信这是一个特定于语言的问题,但为了更好地说明这一点,这里有一点伪代码：
struct Version
integer id
list<Package,set<integer>> dependencies
list<Package,set<integer>> conflicts
list<Package,set<integer>> provides
struct Package
string id
list<Version> versions
struct State
map<Package,Version> packages
map<Package,boolean> isVersionLocked
State resolve(State initialState,list<Package> availablePackages,list<Package> newPackages)
{
// do stuff here
}
(如果你应该有实际的代码或知道一个现在的实现的东西,这样做(任何语言,C首选)随时提及它)
一些坏消息：这个问题是NP-hard,所以除非P = NP,否则没有可以有效地解决所有实例的算法.我将通过显示如何在多项式时间内将NP-hard问题3SAT的任何给定实例转换为适合于输入您的问题的依赖图结构,以及如何将任何依赖关系解析算法的输出转换为问题回到原来的3SAT问题的解决方案,再次在多项式时间.逻辑基本上是如果有一些算法可以解决多项式时间的依赖解决问题,那么它也可以解决多项式时间中的任何3SAT实例 – 而且由于计算机科学家花了几十年的时间寻找这样的算法而没有找到一个,这被认为是不可能的.
我将在以下假设,在任何时候最多可以安装任何软件包的一个版本. (这相当于假设在同一个包的每对不同版本之间存在隐式冲突.)
首先,我们来制定一个稍微放松的依赖关系解决问题的版本,其中我们假设没有安装软件包.我们想要的是一种算法,给定一个“目标”包,或者返回一组要安装的软件包版本,(a)包含一些版本的目标软件包,(b)满足每个软件包的所有依赖和冲突属性设置或返回“IMPOSSIBLE”,如果没有一套软件包版本可以工作.显然,如果这个问题是NP-hard,那么我们还会指定一组不被改变的已经安装的软件包版本的更一般的问题.
构建实例
假设我们给出了一个包含n个子句和k个变量的3SAT实例.我们将为每个变量创建2个包：一个对应于文字x_k,一个对应于文字！x_k. x_k包将与！x_k包冲突,反之亦然,确保包管理器中最多只能安装这两个包中的一个.所有这些“文字”包将只有一个版本,没有依赖关系.
对于每个子句,我们还将创建一个“父”包,还有一个“子”包的7个版本.每个父包将依赖于其子包的7个版本中的任何一个.子包对应于从一组3个项目中选择至少一个项目的方法,并且每个项目将具有对相应文字包的3个依赖关系.例如,一个子句(p,！q,r)将具有对文字包(p,q,！r),(！p,q) r),(p,r),r)和(p,r)：前3个版本完全满足文字p,！q或r;接下来的3个版本正好满足2个;最后满足3.
最后,我们创建一个“根”包,其中包含所有n个父条款包作为其依赖关系.这将是我们要求软件包管理器安装的软件包.
如果我们在这套2k 8n 1软件包版本上运行软件包管理器,请求它安装根软件包,它将返回“IMPOSSIBLE”或要安装的软件包版本列表.在前一种情况下,3SAT问题不能令人满意.在后一种情况下,我们可以轻松提取变量的值：如果安装了x_k的文字包,请将x_k设置为true;如果安装了文字包！x_k,请将x_k设置为false. (请注意,不会有任何没有安装文字包的变量：每个变量至少显示一个子句,每个子句都会生成7个子包版本,其中至少有一个必须被安装,并且将强制安装一个的这个变量的两个文字.)
甚至有些限制也很困难
这种结构没有使用预先安装的软件包或“提供”信息,所以即使不允许这个问题,这个问题仍然是NP-hard.更有趣的是,假设我们假设一次最多可以安装一个版本的任何软件包,即使我们不允许冲突,问题仍然是NP-难度：而不是使文字x_k和！x_k分离包含冲突子句在每个方向,我们只是让他们两个不同版本的同一个包！
