論文開(kāi)題：實(shí)施并改進(jìn)旅行問(wèn)題算法

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

課題名稱(chēng) 實(shí)施并改進(jìn)旅行問(wèn)題算法

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

在現(xiàn)實(shí)生活中各種各樣的加工工業(yè)上, 例如, 制衣, 制窗, 或機(jī)械加工等, 常常需要從大片的紙, 布料, 玻璃, 金屬, 等上面切割出很多的部件(假如以簡(jiǎn)單多邊形為模型),而切割的部件通常需要使面積最小或周長(zhǎng)最短. 這些應(yīng)用雖只是解決TP問(wèn)題中最初始的一步，但不難看出他的實(shí)際應(yīng)用性和重要性。TP問(wèn)題在交通運(yùn)輸、管道鋪設(shè)、旅游出行、電路板線路設(shè)計(jì)、工業(yè)材料切割以及物流配送等領(lǐng)域內(nèi)有著廣泛的應(yīng)用。解決好這個(gè)問(wèn)題對(duì)于節(jié)約時(shí)間金錢(qián)、節(jié)約城市資源、物流配送人力資源，降低工業(yè)制造類(lèi)企業(yè)不必要的開(kāi)支有著重要的意義，也會(huì)對(duì)提高運(yùn)輸效率和建設(shè)節(jié)約型社會(huì)十分有利。當(dāng)然實(shí)際上的應(yīng)用需要解決更復(fù)雜的問(wèn)題，也需要更多的人力物力，所以本課題主要以理想的條件下考慮。

2、 文獻(xiàn)綜述（
……（新文秘網(wǎng)http://jey722.cn省略698字，正式會(huì)員可完整閱讀）……　
應(yīng)的步驟進(jìn)行相應(yīng)算法的研究與實(shí)現(xiàn)，最后我將視時(shí)間允許以否把這三個(gè)部分進(jìn)行整合。
成果就是把上面所述的三個(gè)部分用開(kāi)發(fā)工具將算法實(shí)現(xiàn),如果有時(shí)間將整合到MFC中.


4、擬解決的關(guān)鍵問(wèn)題：

本課題主要介紹和應(yīng)用基于三角剖分的TP算法，所以主要解決的是如何將平面多邊形進(jìn)行三角剖分、解決如何進(jìn)行剪枝優(yōu)化所求的線段、如何利用RBA橡皮筋算法求解點(diǎn)-線—點(diǎn)最短路徑等，。因此該課題所要研究是如何把算法實(shí)現(xiàn)以及如何把算法優(yōu)化最終得到理想的效果。
所謂的技術(shù)的路線和方法無(wú)非就是運(yùn)用所學(xué)知識(shí)把算法在計(jì)算機(jī)上實(shí)現(xiàn)，這也是本課題的重中之重和難點(diǎn)所在。如果非要列出個(gè)方法那就是我將應(yīng)用vc等開(kāi)發(fā)工具進(jìn)行算法的設(shè)計(jì)和實(shí)現(xiàn)，這就是選擇算法課題的優(yōu)勢(shì)和劣勢(shì)所在。
雖然了了幾句就把解決問(wèn)題的方法搞定了，但是這其中要付出的恐怕不比別的課題少。

5、研究思路、方法和步驟：
為了解決TP問(wèn)題，本課題將引入了點(diǎn)-邊-點(diǎn)的最短路徑的思路（該知識(shí)點(diǎn)李發(fā)捷老師做過(guò)相關(guān)研究），提出基于三角剖分的TP算法如下：
1.對(duì)平面上的簡(jiǎn)單多邊形進(jìn)行三角剖分。（該部分有獨(dú)立的課）所以剖分的算法我將研究凹凸點(diǎn)判別分割簡(jiǎn)單多邊形為三角形，和實(shí)現(xiàn)凸多邊形的最優(yōu)剖分）；
2.按三角形分割的先后順序?qū)⑷切螀^(qū)域進(jìn)行編號(hào)：V1,V2,……，Vn；再將其公共邊進(jìn)行編號(hào)e1,e2,……en-1。建立一棵以三角形為節(jié)點(diǎn)V,公共邊為該樹(shù)的邊E的完整樹(shù)T；
3.運(yùn)用樹(shù)上最短路（The shortest path on the tree）算法對(duì)完整樹(shù)進(jìn)行剪枝，得到一棵目標(biāo)樹(shù)。所求解的旅行問(wèn)題的最短路徑必經(jīng)過(guò)該目標(biāo)樹(shù)的所有樹(shù)邊；
4.到這里問(wèn)題將轉(zhuǎn)化為已知起(終)點(diǎn)，有序的經(jīng)過(guò)目標(biāo)樹(shù)上所給的線段。本課題將采用橡皮筋算法（Rubber Band Algorithm，RBA），通過(guò)不斷調(diào)整點(diǎn)與線段，點(diǎn)與點(diǎn)之間的距離，循環(huán)比較每次運(yùn)算得到的路徑距離，最后得到簡(jiǎn)單多邊形內(nèi)任意聯(lián)系兩點(diǎn)間的最短路徑，即兩個(gè)帳篷間的最短路徑。
5.以步驟4中的終點(diǎn)為起點(diǎn)，重復(fù)步驟4，即可得到到下一個(gè)終點(diǎn)得最短距離，如此循環(huán)，直到再回到起點(diǎn)，可得到環(huán)路最短路徑，最后所得即為T(mén)P問(wèn)題所求解。

6、本課題的進(jìn)度安排(期間將去公司實(shí)習(xí)所以時(shí)間還是偏緊)：
本課題計(jì)劃分為三部分：

第一部分
2012-2-15——2012-2-28(13天)：主要進(jìn)行課題的材料收集和課題的前期研究，期間將完成開(kāi)題報(bào)告；
第二部分
2012-3-1——2012-3-20（20天）：主要學(xué)習(xí)和研究并選擇一種算法實(shí)現(xiàn)簡(jiǎn)單多邊形的三角剖分（該部分由于有另一個(gè)獨(dú)立課題所以不做深入的研究，然而這又是本課題的基礎(chǔ)所以也不得不多花點(diǎn)時(shí)間學(xué)習(xí)）；
2012-3-20——2012-4-05（15天）：主要學(xué)習(xí)和研究并實(shí)現(xiàn)樹(shù)上最短路算法；
2012-4-05——2012-4-30（25天）：主要學(xué)習(xí)研究和實(shí)現(xiàn)點(diǎn)-線-點(diǎn)問(wèn)題中兩點(diǎn)最短距離的求解及最終TP問(wèn)題的求解（最終TP問(wèn)題的求解實(shí)現(xiàn)以否和實(shí)現(xiàn)效果好壞將依時(shí)間而定），這是本課題中最重要的部分，所以講花比較大的篇幅。（期間有中期檢查，將對(duì)中期檢查的意見(jiàn)進(jìn)行相應(yīng)的整理）

第三部分
2012-5-01——答辯：將整理課題設(shè)計(jì)成果并進(jìn)行畢業(yè)論文材料的收集整理和撰寫(xiě)，完成畢業(yè)答辯。














7、參考文獻(xiàn)：
1．徐春蕾．李思昆．一種適用任意平面多邊形的三角剖分算法[J]．國(guó)防科技大學(xué)．2000．（02）．
2．馬小虎．潘志庚．石教英．基于凹凸頂點(diǎn)判定的簡(jiǎn)單多邊形Delaunay三 ……（未完，全文共3878字，當(dāng)前僅顯示1958字，請(qǐng)閱讀下面提示信息。收藏《論文開(kāi)題：實(shí)施并改進(jìn)旅行問(wèn)題算法》）