論文開題：基于有限視距的最短邊界尋路

大學本科畢業(yè)論文(設(shè)計)開題報告
學院：計算機科學與技術(shù)學院　　　　　　　　　　　　　 專業(yè)班級：軟件二班

課題名稱 基于有限視距的最短邊界尋路

1、本課題的的研究目的和意義：

總體目標：實踐大學四年學習的各種計算機知識，訓練編程能力，培養(yǎng)編寫較大軟件的綜合素養(yǎng)。

具體畢業(yè)設(shè)計目標：針對給定的現(xiàn)實環(huán)境(如小區(qū)的平面圖)，以及巡視設(shè)備和人員現(xiàn)狀，設(shè)計并實現(xiàn)一個能夠規(guī)劃無死角巡視小區(qū)邊界的巡查路徑，并盡可能高效的完成。

本課題研究意義：隨著計算機科學的發(fā)展，人們生產(chǎn)生活經(jīng)濟利潤的提高，最短邊界尋路問題逐漸成為計算機科學、運籌學、地理信息科學等學科的一個研究熱點。也正因為基于有限視距的最短邊界尋路問題在實際生活中應(yīng)用廣泛，優(yōu)化該算法和提高該算法的求解效率具有重大的現(xiàn)實意義。為研究本算法在一些出行問題、管理問題、工程問題及實際生活問題中的應(yīng)用，為企業(yè)和個人提供方便的選擇方法。

同時也為參加數(shù)學建模的同學提供一些解題的思路與方法，為比賽提供有利的資源。最后應(yīng)用本算法解決現(xiàn)實環(huán)境(如小區(qū)的平面圖)，以及巡視設(shè)備和人員現(xiàn)狀，設(shè)計并實現(xiàn)一個能夠規(guī)劃無死角巡視小區(qū)邊界的巡查路徑，并盡可能對其優(yōu)化。



2、文獻綜述（國內(nèi)外研究情況及其發(fā)展）：


……（新文秘網(wǎng)http://www.120pk.cn省略892字，正式會員可完整閱讀）……　
26; 選擇適合的數(shù)據(jù)結(jié)構(gòu)
• 考慮如何把巡視人員或工具的“有限視距”加入到最短路徑的約束中
• 編寫高效的算法

C. 設(shè)計合理



6、本課題的進度安排：

~2013.3：閱讀文獻，了解課題
2013.3 ~ 2013.5：編寫代碼，調(diào)試
2013.5 ~2013.6：畢業(yè)論文，畢業(yè)答辯


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字，請閱讀下面提示信息。收藏《論文開題：基于有限視距的最短邊界尋路》）