淺議旅行商問題的求解

本文共計(jì)24頁，8592字；

摘 要

旅行商問題(TSP問題)就是一銷售商從n個(gè)城市中的某一城市出發(fā)，不重復(fù)地走完其余n-1個(gè)城市并回到原出發(fā)點(diǎn)，在所有可能的路徑中求出路徑長(zhǎng)度最短的一條。它是組合優(yōu)化中研究最多的問題之一，是一個(gè)經(jīng)典的NP難題。吸引了許多不同領(lǐng)域的研究工作者，包括數(shù)學(xué)、運(yùn)籌學(xué)、物理、生物和人工智能等領(lǐng)域，它是目前優(yōu)化領(lǐng)域里的研究熱點(diǎn)。
目前解決旅行商問題有諸多算法，神經(jīng)網(wǎng)絡(luò)、遺傳算法、免疫算法等，在各種解決旅行商問題的算法中，還是存在很多問題。
本次設(shè)計(jì)嘗試使用最小生成樹來求解旅行商問題。在對(duì)題目要求進(jìn)行深入分析的基礎(chǔ)上，對(duì)原有算法進(jìn)行了多方面改進(jìn)，并用C語言進(jìn)行了實(shí)現(xiàn)。采用選取排除最長(zhǎng)路徑頂點(diǎn)的方法降低時(shí)間復(fù)雜度、采用比較頂點(diǎn)次序的方法提高算法準(zhǔn)確性，通過自動(dòng)產(chǎn)生頂點(diǎn)坐標(biāo)降低輸入復(fù)雜性和測(cè)試的準(zhǔn)確性，實(shí)驗(yàn)結(jié)果表明該算法可以取得較好的效果。

關(guān)鍵詞：TSP,最小生成樹,最短路徑,組合優(yōu)化
ABSTRACT
Traveling Sale-man Problem (TSP) means a sale-man starts from a city among n city, and passes by every city and return the origin non-repeatedly. From all the routes the shortest is selected and is adopted as the solve. TSP is the most important problem in the combined optimization area, and a NP-hard problem. It has already attracted many researchers from all areas, including mathematics, operational research, physics, biology, and artificial intelligence, at the same time, it is a hotspot in the current optimization area.
目 錄
摘要…………………………………………………………………………………………………………………..3
ABSTRACT……………………………………………………………………………………………………3
一． 引言………………………………………………………………………………………...4
1． 背景介紹…………………………………………………………………………..4
2． 存在主要問題…………………………………………………………………..4
3． 本文主要內(nèi)容…………………………………………………………………..4
二. 設(shè)計(jì)分析……………………………………………..………………………….………5
1設(shè)計(jì)題目……………………………………………..………………………….………5
(1)題目要求……………………………………..…..………………………….……….5
(2)題目分析…………………………………………………………………….……….5
2輸入分析………………………………………………………………………………..5
3查找路徑……………………………………………………………………………..…5
（1）最小生成樹……………………………………………………………………….5
（2）求解最小生成樹………………………………………………………………...6
（3） TSP路徑查找…………………………………………………………………..7
4輸出分析………………………………………………………………………………..7
三. 算法設(shè)計(jì)………………………………………………………………………………..8
1輸入設(shè)計(jì)…………………………………………………………………………………8
2 TSP路徑查找設(shè)計(jì)…………………………………………………………………9
3輸出設(shè)計(jì)………………………………………………………………….……………..9
四. 算法改進(jìn)……………………………………………………………………………....11
1降低時(shí)間復(fù)雜度………………………………………………………....…………11
2提高算法準(zhǔn)確性…………………………………………………………….…...…11
3降低輸入復(fù)雜性…………………………………………………………….……...12
五. 結(jié)束語……………………………………………………………….………….…..…..13
致謝………………………….………………………………………………………….……..…13
參考文獻(xiàn)…………………………………………………………………………….……...…13
附錄1 源程序代碼……………………………………………………………………..14
附錄2 運(yùn)行實(shí)例……………………………………………………………….………...22
參考文獻(xiàn)

1. 譚浩強(qiáng)，C語言程序設(shè)計(jì)（第二版）， 清華大學(xué)出版社,1998.5

2. 張基溫, C/C++程序設(shè)計(jì)教程, 高等教育出版社,1997.4

3. 吳偉民, 數(shù)據(jù)結(jié)構(gòu)（C語言版）, 清華大學(xué)出版社,2000.5

4. 靳蕃, 神經(jīng)網(wǎng)絡(luò)與神經(jīng)計(jì)算機(jī)（原理與應(yīng)用） ,西南交通大學(xué)出版社,1999.6