設備更新問題
- 1.實驗要求
- 2.構造圖求解
- 3.舉例子說明
- 4.圖的最短路徑求解
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要寫，哭了，，
動態規劃演算法暫時沒時間寫，以后再公布，，
點個關注，點個贊再走啊啊啊
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/204607.html
標籤：其他