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

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

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

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

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

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


4、擬解決的關鍵問題：

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

5、研究思路、方法和步驟：
為了解決TP問題，本課題將引入了點-邊-點的最短路徑的思路（該知識點李發(fā)捷老師做過相關研究），提出基于三角剖分的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）算法對完整樹進行剪枝，得到一棵目標樹。所求解的旅行問題的最短路徑必經(jīng)過該目標樹的所有樹邊；
4.到這里問題將轉(zhuǎn)化為已知起(終)點，有序的經(jīng)過目標樹上所給的線段。本課題將采用橡皮筋算法（Rubber Band Algorithm，RBA），通過不斷調(diào)整點與線段，點與點之間的距離，循環(huán)比較每次運算得到的路徑距離，最后得到簡單多邊形內(nèi)任意聯(lián)系兩點間的最短路徑，即兩個帳篷間的最短路徑。
5.以步驟4中的終點為起點，重復步驟4，即可得到到下一個終點得最短距離，如此循環(huán)，直到再回到起點，可得到環(huán)路最短路徑，最后所得即為TP問題所求解。

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

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

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














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