基于floyd算法的旅游線路優(yōu)化設(shè)計(jì)

基于floyd算法的旅游線路優(yōu)化設(shè)計(jì)

根據(jù)地圖，游客應(yīng)該從發(fā)達(dá)地區(qū)到目的地的距離最短，并節(jié)省成本和時(shí)間。例如游客選取甘肅省及周邊地區(qū)13個(gè)旅游景點(diǎn),旅游地圖如圖一所示,通過(guò)上網(wǎng)收集到各個(gè)旅游景點(diǎn)之間的距離如表一所示。在表一中,0表示蘭州火車站,1—13分別表示甘肅省及周邊旅游景點(diǎn)興隆山、嘉峪關(guān)文物景區(qū)、拉卜楞寺、崆峒山、雷臺(tái)、大佛寺、敦煌、黃河石林、貴清山、青海湖鳥島景區(qū)、塔爾寺、沙坡頭、麥積山?！薇硎具@兩個(gè)旅游景點(diǎn)之間沒(méi)有直接到達(dá)的交通線路。如何求出任意兩點(diǎn)之間的最短距離以及最短路對(duì)旅客來(lái)說(shuō)顯得尤為重要,比如游客想從蘭州火車站出發(fā),前往敦煌鳴沙山月牙泉旅游,如何選擇旅游線路的問(wèn)題。再比如游客在旅行途中必須去拉卜楞寺和嘉峪關(guān)觀光,即選定兩個(gè)旅游景點(diǎn)后到達(dá)目的地的旅行線路設(shè)計(jì)。將旅游景點(diǎn)看成圖中的頂點(diǎn),各個(gè)景點(diǎn)的交通路線可看成圖上的邊,邊上的權(quán)重代表從一個(gè)景點(diǎn)到另一個(gè)景點(diǎn)的距離或者時(shí)間或者費(fèi)用。上面的問(wèn)題都可以利用圖論中最短路問(wèn)題解決。在給定的賦權(quán)圖G中,求兩個(gè)互異頂點(diǎn)間的最短路徑稱之為最短路問(wèn)題。最短路問(wèn)題是重要的最優(yōu)化問(wèn)題之一,也是圖論研究中的一個(gè)經(jīng)典算法問(wèn)題。最短路問(wèn)題的應(yīng)用背景十分廣泛,本文將最短路問(wèn)題應(yīng)用到旅游線路設(shè)計(jì)中具有很大實(shí)用價(jià)值。歸納起來(lái),最短路問(wèn)題一般歸為兩類:一類是求從某個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路徑;另一類是求圖中每一對(duì)頂點(diǎn)間的最短路徑。關(guān)于最短路的研究,目前已經(jīng)有很多算法,但是基本上是以Dijkstra和Floyd兩種算法為基礎(chǔ),本文利用Floyd算法研究了最短路問(wèn)題在旅游線路優(yōu)化中的應(yīng)用。1通過(guò)計(jì)算兩個(gè)旅游目的地之間最短的floyd算法和nb1.1以dkj為中心的vk和到頂vj的最距離設(shè)圖G=(V,E),頂點(diǎn)集記作{v1,v2,…,vn},G的每條邊賦有一個(gè)權(quán)值,ωij表示邊vivj上的權(quán),若vi、vj不相鄰,則令ωij=+∞。Floyd算法利用了動(dòng)態(tài)規(guī)劃的基本思想,即若dik是頂點(diǎn)vi到vk的最短距離,dkj是頂點(diǎn)vk到頂點(diǎn)vj的最短距離,則dij=dik+dkj是頂點(diǎn)vi到頂點(diǎn)vj的最短距離。對(duì)于任何一個(gè)頂點(diǎn)vk∈V,頂點(diǎn)vi到頂點(diǎn)vj的最短距離經(jīng)過(guò)vk或者不經(jīng)過(guò)vk。比較dij和dik+dkj的值,若dij>dik+dkj,則令dij=dik+dkj,保持dij是當(dāng)前搜索的頂點(diǎn)vi到頂點(diǎn)vj的最短距離。重復(fù)這一過(guò)程,最后搜索完所有的頂點(diǎn)時(shí),就是頂點(diǎn)到頂點(diǎn)的最短距離。Floyd算法的基本步驟如下:步驟1:輸入加權(quán)圖,存儲(chǔ)在矩陣W。對(duì)于所有的i、j,有dij=ωij,k=1。步驟2:更新dij,對(duì)所有的i、j,若dij>dik+dkj,則令dij=dik+dkj。步驟3:若dij<0,則存在一條含有頂點(diǎn)vi的負(fù)回路,停止;或者k=n停止;否則跳轉(zhuǎn)到步驟2。1.2最短距離floyd算法的nb1.3線路運(yùn)行matlab程序求蘭州火車站到麥積山的旅游最短距離和最短路。運(yùn)行Matlab程序:即從蘭州火車站到麥積山的旅游最短路是蘭州火車站到興隆山到麥積山,最短距離是350公里2任意最短路的求法在旅游過(guò)程中經(jīng)常會(huì)遇到這樣的問(wèn)題:倘若在任意旅游景點(diǎn),想知道下一任意旅游景點(diǎn)的最短路。這就是圖中任意兩頂點(diǎn)最短路的求法。求任意兩頂點(diǎn)最短路的算法思想是利用Floyd算法思想,首先求得最短距離矩陣,然后求任意給定兩個(gè)頂點(diǎn)間的最短路包含的頂點(diǎn)。2.1算法與b段2.2到麥積山和拉卜傳統(tǒng)從6公里到5.5公里分別求出敦煌鳴沙山月牙泉風(fēng)景區(qū)到麥積山拉卜楞寺到沙坡頭的最短距離和最短路。運(yùn)行Matlab程序得到敦煌鳴沙山月牙泉到麥積山的最短路為:敦煌鳴沙山月牙泉→青海湖→塔爾寺→(蘭州火車站)→興隆山→麥積山,最短距離為1042公里;拉卜楞寺到沙坡頭的最短路為:拉卜楞寺→(蘭州火車站)→黃河石林→沙坡頭,最短距離是556公里。假設(shè)外地游客來(lái)蘭州,他在蘭州火車站看到蘭州旅游地圖,想知道從蘭州火車站到其他13個(gè)旅游景點(diǎn)的最短距離和最短路,同樣可以由上面敘述的方法獲得。3指定點(diǎn)的最短距離算法及其變量的實(shí)現(xiàn)當(dāng)旅行者在旅游過(guò)程中務(wù)必經(jīng)過(guò)指定的兩個(gè)旅游景點(diǎn)時(shí),旅游最短路設(shè)計(jì)等價(jià)于指定圖兩頂點(diǎn)的最短路求法。3.1計(jì)算以最短路的提供道路由起始點(diǎn)k1到終點(diǎn)k2,經(jīng)過(guò)指定的頂點(diǎn)t1、t2的最短路經(jīng)過(guò)四個(gè)頂點(diǎn)的順序只能有兩種情況k1→t1→t2→k2或者k2→t2→t1→k1。若要滿足所求得的路是從始點(diǎn)k1到達(dá)終點(diǎn)k2的最短路,則在四個(gè)頂點(diǎn)中經(jīng)過(guò)相鄰頂點(diǎn)之間的路一定是最短路,故只需分別計(jì)算頂點(diǎn)k1→t1,t1→t2,t2→k2和k1→t2,t2→t,t1→k2之間的最短路;然后把前面三者的距離加起來(lái)得到d1,把后三個(gè)加起來(lái)得到d2;比較d1和d2的值,誰(shuí)小則能作為始點(diǎn)k1到終點(diǎn)k2經(jīng)過(guò)指定的頂點(diǎn)t1、t2的最短路。3.2算法與b段3.3floyd算法在旅游線路設(shè)計(jì)中的應(yīng)用假設(shè)游客從蘭州火車站出發(fā)前往敦煌鳴沙山月牙泉旅行,途中必須經(jīng)過(guò)拉卜楞寺和嘉峪關(guān)文物景區(qū),怎么設(shè)計(jì)旅游線路使旅行線路最短。運(yùn)行上述Matlab程序得到最短路為:蘭州火車站→拉卜楞寺→塔爾寺大佛寺→嘉峪關(guān)文物景區(qū)→敦煌鳴沙山月牙泉;