最短路问题及其若干实际运用开题报告

1. 研究目的与意义

最短路问题是网络理论解决的典型问题之一。随着时代的飞速发展，最短路问题的优化理念在实际生活中有着越来越广泛的运用。最短路径问题在计算机科学、交通工程学、运筹学、地理信息学等学科的研究中一直是一个热点问题．所有的路径中距离最短的一条，我们把它称作最短路径．而最短路径问题不仅仅指的是距离上的最短路径，更能够引申到其他意义上．相应地，最短路径问题在实际的应用中就成为最快路径问题、最低费用问题等．为了简化问题，很多问题我们通过建立数学模型突出要点，而建立图论模型的目的则是一样的，便于更加深入地研究问题的本质，例如根据图论的基本理论来分析图论模型性质，或者根据典型的图论算法对图论模型进行求解，图论模型中的相关算法及理论其他模型不具备。许多优化问题可以使用这一模型，如可以用来解决管道铺设、线路安装、设备更新、场址布局等等，而这些和经济问题联系在一起，将能实现费用的最优化，所以研究最短路问题在现实生活中有着重要的意义。

2. 研究内容和预期目标

研究内容：许多优化问题可以可以使用最短路问题的思想和应用来解决，如设备更新、管道铺设、线路安排、厂区布局等，现在需要研究的就是如何把运筹学中的最短路问题这一小块内容放到现实生活中，使之用来实现最短路问题的运用。

拟解决的关键问题：运用动态规划中的最短路问题设计最优的路线铺设使效益达到最高。但某些最短路问题（如道路不能整齐分段着）构造动态规划方程比较困难，而图论方法则比较有效，运用Dijkstra或者Floyd算法来解决设备更新和选址问题等，使之最优。

3. 国内外研究现状

关于最短路问题国内外的研究目前没有什么太大的差异，都是基于最短路算法的原理，将最短路问题投入到实际生活中的运用中去，如路线的优化问题，再具体化就是物流和旅游还有就是铁路规划等，再者就是将最短路问题和不同的学术问题联系在一起，如将最短路运用到计算机科学和随机过程上等等。

4. 计划与进度安排

关于即将要写论文的计划，在前期，我将先阅读有关数学方面的运筹学中关于最短路问题的书籍来简单了解最短路的概念和算法，然后查找关于最短路问题的资料加强我对最短路的理解，其次再去查看相关资料中有关最短路的运用。在中期，我将和论文的指导老师鲍老师加强联系，让他给予必要的指导，以便自己顺利的完成初稿。在后期，我将和指导老师鲍老师一起查找论文的不足之处，然后好好修改为最后呈现出一篇较好的论文做好最后的准备。

5. 参考文献