畢業(yè)論文【設(shè)計】動態(tài)規(guī)劃-貨郎擔(dān)問題算法設(shè)計與實(shí)現(xiàn)

《畢業(yè)論文【設(shè)計】動態(tài)規(guī)劃-貨郎擔(dān)問題算法設(shè)計與實(shí)現(xiàn)》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、必姜達(dá)統(tǒng)科技A#課程設(shè)計（論文）任務(wù)書專業(yè)班級：信管1501學(xué)生姓名：_指導(dǎo)教師（簽名）：「二7W趕蠶評??（￥支-）-If??動態(tài)規(guī)劃：貨郎擔(dān)問題算法設(shè)計與實(shí)現(xiàn)二、本次課程設(shè)計（論文）應(yīng)達(dá)到的目的《系統(tǒng)優(yōu)算法設(shè)計與實(shí)現(xiàn)》課程設(shè)計是實(shí)踐教學(xué)環(huán)節(jié)的重耍組成部分,其目的是通過課程設(shè)計加深學(xué)生對系統(tǒng)優(yōu)算法設(shè)計與實(shí)現(xiàn)基本知識掌握和基本編程技能的培養(yǎng)，提高綜合運(yùn)用知識解決實(shí)鉍問題的能力；本次要求學(xué)生通過掌握系統(tǒng)優(yōu)算法設(shè)計與實(shí)現(xiàn)的程序設(shè)計方法，以提高學(xué)生獨(dú)立分析問題、解決問題的能力，逐步増強(qiáng)實(shí)際工程訓(xùn)練。三、本次課程設(shè)計（論文）任務(wù)的主要內(nèi)容和要

2、求設(shè)計內(nèi)容：貨郎擔(dān)問題（也稱TSP問題），其一般提法為：有n個城市，用1，2,…，n表示，城i,j之間的距離為有一個貨郎從城市1出發(fā)到其他城市一次且僅一次，最后回到城市1，怎樣選擇行走路線使總路程最短。5’表示從W到「7屮間所可能經(jīng)過的城市集合，S實(shí)際上是包含除「7和「7兩個點(diǎn)之外的其余點(diǎn)的集合，但S中的點(diǎn)的個數(shù)要隨階段數(shù)改變。狀態(tài)變量（/,幻表示：從點(diǎn)出發(fā)，經(jīng)過S集合中所有點(diǎn)一次最后到達(dá)r/。其動態(tài)規(guī)劃遞推關(guān)系為/（/，5）=min{}/（l,=min{^+k,f’-{l,々}）}（2彡杉n）要求：1.提交正確的和完整的程序設(shè)計代碼

3、。2.捉交設(shè)計說明15。3.接受現(xiàn)場檢驗。四、應(yīng)收集的資料及主要參考文獻(xiàn)：應(yīng)收集的資料：本次設(shè)計應(yīng)該收集和題F1??景的有關(guān)資料。主要參考文獻(xiàn)：1.胡運(yùn)權(quán).《運(yùn)籌學(xué)》.淸平人學(xué)出版社，2012五、審核批準(zhǔn)意見教研室主任（簽字）設(shè)計總說明貨郎枳M題（TSP問題）是指貨郎要到n個城市售賣貨物然后回到出發(fā)城市，要求各個城市經(jīng)歷一次且僅經(jīng)歷一次，并要求所走的路程最短。該問題又稱為旅行商問題、郵遞員問題、售貨員問題，是圖問題中最廣為人知的M題。動態(tài)規(guī)劃算法是解決多階段決策過程最優(yōu)化W題的一種常用方法，難度比較大，技巧性也很強(qiáng)。本次課設(shè)運(yùn)用動態(tài)規(guī)

