1、旅行商問(wèn)題摘要的目的：旅行商問(wèn)題是數(shù)學(xué)領(lǐng)域的著名問(wèn)題之一，是最基本的路線問(wèn)題，該問(wèn)題是在尋求單一旅行者由起點(diǎn)出發(fā)，通過(guò)所有給定的需求點(diǎn)之后，最后再回到原點(diǎn)的最小路徑成本。的意義：旅行商問(wèn)題是組合優(yōu)化領(lǐng)域里的一個(gè)典型的、易于描述卻難以求解的 NP 完全難題，其可能的路徑數(shù)目與城市數(shù)目呈現(xiàn)指數(shù)增長(zhǎng)，求解非常，而快速、有效地解決TSP 有著重要的理論價(jià)值和極高的使用價(jià)值，由于該問(wèn)題在現(xiàn)實(shí)生活中應(yīng)用廣泛，所以其現(xiàn)實(shí)應(yīng)用也具有相當(dāng)?shù)囊饬x。的方法：選擇一種算法不斷優(yōu)化解決小規(guī)模的旅行商問(wèn)題。的內(nèi)容：本實(shí)驗(yàn)中用 Or-opt 算法求解旅行商問(wèn)題。的結(jié)果：成功解決小規(guī)模旅行商問(wèn)題。主要結(jié)論：Or-opt 算法

2、可以控制求解的迭代次數(shù)，但不一定求得最優(yōu)解。：Or-opt 算法，結(jié)合，可控，局部最優(yōu)目錄摘要1第一章實(shí)驗(yàn)介紹11.1實(shí)驗(yàn)?zāi)康募皟?nèi)容11.2實(shí)驗(yàn)原理. 11.3實(shí)驗(yàn)環(huán)境. 11.4實(shí)驗(yàn)要求. 1第二章實(shí)驗(yàn)成果及分析12.1算法12.1.1城市數(shù)據(jù)22.1.2轉(zhuǎn)化為距離矩陣22.1.3Or-opt 算法求路徑32.2實(shí)驗(yàn)結(jié)果52.3結(jié)果分析6第三章總結(jié)63.1 實(shí)驗(yàn)心得63.2 實(shí)驗(yàn)意義7參考資料7第一章實(shí)驗(yàn)介紹1.1實(shí)驗(yàn)?zāi)康募皟?nèi)容探究旅行商問(wèn)題。旅行商問(wèn)題，常被稱為旅行問(wèn)題，是指一名要拜訪多個(gè)地點(diǎn)時(shí)，如何找到在拜訪每個(gè)地點(diǎn)一次后再回到起點(diǎn)的最短路徑。1.2實(shí)驗(yàn)原理Or-opt 算法是一種途程改

