哈工大数据结构实验三——设备更新问题
设备更新问题
1.实验要求
2.构造图求解
初看这道题我想用动态规划求解，不过由于本章学的是图的最短路径问题，所以我使劲的想构造图来解决这个问题。
构造的图是有向图，因为时间是顺着流的。
解题思路:
- 图的每个顶点的编号表示的是第几年初，比如顶点1表示第1年初。
- 图中任意两个顶点i和j有一条有向边，表示在第i年购买了一台机器，这台一直用到了第j年。(第j年没用这台机器)
- 图的任意两个顶点之间i和j的权重，表示第i年到第j年的使用机器的费用。(不包括第j年)
第i个节点到第j个节点的费用怎么算呢？就是等于第i年购买某台机器的费用+ 第i年到第j年的维修费用。
- 除了给出的n年需要构造n个节点之外，我需要借助第n+1个节点。所有的其他顶点都有一条边指向第n+1个节点，表示这n年的总开销。
想一想为什么？
因为我的节点的含义是每一年的开始。我们要统计n年的费用肯定得统计到第n年结束。也就是一直统计到第n+1个节点。
所有的其他顶点都有一条边指向第n+1个节点表示我在其他的某年购买了一台机器我就不再购买机器了，一直用到第n年年底。
- 因此我们只要把所求的问题构造出图，然后问题的求解就是求第1个节点到第n+1个节点的最短路径。
3.举例子说明
拿实验要求给的例子说明
那么我们构造的有向图为：
上图的邻接矩阵为
(节点0表示第1年，因为数组是从下标0开始存储的，所以就这样表示)
第i年到第j年的权重=第i年机器的费用+第i年到第j年的维修费
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 0 | 0 | 11+5=16 | 11+5+6=22 | 11+5+6+8=30 | 11+5+6+8+11=41 | 11+5+6+8+11+18=59 |
| 1 | 无穷 | 0 | 11+5=16 | 11+5+6=22 | 11+5+6+8=30 | 11+5+6+8+11=41 |
| 2 | 无穷 | 无穷 | 0 | 12+5=17 | 12+5+6=23 | 12+5+6+8=31 |
| 3 | 无穷 | 无穷 | 无穷 | 0 | 12+5=17 | 12+5+6=23 |
| 4 | 无穷 | 无穷 | 无穷 | 无穷 | 0 | 13+5=18 |
| 5 | 无穷 | 无穷 | 无穷 | 无穷 | 无穷 | 0 |
如上图所示，当把图构造出来后，只需要利用最短路径算法(Dijkstra算法或者Floyd算法即可求解出来。)
4.图的最短路径求解
我在另一片博客详细讲解了Dijkstra算法和Floyd算法。详细讲解了单源最短路径和任意两个最短路径的求解方法。
因此，你需要做的就是按照我上述的思路建立一个有向图，然后跑一遍图最短路径算法即可。
具体代码暂时不公布，没时间写。我自己也有很多实验ddl要写，哭了。。
动态规划算法暂时没时间写，以后再公布。。
点个关注，点个赞再走啊啊啊