動態規劃旅行售貨員問題

動態規劃演算法的應用

課程名稱

院系學生姓名

學號專業班級

指導教師

2023年12月27日

動態規劃的應用

摘要：旅行商問題（tsp問題）時是指旅行家要旅行n個城市然後回到出發城市，要求各個城市經歷且僅經歷一次，並要求所走的路程最短。該問題又稱為貨郎擔問題、郵遞員問題、售貨員問題，是圖問題中最廣為人知的問題。

動態規劃（ dynamic programming ）演算法是解決多階段決策過程最優化問題的一種常用方法，難度比較大，技巧性也很強。利用動態規劃演算法，可以優雅而高效地解決很多貪婪演算法或分治演算法不能解決的問題。

本次課程設計運用動態規劃解決旅行售貨員問題，動態規劃的基本思想是：把求解的問題分成許多若干階段或許多子問題，然後按順序求解各子問題。前一子問題的解，為後一子問題的求解提供了有用的資訊，在求解任一子問題時列出各種可能的區域性解，通過決策保留那些有可能達到最優的區域性解，丟棄其他區域性解。

依次解決各子問題，最後乙個子問題就是初始問題的解。通過圖的關係矩陣來表示個城市之間的關係，二維陣列表示頂點之間的距離關係，對子問題進行求解比較，最後得出所求結果。

關鍵字:旅行商問題動態規劃法圖矩陣

目錄第一章緒論 1

1.演算法介紹 1

2.演算法應用 1

第二章動態規劃理論知識 2

2.1動態規劃的基本思想 2

2.2動態規劃設計步驟 2

第三章旅行售貨員問題 3

3.1問題描述：旅行售貨員問題 3

3.2演算法設計內容 3

3.3演算法分析 3

3.4流程圖 4

第四章物流配送網路 5

第五章結論 7

參考文獻 8

附件 9

動態規劃（ dynamic programming ）是解決多階段決策過程最優化問題的一種數學方法。2023年美國數學家bellman（貝爾曼）等人根據一類多階段決策問題的特性，提出了解決這類問題的「最優性原理」，並研究了許多實際問題，從而建立了最優化問題的一種新方法——動態規劃。

解決多階段決策過程最優化問題，難度比較大，技巧性也很強。利用動態規劃演算法，可以優雅而高效地解決很多貪婪演算法或分治演算法不能解決的問題。動態規劃演算法的基本思想是：

將待求解的問題分解成若干個相互聯絡的子問題，先求解子問題，然後從這些子問題的解得到原問題的解；對於重複出現的子問題，只在第一次遇到的時候對它進行求解，並把答案儲存起來，讓以後再次遇到時直接引用答案，不必重新求解。動態規劃演算法將問題的解決方案視為一系列決策的結果，與貪婪演算法不同的是，在貪婪演算法中，每採用一次貪婪準則，便做出乙個不可撤回的決策；而在動態規劃演算法中，還要考察每個最優決策序列中是否包含乙個最優決策子串行，即問題是否具有最優子結構性質。

動態規劃在工程技術、管理、經濟、工業生產、軍事及現代控制工程等方面都有廣泛的應用，而且由於動態規劃方法有其獨特之處，在解決某些實際問題時，顯得更加方便有效。由於決策過程的時間引數有離散的和連續的情況，故決策過程分為離散決策過程和連續決策過程。這種技術採用自底向上的方式遞推求值，將待求解的問題分解成若干個子問題，先求解子問題，並把子問題的解儲存起來以便以後用來計算所需要求的解。

簡言之，動態規劃的基本思想就是把全域性的問題化為區域性的問題，為了全域性最優必須區域性最優。

把求解的問題分成許多若干階段或許多子問題，然後按順序求解各子問題。前一子問題的解，為後一子問題的求解提供了有用的資訊，在求解任一子問題時列出各種可能的區域性解，通過決策保留那些有可能達到最優的區域性解，丟棄其他區域性解。依次解決各子問題，最後乙個子問題就是初始問題的解。

簡言之，動態規劃的基本思想就是把全域性的問題化為區域性的問題，為了全域性最優必須區域性最優。

（1）劃分階段：按照問題的時間或空間特徵，把問題分為若干階段。這若干階段一定要是有序的或可排序的（無後向性）。

（2）選擇狀態：將問題發展到各個階段時所出現的各種客觀情況用不同的狀態來表示出來。狀態的選擇要有無後向性。

（3）確定決策並寫出狀態轉移方程：狀態轉移就是根據上一階段的狀態和決策來匯出本階段的狀態。

