软件自动升级问题，求助各位！

[sunway1988]

问题是这样的

公司有很多产品需要实现在线自动更新（可以定时检查发起更新，也可能是用户自己发起），大致的解决方案如下：

升级客户端首先获取到产品的配置信息列表，里面包含一些可能的升级路径，比如可以从 1.1-1.2 升级到 1.5 ，并且需要包含一些依赖的其他组件或者数据库啊什么的内容包（这些当然也会当成是一个产品来升级），所以就有如下问题：

1. 一个产品 A 如果升级的话，可能一次无法完成升级，需要从中间版本过渡，如 1.1 升级到 1.8 ，需要先升级到 1.5 ，然后再从 1.5 升级到 1.8 ，如何在配置的路径中找到最优的升级路径。配置的路径就是一些可实现升级的路径，如： from 1.1-1.2 to 1.5 ， from 1.3 to 1.4 ， from 1.4-1.7 to 1.8 ，等等。
   这个有什么好的算法解决呢？

2. 一个产品 A 如果需要升级到如上所述的 1.8 的话，首先需要升级到 1.5 ，然后再升级到 1.8 ，而且在每一次升级过程中还需要升级依赖的其他产品，如 A 从 1.1 升级到 1.5 ，需要将 B 升级到 1.9 ，将 C 升级到 2.1 ，这又会导致在升级 B 和 C 的时候，又需要安装他们的依赖。
   那么用什么数据结构和算法来解决这个问题呢？

感谢各位的回答，谢谢！

[domty]

1. 第一个 把每生一次的权设为 1 的话，就是当前版本到最高版本的最短路径把？
2. 给个我的理解，可以参考 android 的 google play 服务。设置一个专门的提供服务的软件 d ，所有的软件升级统一依赖这个服务软件 d ，这样就可以把每个软件对其他多个软件的依赖转为单对软件 d 的依赖。在升级当前软件后发现缺少依赖的服务的话直接提示用户升级软件 d 到最新版本就好。

[sunway1988]

@domty 感谢回答：

1. 通过将升级路径构造“图”数据结构可以找到最短路径，这样解决很好。
2. 产品是相互独立的，每个产品都有特定的依赖，怎么实现统一依赖软件 d 呢？
比如一套系统由 A ， B ， C ， D 组成，如果 A 升级需要依赖 BCD 的版本，另一套系统由 E ， F ， G ， H 组成， E 升级需要依赖 FGH 的版本。

[domty]

@sunway1988
第二个我只是提供一种参考方式，因为你提的需求恰好让我想到了 google play 服务框架的做法。
首先要确定每套系统到底依赖的是什么东西。
*比如一套系统由 A ， B ， C ， D 组成，如果 A 升级需要依赖 BCD 的版本，另一套系统由 E ， F ， G ， H 组成， E 升级需要依赖 FGH 的版本。*
你可以认为唯一被依赖软件（假设为 d)是一个被所有软件所共享的工具箱，当其他软件需要使用一些不是自己的动能的时候，就去工具箱找。所以当每个软件中存在除本身外还被其他软件所需要的功能的时候，这个功能就应该是可被所有软件共享的，就应该被放到工具箱(软件 d)里。

[wencan]

如果是 linux ，可以考虑自建仓库

[sunway1988]

@domty 我受到启发可以通过树的建立和后续遍历（假设以二叉树为例）来解决：

首先根据升级路径建树：
假设需要升级 A ，则 A 为根节点， A 依赖于 B ， C ， D ，则 BCD 依次为 A 的子节点，构成一棵树；
同样升级 B ， C ， D 时，也有相应的依赖，假设是存在没有任何依赖的软件（主要通过配置文件约束实现），那么必然上述过程会结束，也就是存在叶子节点。

然后先子节点后根节点 /或者按层从下到上的顺序遍历上面建的树：
那么必然是被依赖的先升级，然后再升级有依赖的（但是此时依赖已经完成升级了，尽管大胆升级）。

由此，就可以将存在依赖关系转化为升级顺序，这样在升级时，就可以只关注自己，而不用关心依赖了，因为依赖已经完成升级了。

以上方案，如何？

[sunway1988]

@domty 或者采用栈的方式来实现也可以，就是我上面讲的：
建树是入栈，按照顺序入栈就行了
按层从下到上的顺序遍历上面建的树 [出栈]

[domty]

@sunway1988
可以啊，就是先生成一个依赖树，然后子节点先于父节点升级(后续遍历)
但是要注意一点，设置依赖关系的时候不要设错，否则你的树可能就变成一个环了。最后可能造成类似死锁的东西。

比如 a 依赖 b ， b 依赖 c ，如果设置错了 c 依赖 a ，你的这个升级循环就找不到子节点了

[xylophone21]

移植一个软件包管理系统吧，看看 dpkg ， pip 神马的是怎么实现的。

[sunway1988]

@domty 是啊，不能存在互相依赖，这个可以通过配置文件约束实现。而且一般现实情况也是不会存在这样互相依赖情形的。

[sunway1988]

@xylophone21 这是不是太复杂了一点，短时间能否实现？

[sunway1988]

@xylophone21 这个在哪可以找到参考，搜索出来基本都是如何使用的

[sunway1988]

最后总结一下，主要实现方案如下：

1. 首先，根据配置文件中所有的升级路径创建图，权值设为 1 ；
2. 根据上面创建的图，寻找最短路径，即为升级的最优路径；
3. 依次（反序，即先高版本的升级路径，假设 A 需要 1.0-1.3-1.5 ，则先处理 1.3-1.5 ，后处理 1.0-1.3 ）判断上述产品升级的依赖情况，如有依赖，则将该产品升级信息入栈，假设记为{‘ A ’， ‘ 1.0 ’，‘ 1.3 ’}，即 A 由 1.0 升级到 1.3 ，然后按照上述方式判断 A 的依赖的升级路径和是否存在依赖，后面的操作同 A ；
4. 依次将升级情况入栈，最终栈中保存了升级的先后顺序，依次出栈并完成升级，此时依赖关系已经转化为了升级顺序，只需要专注升级自身即可。

感谢各位的回答，谢谢！

[xylophone21]

忽然发现既然你发在 Python 节点下，那你的那些模块都是 Python 模块？那是不是自己建一个 pip 的服务器，用 pip 管理就可以了？

至于看资料，就看 pip 的官网吧