最短路径问题的动态规划方法研究_信息与计算科学.zip

摘要:动态规划是研究一类最优化问题的算法，本文首先分析它的特点，然后用它来解决最短路径问题。

将动态规划思想运用到求解最短路径问题中，将过程划分为几个阶段，在每阶段中选取最优策略，最后找到整个过程的总体最优目标即最短径路。给出了动态规划方法的基本原理，建立了动态规划数学模型，通过一个实际应用例子具体说明动态规划求解最短路径问题的过程，并总结出动态规划在此类问题中的优越性。

文章在分析动态规划的特点的同时，还根据这些特点分析了我们在解题中应该怎样利用这些特点，怎样运用动态规划解决最短路径问题。这对我们的解题与实践有一定的指导意义。

关键词 动态规划；最短路径；多阶段决策；优化；算法

目录

摘要

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