網(wǎng)站添加背影音樂怎么做深圳網(wǎng)絡(luò)營(yíng)銷怎么推廣
問題描述
物流問題
????????有一個(gè)物流公司需要從起點(diǎn)A到終點(diǎn)B進(jìn)行貨物運(yùn)輸,在運(yùn)輸過程中,該公司需要途徑多個(gè)不同的城市,并且在每個(gè)城市中都有一個(gè)配送站點(diǎn)。為了最大程度地降低運(yùn)輸成本和時(shí)間,該公司需要確定經(jīng)過哪些配送站點(diǎn),并且給出完成貨物運(yùn)輸?shù)淖疃搪窂介L(zhǎng)度。
路線分布圖
問題分析
問題簡(jiǎn)化
????????可以將該問題抽象為多段圖的最短路徑問題,其中每個(gè)城市對(duì)應(yīng)圖中的一個(gè)節(jié)點(diǎn),不同城市之間的距離對(duì)應(yīng)著圖中的邊權(quán),城市內(nèi)部的配送站可以看作同一個(gè)節(jié)點(diǎn)。從起點(diǎn)A到終點(diǎn)B的貨物運(yùn)輸路徑可以表示為多段圖中的一條路徑。找到起點(diǎn)A到終點(diǎn)B的最短路徑并給出路徑長(zhǎng)度即可求解此問題。
路線簡(jiǎn)化圖
下標(biāo) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
元素值 | 4 | 8 | 6 | 10 | 8 | 12 | 14 | 17 | 15 |
狀態(tài)轉(zhuǎn)換 | 0->1 | 0->2 | 0->3 | 1->4 | 3->5 | 5->6 | 5->7 | 5->8 | 7->9 |
最短路徑為:0->3->5->7->9,最短路徑長(zhǎng)度為15
算法設(shè)計(jì)
算法設(shè)計(jì)分析
????????多段圖的最短路徑問題滿足最優(yōu)性原理,可以使用動(dòng)態(tài)規(guī)劃法求解。
????????設(shè)Cuv表示多段圖的有向邊<u,v>上的權(quán)值,從源點(diǎn)s到終點(diǎn)t的最短路徑長(zhǎng)度記為d(s,t),原問題的部分解d(s,v),則下式成立:
d(s,v)=Csv ???????????????(<s,v>∈E)
d(s,v)=min{d(s,u)+Cuv} ????(<u,v>∈E)
數(shù)組arc[n][n]存儲(chǔ)圖的代價(jià)矩陣,數(shù)組cost[n]存儲(chǔ)最短路徑長(zhǎng)度,cost[j]表示從源點(diǎn)s到頂點(diǎn)j的最短路徑長(zhǎng)度,數(shù)組path[n]記錄轉(zhuǎn)移狀態(tài),path[j]表示從源點(diǎn)s到頂點(diǎn)j的路徑上頂點(diǎn)j的前一個(gè)頂點(diǎn)。
算法偽代碼
輸入:多段圖的代價(jià)矩陣
輸出:最短路徑長(zhǎng)度及路徑c[n][n]
1.循環(huán)變量j從1~n-1重復(fù)下述操作,執(zhí)行填表工作
??1.1考察頂點(diǎn)j的所有入邊,對(duì)于邊<i,j>∈E,執(zhí)行下述操作
?????1.1.1cost[j]=min{cost[i]+c[i][j]}
?????1.1.2path[j]=使cost[i]+c[i][j]最小的i
??1.2 j++
2.輸出最短路徑長(zhǎng)度cost[n-1]
3.循環(huán)變量i=path[n-1],循環(huán)直到path[i]=0,輸出最短路徑經(jīng)過的頂點(diǎn)
??3.1輸出path[i]
??3.2 i=path[i]
實(shí)驗(yàn)結(jié)果
最短路徑
最短路徑為:0->3->5->7->9,最短路徑長(zhǎng)度是15
算法分析
時(shí)間復(fù)雜度分析
????????算法第一部分是依次計(jì)算從源點(diǎn)到各個(gè)頂點(diǎn)的最短路徑長(zhǎng)度,由兩層循環(huán)嵌套組成,外層循環(huán)執(zhí)行n-1次,內(nèi)層循環(huán)對(duì)所有入邊進(jìn)行計(jì)算,在所有循環(huán)中,每條入邊只計(jì)算一次。假設(shè)圖的邊數(shù)為m,時(shí)間復(fù)雜度為O(m);第二部分是輸出最短路徑經(jīng)過的頂點(diǎn),設(shè)多段圖劃分為k段,時(shí)間復(fù)雜度為O(k)。整個(gè)算法的時(shí)間復(fù)雜度為O(m+k)。
空間復(fù)雜度分析
????????算法的空間復(fù)雜度主要體現(xiàn)在圖的代價(jià)矩陣arc[n][n]的存儲(chǔ),空間復(fù)雜度為O(n^2),存儲(chǔ)最短路徑長(zhǎng)度的數(shù)組cost[n]的空間復(fù)雜度為O(n),轉(zhuǎn)移狀態(tài)記錄數(shù)組path[n]的空間復(fù)雜度為O(n),所以整個(gè)算法的空間復(fù)雜度為O(n^2)。
源代碼
#include<iostream>
using namespace std;
#define INF 999
int arc[10][10]; // 最多10個(gè)點(diǎn)
int CreateGraph()
{int i, j, k;int weight;int vnum, arcnum;cout << "請(qǐng)輸入頂點(diǎn)和邊的個(gè)數(shù):";cin >> vnum >> arcnum;for (int i = 0; i < vnum; i++) // 初始化圖的代價(jià)矩陣 for (int j = 0; j < vnum; j++)arc[i][j] = INF;for (k = 0; k < arcnum; k++){cout << "請(qǐng)輸入第" << k + 1 << "條邊的兩個(gè)頂點(diǎn)和權(quán)值:";cin >> i >> j >> weight;arc[i][j] = weight;}return vnum; // 返回頂點(diǎn)的個(gè)數(shù)
}
// 求 n個(gè)頂點(diǎn)的多段圖的最短路徑
int BackPath(int n)
{int i, j, temp;int cost[100], path[100]; // 存儲(chǔ)路徑長(zhǎng)度和路徑 for (i = 1; i < n; i++){cost[i] = INF;path[i] = -1;}cost[0] = 0; // 頂點(diǎn)0為源點(diǎn) path[0] = -1;for (j = 1; j < n; j++) // 依次計(jì)算后面下標(biāo)為1到n-1的點(diǎn)(填表) for (i = j - 1; i >= 0; i--){if (cost[i] + arc[i][j] < cost[j]){cost[j] = cost[i] + arc[i][j]; // 更新值 path[j] = i; // 記錄前一個(gè)點(diǎn) }}// 輸出路徑i = n - 1;cout << "最短路徑為:" << i;while (path[i] >= 0)// 前一個(gè)點(diǎn)大于0 {cout << "<-" << path[i];i = path[i]; // 更新為前一個(gè)點(diǎn) }cout << endl;return cost[n - 1]; // 返回最短路徑長(zhǎng)度
}
int main()
{int graph = CreateGraph();cout << "最短路徑長(zhǎng)度為:" << BackPath(graph) << endl;return 0;
}
感謝大家的觀看