中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當(dāng)前位置: 首頁 > news >正文

網(wǎng)站添加背影音樂怎么做深圳網(wǎng)絡(luò)營(yíng)銷怎么推廣

網(wǎng)站添加背影音樂怎么做,深圳網(wǎng)絡(luò)營(yíng)銷怎么推廣,企業(yè)網(wǎng)站可以免費(fèi)做嗎,網(wǎng)站建設(shè)工程師 html5問題描述 物流問題 有一個(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)&#xff…

問題描述

物流問題

????????有一個(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)123456789
元素值48610812141715
狀態(tài)轉(zhuǎn)換0->10->20->31->43->55->65->75->87->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;
}

感謝大家的觀看

http://www.risenshineclean.com/news/5389.html

相關(guān)文章:

  • 網(wǎng)絡(luò)營(yíng)銷的概念和特點(diǎn)商丘搜索引擎優(yōu)化
  • 邢臺(tái)地區(qū)網(wǎng)站建設(shè)痘痘如何去除效果好
  • 惠陽營(yíng)銷網(wǎng)站制作免費(fèi)外鏈生成器
  • 北交所公司企業(yè)債券開市合肥優(yōu)化排名推廣
  • 網(wǎng)站logo做黑頁百度首頁精簡(jiǎn)版
  • qq網(wǎng)頁版網(wǎng)址優(yōu)化搜索引擎
  • 2017網(wǎng)站備案抽查站長(zhǎng)工具seo診斷
  • 網(wǎng)站限時(shí)搶購(gòu)怎么做網(wǎng)絡(luò)服務(wù)商在哪咨詢
  • 深圳 電子商務(wù)網(wǎng)站開發(fā)青島網(wǎng)站推廣公司排名
  • 網(wǎng)站建設(shè)和推廣大概需要多少費(fèi)用福州seo代理計(jì)費(fèi)
  • 王者榮耀做網(wǎng)站什么軟件可以免費(fèi)發(fā)廣告
  • 怎么用sharepoint做網(wǎng)站成功營(yíng)銷十大經(jīng)典案例
  • 建設(shè)電子商務(wù)網(wǎng)站目的指數(shù)平滑法
  • 營(yíng)銷型網(wǎng)站建設(shè)明細(xì)報(bào)價(jià)表推銷網(wǎng)站
  • 萬網(wǎng)的怎么做網(wǎng)站地圖深圳seo優(yōu)化方案
  • 那個(gè)網(wǎng)站做圖片好看電商廣告
  • 項(xiàng)目計(jì)劃書ppt模板免費(fèi)seo網(wǎng)頁推廣
  • 網(wǎng)站建設(shè)百度推廣微信營(yíng)銷的方法和技巧
  • 深圳 網(wǎng)站百度網(wǎng)盤搜索引擎官方入口
  • 帝國(guó)軟件怎么做網(wǎng)站常州網(wǎng)絡(luò)推廣哪家好
  • 鄭州制作個(gè)人網(wǎng)站品牌策劃公司排名
  • c語言 做網(wǎng)站深圳龍崗區(qū)布吉街道
  • 網(wǎng)站建設(shè)發(fā)展方向北京seo課程培訓(xùn)
  • 做一款網(wǎng)站seoheuni
  • 免費(fèi)靜態(tài)網(wǎng)站模板下載廣州最新疫情情況
  • 中國(guó)電信 網(wǎng)站備案重慶網(wǎng)站制作
  • 剛做的網(wǎng)站搜索不到百度競(jìng)價(jià)推廣怎么做
  • 派出所web網(wǎng)站建設(shè)策劃案seo的方式包括
  • 防城港市建設(shè)工程質(zhì)量監(jiān)督站網(wǎng)站接app推廣的單子在哪接
  • 新手做哪類網(wǎng)站常用的網(wǎng)絡(luò)營(yíng)銷方法有哪些