論文開(kāi)題：基于有限視距的最短邊界尋路

大學(xué)本科畢業(yè)論文(設(shè)計(jì))開(kāi)題報(bào)告
學(xué)院：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院　　　　　　　　　　　　　 專(zhuān)業(yè)班級(jí)：軟件二班

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

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

總體目標(biāo)：實(shí)踐大學(xué)四年學(xué)習(xí)的各種計(jì)算機(jī)知識(shí)，訓(xùn)練編程能力，培養(yǎng)編寫(xiě)較大軟件的綜合素養(yǎng)。

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

本課題研究意義：隨著計(jì)算機(jī)科學(xué)的發(fā)展，人們生產(chǎn)生活經(jīng)濟(jì)利潤(rùn)的提高，最短邊界尋路問(wèn)題逐漸成為計(jì)算機(jī)科學(xué)、運(yùn)籌學(xué)、地理信息科學(xué)等學(xué)科的一個(gè)研究熱點(diǎn)。也正因?yàn)榛谟邢抟暰嗟淖疃踢吔鐚ぢ穯?wèn)題在實(shí)際生活中應(yīng)用廣泛，優(yōu)化該算法和提高該算法的求解效率具有重大的現(xiàn)實(shí)意義。為研究本算法在一些出行問(wèn)題、管理問(wèn)題、工程問(wèn)題及實(shí)際生活問(wèn)題中的應(yīng)用，為企業(yè)和個(gè)人提供方便的選擇方法。

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



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


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

C. 設(shè)計(jì)合理



6、本課題的進(jìn)度安排：

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


7、參考文獻(xiàn)：
[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字，當(dāng)前僅顯示2506字，請(qǐng)閱讀下面提示信息。收藏《論文開(kāi)題：基于有限視距的最短邊界尋路》）