4、劃解決貨郎枳問題，動態(tài)規(guī)劃的基本思想是：把求解的fuj題分成許多若干階段或許多子fuj題，然后按順序求解各子問題。前一子問題的解，為后一子問題的求解提供了有用的信息，在求解任一子問題吋列出各種吋能的局部解，通過決策保留那些冇可能達(dá)到最優(yōu)的局部解，丟棄其他局部解。依次解決各子W題最后一個子W題就是初始W題的解。通過圖的關(guān)系矩陣來表示各個城市之間的關(guān)系，二維數(shù)組表示頂點(diǎn)之間的距離關(guān)系，對子問題進(jìn)行求解比較，最后得出所求結(jié)果。關(guān)鍵字：貨郎枳問題動態(tài)規(guī)劃圖矩陣目錄1雜11.1內(nèi)容簡介11.2本次課設(shè)目的11.3課設(shè)內(nèi)容22（此處用你的題目中的

5、重點(diǎn)研究部分名稱代替）設(shè)計說明32.1程序設(shè)計過程詳述32.2編程實(shí)現(xiàn)過程詳述32.4原代碼43實(shí)驗研究小結(jié)73.1使用說明詳述73.1.1本部分功能操作注意事項73.1.2本部分功能與其他系統(tǒng)的關(guān)系73.2測試案例詳述8南犬101緒論1.1內(nèi)容簡介貨郎捫問題（TSP）是指在城鎮(zhèn)1?n中，已知各城市距離，貨郎從城鎮(zhèn)1出發(fā)，經(jīng)過所有城鎮(zhèn)一次，且僅一次，最后仍回到原出發(fā)的城鎮(zhèn)1，應(yīng)如何選擇行路線吋使總行程最短1.2本次課設(shè)目的設(shè)計出算法將待求解問題分解成若干個相互重疊的子問題，每個子問題對應(yīng)決策過程的一個階段，一般來說，子悶題的重疊關(guān)系表

6、現(xiàn)在對給定問題求解的遞推關(guān)系（也就是動態(tài)規(guī)劃函數(shù)）中，將子悶題的解求解一次丼填入表中，當(dāng)需要再次求解此子問題時，可以通過查表獲得該子問題的解而不用再次求解，從而避免了大量重復(fù)計算。從而求出貨郎在1?n個城市中以第一個城市為起點(diǎn)走過n個城市并最終回到第?一個城市的最短距離和路線。1.3課設(shè)內(nèi)容貨郎捫問題（也稱TSP問題），其一般提法為：有n個城市，用1,2,…,n表示，城i,j之間的距離為Cij,宥一個貨郎從城1出發(fā)到其他城市一次且僅一次，最后冋到城市1,怎樣選擇行走路線使總路程最短。W此，假設(shè)周游路線是開始于結(jié)點(diǎn)1并終止于結(jié)點(diǎn)1的一條

7、簡單路徑。每一?條周游路線都由一條邊〈l,k〉和一條由結(jié)點(diǎn)k到結(jié)點(diǎn)1的路徑所組成，其中k￡V-{l};而這條由結(jié)點(diǎn)k到結(jié)點(diǎn)1的路徑通過V-{1,k}的每個結(jié)點(diǎn)各一次。容易看出，如果這條周游路線是最優(yōu)的，那么這條由k到1的路徑必定是通過V-{1,k}中所宥結(jié)點(diǎn)的由k到1的最短路徑，因此最優(yōu)性原理成立。設(shè)（i,S）是由結(jié)點(diǎn)i釦及漾篇利札大璺課程設(shè)計(論文)用紙開始，通過S屮的所有結(jié)點(diǎn)，在結(jié)點(diǎn)1終止的一條最短路徑長度。/(1,V-{1})是一條最優(yōu)的周游路線長度。于是，可以得出Z(l,v-{1})=min{?+g(k,V-{1,k})}2彡

8、k彡n一般化可得f(i,S)=min{co+貧(J,S-{j})}2(動態(tài)規(guī)劃：貨郎擔(dān)問題算法設(shè)計與實(shí)現(xiàn))設(shè)計說明2.1程序設(shè)計過程詳述已知n個城巾*間距離，求從K7出發(fā)，經(jīng)蘇余城簾一次且僅一次最后返回的最短路徑和距離。