摘要:動態規劃是研究一類最優化問題的算法，本文首先分析它的特點，然后用它來解決最短路徑問題。

將動態規劃思想運用到求解最短路徑問題中，將過程劃分為幾個階段，在每階段中選取最優策略，最后找到整個過程的總體最優目標即最短徑路。給出了動態規劃方法的基本原理，建立了動態規劃數學模型，通過一個實際應用例子具體說明動態規劃求解最短路徑問題的過程，并總結出動態規劃在此類問題中的優越性。

文章在分析動態規劃的特點的同時，還根據這些特點分析了我們在解題中應該怎樣利用這些特點，怎樣運用動態規劃解決最短路徑問題。這對我們的解題與實踐有一定的指導意義。

關鍵詞 動態規劃；最短路徑；多階段決策；優化；算法

目錄

摘要

Abstract

1 緒論-1

1.1 概述-1

1.2 動態規劃的背景介紹-1

1.3 研究方法及主要研究內容-1

2 動態規劃-3

2.1 動態規劃的本質-3

2.1.1 動態規劃的基本概念-3

2.1.2最優化原理-4

2.1.3動態規劃適用的條件-4

2.1.4動態規劃的基本思想-4

2.1.5動態規劃的基本方程（數學模型）-5

2.1.6建立動態規劃模型的步驟-5

2.2動態規劃的設計與實現-5

2.2.1動態規劃的多樣性-6

2.2.2動態規劃的模式性-7

2.2.3動態規劃的求解方法-8

2.3動態規劃與一些算法的比較-15

2.3.1動態規劃與遞推-15

2.3.2動態規劃與搜索-18

3 最短路徑問題的求解-20

3.1問題的提出-20

3.2問題的分析-20

3.3模型的建立與求解-21

結論-26

致謝-27

參考文獻-28