資源描述：
《動(dòng)態(tài)規(guī)劃-貨郎擔(dān)問題算法設(shè)計(jì)與實(shí)現(xiàn)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、西安建筑科技大學(xué)課程設(shè)計(jì)（論文）任務(wù)書專業(yè)班級(jí)：信管1501學(xué)生姓名：指導(dǎo)教師（簽名）：一、課程設(shè)計(jì)（論文）題目動(dòng)態(tài)規(guī)劃：貨郎擔(dān)問題算法設(shè)計(jì)與實(shí)現(xiàn)二、本次課程設(shè)計(jì)（論文）應(yīng)達(dá)到的目的《系統(tǒng)優(yōu)算法設(shè)計(jì)與實(shí)現(xiàn)》課程設(shè)計(jì)是實(shí)踐教學(xué)環(huán)節(jié)的重要組成部分，其目的是通過課程設(shè)計(jì)加深學(xué)生對系統(tǒng)優(yōu)算法設(shè)計(jì)與實(shí)現(xiàn)基本知識(shí)掌握和基本編程技能的培養(yǎng)，提高綜合運(yùn)用知識(shí)解決實(shí)際問題的能力；本次要求學(xué)生通過掌握系統(tǒng)優(yōu)算法設(shè)計(jì)與實(shí)現(xiàn)的程序設(shè)計(jì)方法，以提高學(xué)生獨(dú)立分析問題、解決問題的能力，逐步增強(qiáng)實(shí)際工程訓(xùn)練。三、本次課程設(shè)計(jì)（論文）任務(wù)的主要內(nèi)容和要求設(shè)計(jì)內(nèi)容：貨郎擔(dān)問題（也稱TSP問題），其一般提法為：有n個(gè)城市
2、，用1，2，…，n表示，城i,j之間的距離為cij，有一個(gè)貨郎從城市1出發(fā)到其他城市一次且僅一次，最后回到城市1，怎樣選擇行走路線使總路程最短。S表示從v1到vi中間所可能經(jīng)過的城市集合，S實(shí)際上是包含除v1和vi兩個(gè)點(diǎn)之外的其余點(diǎn)的集合，但S中的點(diǎn)的個(gè)數(shù)要隨階段數(shù)改變。狀態(tài)變量（i，S）表示：從v1點(diǎn)出發(fā)，經(jīng)過S集合中所有點(diǎn)一次最后到達(dá)vi。其動(dòng)態(tài)規(guī)劃遞推關(guān)系為 f(i,S)=min{cij+g(j,S-{j})} f(1,V-{1})=min{c1k+g(k,V-{1,k})}??(2≤k≤n)要求：1．提交正確的和完整的程序設(shè)計(jì)代碼。2．提交設(shè)計(jì)說明書。3.接受現(xiàn)場檢驗(yàn)。四、應(yīng)
3、收集的資料及主要參考文獻(xiàn)：應(yīng)收集的資料：本次設(shè)計(jì)應(yīng)該收集和題目背景的有關(guān)資料。主要參考文獻(xiàn)：1.胡運(yùn)權(quán).《運(yùn)籌學(xué)》.清華大學(xué)出版社，2012五、審核批準(zhǔn)意見教研室主任（簽字）設(shè)計(jì)總說明貨郎擔(dān)問題（TSP問題）是指貨郎要到n個(gè)城市售賣貨物然后回到出發(fā)城市，要求各個(gè)城市經(jīng)歷一次且僅經(jīng)歷一次，并要求所走的路程最短。該問題又稱為旅行商問題、郵遞員問題、售貨員問題，是圖問題中最廣為人知的問題。動(dòng)態(tài)規(guī)劃算法是解決多階段決策過程最優(yōu)化問題的一種常用方法，難度比較大，技巧性也很強(qiáng)。本次課設(shè)運(yùn)用動(dòng)態(tài)規(guī)劃解決貨郎擔(dān)問題，動(dòng)態(tài)規(guī)劃的基本思想是：把求解的問題分成許多若干階段或許多子問題，然后按順序求解各子問
4、題。前一子問題的解，為后一子問題的求解提供了有用的信息，在求解任一子問題時(shí)列出各種可能的局部解，通過決策保留那些有可能達(dá)到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問題最后一個(gè)子問題就是初始問題的解。通過圖的關(guān)系矩陣來表示各個(gè)城市之間的關(guān)系，二維數(shù)組表示頂點(diǎn)之間的距離關(guān)系，對子問題進(jìn)行求解比較，最后得出所求結(jié)果。關(guān)鍵字：貨郎擔(dān)問題動(dòng)態(tài)規(guī)劃圖矩陣目錄1緒論11.1內(nèi)容簡介11.2本次課設(shè)目的11.3課設(shè)內(nèi)容22（此處用你的題目中的重點(diǎn)研究部分名稱代替）設(shè)計(jì)說明32.1程序設(shè)計(jì)過程詳述32.2編程實(shí)現(xiàn)過程詳述32.4原代碼43實(shí)驗(yàn)研究小結(jié)73.1使用說明詳述73.1.1本部分功能操作注意
5、事項(xiàng)73.1.2本部分功能與其他系統(tǒng)的關(guān)系73.2測試案例詳述8參考文獻(xiàn)10第0頁共14頁1緒論1.1內(nèi)容簡介貨郎擔(dān)問題(TSP)是指在城鎮(zhèn)1~n中，已知各城市距離，貨郎從城鎮(zhèn)1出發(fā)，經(jīng)過所有城鎮(zhèn)一次，且僅一次，最后仍回到原出發(fā)的城鎮(zhèn)1，應(yīng)如何選擇行路線可使總行程最短1.2本次課設(shè)目的設(shè)計(jì)出算法將待求解問題分解成若干個(gè)相互重疊的子問題，每個(gè)子問題對應(yīng)決策過程的一個(gè)階段，一般來說，子問題的重疊關(guān)系表現(xiàn)在對給定問題求解的遞推關(guān)系（也就是動(dòng)態(tài)規(guī)劃函數(shù)）中，將子問題的解求解一次并填入表中，當(dāng)需要再次求解此子問題時(shí)，可以通過查表獲得該子問題的解而不用再次求解，從而避免了大量重復(fù)計(jì)算。從而求出貨
6、郎在1～n個(gè)城市中以第一個(gè)城市為起點(diǎn)走過n個(gè)城市并最終回到第一個(gè)城市的最短距離和路線。1.3課設(shè)內(nèi)容貨郎擔(dān)問題（也稱TSP問題），其一般提法為：有n個(gè)城市，用1，2，…，n表示，城i,j之間的距離為cij，有一個(gè)貨郎從城1出發(fā)到其他城市一次且僅一次，最后回到城市1，怎樣選擇行走路線使總路程最短。因此，假設(shè)周游路線是開始于結(jié)點(diǎn)1并終止于結(jié)點(diǎn)1的一條簡單路徑。每一條周游路線都由一條邊〈1,k〉和一條由結(jié)點(diǎn)k到結(jié)點(diǎn)1的路徑所組成,其中k∈V-{1};而這條由結(jié)點(diǎn)k到結(jié)點(diǎn)1的路徑通過V-{1,k}的每個(gè)結(jié)點(diǎn)各一次。容易看出,如果這條周游路線是最優(yōu)的,那么這條由k到1的路徑必定是通過V-{1,
7、k}中所有結(jié)點(diǎn)的由k到1的最短路徑,因此最優(yōu)性原理成立。設(shè)第9頁共14頁(i,S)是由結(jié)點(diǎn)i開始,通過S中的所有結(jié)點(diǎn),在結(jié)點(diǎn)1終止的一條最短路徑長度。f(1,V-{1})是一條最優(yōu)的周游路線長度。于是,可以得出f(1,V-{1})=min{c1k?+g(k,V-{1,k})}??2≤k≤n一般化可得f(i,S)=min{cij+g(j,S-{j})}第9頁共14頁2（動(dòng)態(tài)規(guī)劃：貨郎擔(dān)問題算法設(shè)計(jì)與實(shí)現(xiàn)）設(shè)計(jì)說明2.1程序設(shè)計(jì)過程詳述已知ｎ個(gè)城市間距離，求從