3、善法，先給定一個(gè)可行途程，然后進(jìn)行改善，一直到不能改善為止。在相同路徑上相鄰的需求點(diǎn)，將之和本身或其它路徑交換且仍保持路徑方向性，并計(jì)算其成本（或距離），如果成本降低（距離減少），則取代之，直到無(wú)法改善為止。1.3實(shí)驗(yàn)環(huán)境Visual C+6.0、Windows 操作系統(tǒng)1.4實(shí)驗(yàn)要求編寫(xiě) Or-opt 算法的實(shí)現(xiàn)程序，能夠快速求出旅行商問(wèn)題的近似優(yōu)解。第二章實(shí)驗(yàn)成果及分析2.1算法2.1.1城市數(shù)據(jù)if(fp=fopen(城市坐標(biāo).txt,r)=NULL)prf(打開(kāi)文件失敗n);exit(0);/城市的坐標(biāo)while(!feof(fp)fscanf(fp,%d %d %dn,&num,&x

4、,&y);c_numi=num;c_xi=x;c_yi=y;i+;2.1.2轉(zhuǎn)化為距離矩陣for(i=0;inc;i+)for(j=0;jnc;j+)disij=sqrt(c_xi-c_xj)*(c_xi-c_xj)+(c_yi-c_yj)*(c_yi-c_yj);prf(距離矩陣為：n);for(i=0;inc;i+)for(j=0;jnc;j+)prf(%3.4ft,disij);prf(n);2.1.3Or-opt 算法求路徑prf(假定初始路徑為：);p=1;for(i=0;inc;i+)prf(%d ,pathi=p+);prf(n);rh=path0;for(i=0;inc*nc;

5、i+)/每 3 條連續(xù)路徑為一組，交換中間兩點(diǎn)，作比較決定是否交換位置if(dispath0-1path2-1+dispath1-1path3-1dispath0-1path1-1+dispath2-1path3-1)p=path1;path1=path2;path2=p;n=path0;for(j=0;jnc-1;j+)/每操作一次，前移整體數(shù)據(jù)，第一個(gè)數(shù)據(jù)傳給最后一個(gè)，避免了循環(huán)時(shí)數(shù)據(jù)不pathj=pathj+1;/比如 1,2,3,4 和 8,9,1,2 需要分開(kāi)，運(yùn)行效率會(huì)降低pathnc-1=n;distance=0.0;/總距離計(jì)算for(i=0;inc-1;i+)distance

6、+=dispathi-1pathi+1-1;distance+=dispathnc-1-1path0-1;prf(總距離為%3.4f ,distance);2.2實(shí)驗(yàn)結(jié)果顯示的數(shù)據(jù)、轉(zhuǎn)化的距離矩陣、初始設(shè)定路徑、優(yōu)化后的路徑和總距離2.3結(jié)果分析Or-opt 算法在對(duì)途程結(jié)構(gòu)改善時(shí)，總是做出在當(dāng)下比較的兩條路徑中更好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，僅追求局部最優(yōu)解，所以程序求得的并不是最優(yōu)解。單就本程序而言，算法是正確的，輸入和輸出基本符合我對(duì)該程序的預(yù)估。重點(diǎn)是這種算法是可以控制迭代次數(shù)的，也就是說(shuō)每次的迭代可以說(shuō)是都有效，所以效率很高，中規(guī)模的數(shù)據(jù)都能快速求解。問(wèn)題：1.在處理大

7、量城市的旅行商問(wèn)題時(shí)或者更難求得更優(yōu)解。2.該算法與其他算法在旅行商問(wèn)題求解時(shí)所得的不夠穩(wěn)定。3.初始路程選擇很重要，但因?yàn)槭请S機(jī)性的，所以會(huì)給尋找最優(yōu)解帶來(lái)。建議：應(yīng)該將貪心算法與其結(jié)合，在尋找較優(yōu)解后，再運(yùn)用途程改善的算法能更接近最優(yōu)解。第三章總結(jié)3.1實(shí)驗(yàn)心得經(jīng)過(guò)了這次的實(shí)驗(yàn)，我更深入理解了貪心算法和途程改善法的區(qū)別，知道了各自的利弊。我一直堅(jiān)信貪心算法不一定求得最優(yōu)解，而途程改善法可以彌補(bǔ)這個(gè)缺陷，但是實(shí)驗(yàn)結(jié)論發(fā)現(xiàn)只有將多種算法正確地結(jié)合才能求得更優(yōu)解。必須學(xué)會(huì)，剛開(kāi)始我對(duì) Or-opt 算法完全陌生，我是在找有關(guān)旅行商問(wèn)題資料的過(guò)發(fā)現(xiàn)這個(gè)算法，所以為了理解該算法我找了很多的資料。數(shù)學(xué)很重要，最后理解該算法是把它看成一個(gè)數(shù)學(xué)問(wèn)題來(lái)求證，最終通過(guò)自己的不斷思考、實(shí)驗(yàn)和證明找到了最簡(jiǎn)單易懂可控的算法。3.2實(shí)驗(yàn)意義在尋找與選擇的方法相應(yīng)的較優(yōu)算法過(guò)進(jìn)一步了解了旅行商問(wèn)題的本質(zhì)，更加深刻明