某售貨員要到若干城市去推銷商品，已知各城市之間的路程。他要選定一條從駐地出發，經過每乙個城市一遍，最後回到駐地的路線，使總的路程最小，並求出最小路程。

（1）不同城市的路線和距離都不一樣。運用動態規劃演算法來設計本次課程設計，考慮到對問題進行階段劃分和狀態的選擇。使用left函式實現v'- 的下標檢索。

（2）根據遍歷城市的各個階段時所出現的情況並用不同的狀態表示出來。當然這時的狀態必須要滿足無後向性。設計第一階段則是各頂點為空，然後給賦值。

依次遍歷各城市，在tsp函式中得以實現。

在無向完全圖中，對於任意兩個頂點vj和vk，我們可以在多項式時間內找到vj和vk這兩個頂點之間的所有路徑，選擇其中路程最短的一條，令c[j,k]表示vj和vk這兩個頂點之間最短距離的那條路徑。搜尋路徑c[j,k]，找到vj到達的在c[j,k]上的第乙個頂點，記該頂點為vi，將其記錄在陣列中d，遞迴查詢vj到vi和vi到vj的最短路徑及其相應權值，最後將陣列d中的權值之和輸出出來即為所求。yn

圖4-1

為進一步說明該方法的有效性和實用性，先將該方法運用於某物流配送網路中：

設某物流配送網路圖由9個配送點組成,點為配送中心,為終點,試求自到圖中任何配送點的最短距離。圖中相鄰兩點的連線上標有兩點間的距離

首先根據網路圖以及上面的建模方法我們可以將運輸過程劃分成三個階段，分別為：第一階段，第二階段，第三階段，顯然兩點之間直線路徑小於折線路徑

階段變數用k表示；

狀態變數表示k階段初可能的位置；

決策表示k階段初可能選擇的路線；

由後向前逐步推移計算最優路徑：

當k=3時，由到只有一條路線，故=16， =8， =4， =14

當k=2時，出發點有三個，若從出發，只有乙個選擇，至，所以=27

從出發，有兩個選擇，至，所以

最短路線是

當k=1時，出發點有乙個，若從出發，至，所以=31

若從出發，至，所以=25

若從出發，至，所以=27

若從出發，至，所以=24

由上面計算得到最優路徑=24，最優路徑為

由本例項我們可以總結出動態規劃的優越性所在：

(1)求解過程，結果清晰明了；

(2)能得到一組解，有利於分析結果；

(3)易於確定全域性最優解；

本次課程設計不僅讓我鞏固了動態規劃解決問題的思想以及方法，同時還讓我學到演算法中的知識得以很好地運用，很好地實現了學以致用。在這次課程設計中我學會了不少知識，旅行售貨員問題在書上本來是用回溯法來求解的，但這次卻要動態規劃來解決旅行售貨員問題，這樣很大程度上考驗了學生對所學知識的紮實，深刻的理解以及需要很好地靈活運用

動態規劃應該在本冊書中是比較難理解但同時也是很重要的一種演算法思想。「分階段逐步求優」是其核心思想，在設計演算法時，不同城市之間路徑有多種，每種路徑的距離都不相同，這就需要對城市進行遍歷，以便求得最佳路徑。在這次課程設計中也遇到不少問題，比如在演算法設計中怎樣去記錄所求得的路徑，還有在程式除錯中for迴圈中的大括號範圍問題，但這些問題最後都一一解決了，很好地完成了本次課程設計。

[1] 演算法設計與分析（第二版）呂國英主編清華大學出版社

[2] 演算法設計與分析王紅梅胡明編著清華大學出版社2006

[3] 演算法基礎 gilles brassard，paul bratley著.邱仲潘，等譯清華大學出版社，2010

[4] 演算法之道鄒恒明機械工業出版社 2010

程式實現**

#include

int isincluded(int x,int array[3])//x是否包含在陣列中

int left(int k,int array[3],int v[8][3])//實現v'- 的下標檢索

{ int i = 0,index = 0,array_0_count = 0,array_1_count = 0,array_2_count = 0,array_3_count = 0;

int v_0_count = 0,v_1_count = 0,v_2_count = 0,v_3_count = 0;

int temp[3];

for(i = 0; i < 3; i++)

temp[i] = array[i];

for(i = 0; i < 3; i++)

if(temp[i] == k)

temp[i] = 0; //相當於去掉k這個城市

for(i = 0; i < 3; i++)

{if(temp[i] == 0)

array_0_count++;

else if(temp[i] == 1)

動態規劃旅行售貨員問題

超市售貨員教案

商場售貨員實習報告

售貨員演講稿

動態規劃旅行售貨員問題

超市售貨員教案

商場售貨員實習報告

售貨員演講稿

相關推薦