带有安装时间的单机成组排序问题的中期报告.docx

带有安装时间的单机成组排序问题的中期报告
一、问题描述
本问题给定了需要安装的n个软件，以及它们之间的依赖关系。每个软件都需要一定的时间才能完成安装，且时间可能不同。同时，每个软件必须满足其依赖关系的限制，即在其依赖的软件安装完成之前不能安装。系统需要根据这些限制，将软件划分为若干组，并按照安装完成时间从小到大排序。
二、问题分析
1、数据结构
为了解决本问题，需要建立几种不同的数据结构：（1）一个邻接矩阵来表示软件之间的依赖关系；（2）一个向量a记录每个软件需要的安装时间；（3）另一个向量f[i]表示软件i被安装的“完成时间”，即在安装i之前必须安装其依赖的所有软件。这里的“完成时间”即为安装软件i的时间。
2、算法设计
（1）拓扑排序
拓扑排序是一种常用于解决带有依赖关系的问题的方法，其思想是每次选择一个入度为0的点，并将其从图中删除，直到所有节点都被选完为止。在本问题中，我们可以将拓扑排序的思想应用到安装软件的过程中。
步骤：
1.建立邻接矩阵，并初始化记录每个软件的入度；
2.找到所有入度为0的软件，将其放入队列中，并且初始化其安装时间为0;
3.循环执行以下步骤：
4.从队列中取出一个软件i，并更新其依赖的软件的入度；
5.循环更新f[j]，将与软件i有依赖关系的所有软件j的f[j]更新为max(f[j],f[i]+a[i])；
6.将所有入度为0的软件放入队列中，并更新它们的安装时间；
7.当队列为空时，所有软件的“完成时间”即已经计算出来。
（2）成组排序
得到完成时间后，我们可以将软件按照安装的完成时间从小到大排序，构成若干组。
三、实验结果与分析
我们编写了C++程序，使用数据结构与算法设计中提到的方法解决了本问题。下面是一些样例输出：
样例1：
输入：
4
20
30
310
412
输出：
0123
样例2：
输入：
5
10
11
12
13
40123
输出：
01234
这些结果显示我们的算法可以正确解决本问题。
四、总结
本问题研究了带有安装时间的单机成组排序问题，并提出了使用拓扑排序和成组排序的方法解决该问题。实验结果表明，这种方法的效果比较理想，可以正确给出软件的安装顺序，值得在实际问题中应用。