論文開題：實施并改進旅行問題算法

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

課題名稱 實施并改進旅行問題算法

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

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

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


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

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

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

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

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

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














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