论文开题：基于有限视距的最短边界寻路

大学本科毕业论文(设计)开题报告
学院：计算机科学与技术学院　　　　　　　　　　　　　 专业班级：软件二班

课题名称 基于有限视距的最短边界寻路

1、本课题的的研究目的和意义：

总体目标：实践大学四年学习的各种计算机知识，训练编程能力，培养编写较大软件的综合素养。

具体毕业设计目标：针对给定的现实环境(如小区的平面图)，以及巡视设备和人员现状，设计并实现一个能够规划无死角巡视小区边界的巡查路径，并尽可能高效的完成。

本课题研究意义：随着计算机科学的发展，人们生产生活经济利润的提高，最短边界寻路问题逐渐成为计算机科学、运筹学、地理信息科学等学科的一个研究热点。也正因为基于有限视距的最短边界寻路问题在实际生活中应用广泛，优化该算法和提高该算法的求解效率具有重大的现实意义。为研究本算法在一些出行问题、管理问题、工程问题及实际生活问题中的应用，为企业和个人提供方便的选择方法。

同时也为参加数学建模的同学提供一些解题的思路与方法，为比赛提供有利的资源。最后应用本算法解决现实环境(如小区的平面图)，以及巡视设备和人员现状，设计并实现一个能够规划无死角巡视小区边界的巡查路径，并尽可能对其优化。



2、文献综述（国内外研究情况及其发展）：


……（新文秘网https://www.wm114.cn省略892字，正式会员可完整阅读）……　
26; 选择适合的数据结构
• 考虑如何把巡视人员或工具的“有限视距”加入到最短路径的约束中
• 编写高效的算法

C. 设计合理



6、本课题的进度安排：

~2013.3：阅读文献，了解课题
2013.3 ~ 2013.5：编写代码，调试
2013.5 ~2013.6：毕业论文，毕业答辩


7、参考文献：
[1] R. Honsberger, “Mathematical Gems II”, Mathematical Association of America, 1976.
[2] V. Chvatal, “A Combinatorial Theorem in Plane Geometry”,Journal of Combinatorial Theory(B) 18 (1975), pp 39-41.
[3] S.Fisk, “A Short Proof of Chvatal’s Watchman Theorem”, Journal of Combinatorial Theory B,24:374,1978
[4]. A. Aggarwal. The Art Gallery Theorem: Its variations, applications and algorithmic;aspects.PhD thesis, John Hopkins University, 1984.
[5] D.T. Lee and A.K. Lin. Computational comple*ity of art gallery problems. IEEE Trans. Info. Theory,32(2):276-282, 1986.
[6] J. ORourke. Art Gallery Theorems and Algorithms.O*ford univ. press, 1987. ISBN 0-19-503965-3.
[7] Shermer, T.: Recent results in art galleries. In: Proc. of the IEEE, pp. 1384–1399 (1992)
[8] Urrutia, J.: Art gallery and illumination problems. In: Sac, J., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 973–1027. Elsevier Science Publishers, Amsterdam (2000)
[9] W. Chin and S. Ntafos, “Optimum Watchman Routes”, Inf. Processing Letters, 28:39–44, 1988.
[10]W. Chin and S. Ntafos, “Shortest Watchman Routes in Simple Polygons” , Discret and Computational Geometry, 6(1):9-31, 1991
[11]*.-H.Tan, T.Hirata, Y.Inagaki, “An Incremental Algorithm for Constructing Shortest Watchman Routes”, In Proc.ISA’91 Algorithms, pages 163-175. Springer Verlag, Lecture Notes in Computer Science 557,1991.
[12]B.Chazelle. “Triangulating a Simple Polygon in Linear Time”. In Proc. 31st Symposium on Foundations of Computer Science, pages 220-230, 1990.
[13] J. C. Culberson , R. A. Reckhow, “Covering Polygons is Hard”, Proc. 29th Symposium on Foundations of Computer Science, 1988.
[14] J. O’Rourke, K. J. Supowit, “Some NP-hard Polygon Decomposition Problems”, IEEE Tran ……（未完，全文共4961字，当前仅显示2506字，请阅读下面提示信息。收藏《论文开题：基于有限视距的最短边界寻路》）