１引言随着开源思想的流行，越来越多的开发者参与开源软件世界，ＦＯＳＳ〔ＦｒｅｅａｎｄＯｐｅｎＳｏｕｒｃｅＳｏｆｔｗａｒｅ〕发行版操作系统中的开源软件仓库的规模日益壮大。同时，开源软件仓库中的软件包之间的依靠和冲突关系越来越冗杂，这导致了一个严峻的问题：当使用系统原生的包管理器安装或升级软件包时，可能会遇到软件包安装或升级后系统变得不稳定或丢失一些功能的状况，甚至可能由于计算上的高冗杂度，包管理器无法找到能够满足系统中软件包之间的依靠和冲突的安装方案，而直接提示软件包安装或升级失败。这些状况会影响正常的生产工作，因此有效地解决软件安装或升级问题格外必要。如图１所示，自２００１年以来，Ｄｅｂｉａｎ软件仓库中的软件包数量持续增长，截至２０１９年１２月，软件包数量已超过５９０００［１］。然而，由于软件包之间的联系，软件包的管理在计算上是特殊冗杂的。例如，一个软件包可能依靠某些软件包或者与某些软件包冲突，软件包管理工具必需要能够维护好一个描述软件包安装状况的配置方案，该方案须满足每个软件包的依靠项，并且不会造成软件包之间的冲突，搜寻这样的配置方案就是软件升级问题。然而，配置方案仅仅满足软件包之间 ...