最小生成樹在旅游路線選擇中的應(yīng)用

編號(hào)：審定成績：重慶郵電大學(xué)研究生堂下考試答卷2013-2014學(xué)年第1學(xué)期論文題目：最小生成樹在旅游路線選擇中的應(yīng)用學(xué)院名稱：學(xué)生姓名：專業(yè)：學(xué)號(hào)：指導(dǎo)教師：重慶郵電大學(xué)教務(wù)處制摘要隨著生活節(jié)奏的加快，人民生活水平的提高，人們?cè)絹碓綗嶂杂谒奶幝糜危瑫r(shí)，大家也不愿意將大局部的時(shí)間花費(fèi)在路途上，人們旅游目的在于放松、賞景、游玩，旅游公司就不得不根據(jù)游客要求做出相應(yīng)的旅游路線安排。很多旅游景點(diǎn)之間都相隔一定的距離，那么如何在眾多旅游景點(diǎn)路線中選擇最近的一條呢？因此，如何做到即保證游覽各個(gè)景點(diǎn)又確保路途最近地從眾多可行路線中選出最優(yōu)路線成為了解決此問題的關(guān)鍵。圖論最小生成樹理論常用于交通線路選擇中，本文將其運(yùn)用于旅游交通優(yōu)化與線路組織上，即在賦權(quán)圖中找出一顆最優(yōu)樹，以滿足以最短路徑最小連接各旅游目的城市和最小的建設(shè)本錢。我們所學(xué)《圖論及其算法》教材中介紹了其中的三種算法Prim算法、Kruskal算法和破圈法。本文涉及的抽象圖形結(jié)構(gòu)較為簡單，使用各類算法的差異在此并無明顯表達(dá)，一般來說，Kruskal算法應(yīng)用較為普遍，因此本文采用Kruskal算法實(shí)現(xiàn)最優(yōu)路徑求取。文中通過一個(gè)例子應(yīng)用，將最小生成樹的Kruskal算法實(shí)際化，通過算法步驟分析，以及在VC++6.0中程序的運(yùn)行，最終求出的最小生成樹與實(shí)際相符，該算法思想成立，并具有一般性，能夠增刪節(jié)點(diǎn)、修改權(quán)值，也可運(yùn)用到其他問題的解決中。關(guān)鍵詞：旅游路線問題Kruskal算法最優(yōu)路線最小生成樹一、引言旅游交通是為旅游者由客源地到旅游目的地的往返，以及在旅游目的地各處旅游活動(dòng)而提供的交通設(shè)施及效勞，其便利程度，是衡量旅游業(yè)興旺程度的重要標(biāo)志。與一般交通不同，旅游交通過程本身也是旅游體驗(yàn)過程，對(duì)于游客來說，立足于最小的時(shí)間與經(jīng)濟(jì)本錢獲得最多的旅游體驗(yàn)，對(duì)于旅游組織者來說，那么立足于最小的建設(shè)本錢與最大的社會(huì)、經(jīng)濟(jì)、生態(tài)效益。道路是交通的載體，具有高度通達(dá)性、完善的旅游效勞功能和景觀化、生態(tài)化、人性化的道路是區(qū)域旅游交通完善的重要標(biāo)志，基于此，有學(xué)者提出“風(fēng)景道”、“旅游交通干道”等規(guī)劃建設(shè)理念與原那么。其中，旅游交通系統(tǒng)的優(yōu)化很大程度取決于合理的道路布局，而如何使道路通達(dá)性與建設(shè)本錢之間獲得平衡，到達(dá)性價(jià)比最優(yōu)，成為道路系統(tǒng)優(yōu)化的重要指標(biāo)。因此，其實(shí)質(zhì)上可以簡化為最短距離連接各旅游目的地最優(yōu)解問題[1]。旅游路線組織是旅游地理學(xué)研究的重要內(nèi)容，其研究主要以游客的行為空間模式為導(dǎo)向，旅游路線是旅游產(chǎn)品的組成局部，作為產(chǎn)品就必須滿足游客的需求，因此游客的行為模式就成為旅游路線設(shè)計(jì)的重要依據(jù)。二、背景知識(shí)圖和樹圖論中的圖是由假設(shè)干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形通常用來描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間具有這種關(guān)系。樹是無圈連通無向圖，如果樹T的節(jié)點(diǎn)數(shù)為n，那么樹的邊數(shù)為n-1。生成樹連通圖G上的一個(gè)子圖，該子圖連通，無回路且包含圖G的所有節(jié)點(diǎn)，稱為連通圖的極小連通子圖。一個(gè)連通圖可以有多棵不同的生成樹。最小生成樹對(duì)一個(gè)帶權(quán)連通圖，也有多可不同的生成樹。由于該圖是帶權(quán)圖，各邊的權(quán)值不一定相等，因此這些生成樹的各邊權(quán)值之和也不一定相同，其中權(quán)值最小的生成樹被稱為該帶權(quán)連通圖的最小生成樹[4]。三、最小生成樹的求解方法構(gòu)造最小生成樹可以有多種算法。我們所學(xué)《圖論及其算法》教材中介紹了其中的三種算法Prim算法、Kruskal算法和破圈法，本文分別用這三種算法來實(shí)現(xiàn)最小生成樹的構(gòu)造。1、Prim算法算法思想：普里姆算法通過逐個(gè)往生成樹上添加頂點(diǎn)來構(gòu)造連通網(wǎng)的最小生成樹。算法具體步驟：〔1〕開始：選取連通網(wǎng)中的任意一個(gè)頂點(diǎn)添加到最小生成樹中?！?〕重復(fù)執(zhí)行以下操作：連通網(wǎng)的頂點(diǎn)集合分成兩個(gè)局部：已經(jīng)添加到最小生成樹中的頂點(diǎn)集合和尚未添加到最小生成樹中的頂點(diǎn)集合；找出所有連通這兩個(gè)集合中頂點(diǎn)的邊；從中選取一條權(quán)值最小的邊添加到生成樹中，同時(shí)將與這條邊相連的頂點(diǎn)也添加到生成樹中?！?〕結(jié)束：所有的頂點(diǎn)都被添加到最小生成樹中。2、Kruskal算法算法思想：通過逐個(gè)往生成樹上添加邊來構(gòu)造連通網(wǎng)的最小生成樹。算法具體步驟：〔1〕將連通網(wǎng)中的所有頂點(diǎn)添加到最小生成樹中，構(gòu)造一個(gè)森林；〔2〕將各邊按照權(quán)值從小到大排序；〔3〕按照排好的順序向生成樹中添加不使森林中產(chǎn)生回路的邊(假設(shè)構(gòu)成回路那么不添加，繼續(xù)考察下一條邊)。直至該森林變成一棵樹為止。3、破圈法算法思想：通過逐個(gè)從連通網(wǎng)中刪除邊來構(gòu)造最小生成樹。算法具體步驟：〔1〕將連通網(wǎng)中各邊按照權(quán)值從大到小排序；〔2〕按照排好的順序從連通網(wǎng)中刪除權(quán)值最大的邊，條件是使刪除該邊后的子圖仍然保持連通(假設(shè)刪除后子圖不連通那么改邊保存，繼續(xù)刪除下一條邊)。直至子圖中任何一條邊都不能刪除〔即刪除任意一條邊都會(huì)造成該子圖不連通〕為止。4、三種算法的比擬〔1〕普里姆算法：主要是對(duì)頂點(diǎn)進(jìn)行操作；采用鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)，在行過程中對(duì)連通網(wǎng)中的每一個(gè)頂點(diǎn)都考察到了。普里姆算法適用于求邊稠密的連通網(wǎng)的最小生成樹?！?〕克魯斯卡爾算法：主要是對(duì)邊進(jìn)行操作，時(shí)間復(fù)雜度主要取決于對(duì)邊按照權(quán)值進(jìn)行排序的時(shí)間，邊的個(gè)數(shù)為e，排序的時(shí)間復(fù)雜度可以做到O(eloge)，因此算法的時(shí)間復(fù)雜度為O(eloge)?？唆斔箍査惴ㄟm用于求邊稀疏的連通網(wǎng)的最小生成樹?！?〕破圈法：主要是對(duì)邊進(jìn)行操作，時(shí)間復(fù)雜度主要取決于對(duì)邊按照權(quán)值進(jìn)行排序的時(shí)間，邊的個(gè)數(shù)為e，排序的時(shí)間復(fù)雜度可以做到O(eloge)，因此算法的時(shí)間復(fù)雜度為O(eloge)。該算法適用于求邊稀疏的連通網(wǎng)的最小生成樹[5]。四、應(yīng)用利用最小生成樹來解決旅游路線問題，將旅游路線問題中的旅游景點(diǎn)看做圖中的頂點(diǎn)，各個(gè)景點(diǎn)之間的路線看做圖中頂點(diǎn)之間的邊，景點(diǎn)之間路線的長度看做圖中各邊上的權(quán)值。這樣，我們就把旅游路線問題轉(zhuǎn)換成了求一個(gè)有向連通網(wǎng)的最小生成樹問題。此時(shí)，假設(shè)景點(diǎn)個(gè)數(shù)為6，分別為v1,v2,v3,v4,v5,v6。并設(shè)其對(duì)應(yīng)景點(diǎn)之間的路線距離權(quán)值及初始狀態(tài)的連通加權(quán)無向圖如下列圖所示。邊(1,2〕(1,3〕(1,4〕(2,3)(2,6)(3,4)(3,5)(3,6)(4,5)(5,6)權(quán)值6197356426以下是用Kruskal算法求解最小生成樹〔1〕實(shí)現(xiàn)步驟：根據(jù)前文介紹的Kruskal算法步驟依次添加邊〔1,3〕,〔4,5〕,〔2,6〕,〔3,6〕,〔3,4〕，并依次添加對(duì)應(yīng)節(jié)點(diǎn)，各個(gè)步驟結(jié)果如下列圖：第一步第二步第三步第四步第五步〔2〕仿真及結(jié)果分析在vc++6.0環(huán)境下，首先輸入圖的頂點(diǎn)數(shù)和邊數(shù)，然后輸入第一條邊的起始點(diǎn)和終點(diǎn)，以及這條邊的權(quán)值，直到輸完為止自動(dòng)將權(quán)從小到大排序，并且得出最小生成樹，如下列圖運(yùn)行結(jié)果所示。五、總結(jié)本文首先將實(shí)際的旅游路線選擇問題轉(zhuǎn)化成了圖論的最小生成樹問題，然后選用Kruskal算法編寫相應(yīng)的C語言程序最終實(shí)現(xiàn)。這樣一方面可以得到一條最有效的路線，使得路途欣賞性和時(shí)間效率都得到提高，另一方面還可以增加景點(diǎn)〔頂點(diǎn)數(shù)〕，改變邊的權(quán)值〔景點(diǎn)之間的距離〕等等，具有靈活、準(zhǔn)確、簡便等特點(diǎn)，由于它的一般性，不僅僅解決了旅游路線選擇的問題，同時(shí)還適用于其他問題的解決。參考文獻(xiàn)[1]鮑捷.基于最小生成樹Kruskal算法的皖北地區(qū)旅游交通優(yōu)化與線路組織[J].人文地理.2010,03.[2]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)〔C語言版〕[M].北京：清華大學(xué)出版社，2003，11.[3]譚浩強(qiáng).C程序設(shè)計(jì)〔第三版〕[M].北京：清華大學(xué)出版社，2005.[4]殷劍宏，吳開亞.圖論及其算法[M].北京：中國科學(xué)技術(shù)大學(xué)出版社，2006[5]李曉莉，王發(fā)曾，羅軍.中原城市群軌道交通干線選擇研究[J].2008,10附錄Kruskal算法程序：#include<stdio.h>#include<stdlib.h>#defineM20#defineMAX20typedefstruct//構(gòu)造邊{intbegin;intend;intweight;//權(quán)值}edge;typedefstruct{intadj;intweight;}AdjMatrix[MAX][MAX];typedefstruct{AdjMatrixarc;intvexnum,arcnum;//頂點(diǎn)數(shù)和邊數(shù)}MGraph;voidCreatGraph(MGraph*);//函數(shù)申明構(gòu)造圖voidsort(edge*,MGraph*);//函數(shù)申明對(duì)邊的排序voidMiniSpanTree(MGraph*);//最小生成樹intFind(int*,int); voidSwapn(edge*,int,int);//交換兩條邊的權(quán)值和它們的起點(diǎn)和終點(diǎn)voidCreatGraph(MGraph*G)//構(gòu)件圖G{inti,j,n,m;printf("請(qǐng)輸入圖的頂點(diǎn)數(shù)和邊數(shù):");scanf("%d%d",&G->vexnum,&G->arcnum);for(i=1;i<=G->vexnum;i++)//初始化圖{ for(j=1;j<=G->vexnum;j++){G->arc[i][j].adj=G->arc[j][i].adj=0;}} for(i=1;i<=G->arcnum;i++)//輸入邊和權(quán)值{printf("\n請(qǐng)輸入邊的起始點(diǎn)和終點(diǎn):");scanf("%d%d",&n,&m);while(n<0||n>G->vexnum||m<0||m>G->vexnum){printf("\n");printf("\n");printf("輸入的數(shù)字不符合要求請(qǐng)重新輸入:");scanf("%d%d",&n,&m);}G->arc[n][m].adj=G->arc[m][n].adj=1;getchar();printf("\n請(qǐng)輸入%d與%d之間的權(quán)值:",n,m);scanf("%d",&G->arc[n][m].weight);//輸入權(quán)值}}voidsort(edgeedges[],MGraph*G)//對(duì)權(quán)值進(jìn)行排序{inti,j;for(i=1;i<G->arcnum;i++){for(j=i+1;j<=G->arcnum;j++){if(edges[i].weight>edges[j].weight){Swapn(edges,i,j);}}}printf("\n");printf("\n");printf("\n");printf("權(quán)從小到大排序之后為:\n");printf("◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆\n");printf("起點(diǎn)終點(diǎn)權(quán)\n");for(i=1;i<=G->arcnum;i++){printf("<<%d%d>>%d\n",edges[i].begin,edges[i].end,edges[i].weight);}}voidSwapn(edge*edges,inti,intj)//交換權(quán)值以及頭和尾{inttemp;temp=edges[i].begin;edges[i].begin=edges[j].begin;edges[j].begin=temp;temp=edges[i].end;edges[i].end=edges[j].end;edges[j].end=temp;temp=edges[i].weight;edges[i].weight=edges[j].weight;edges[j].weight=temp;}voidMiniSpanTree(MGraph*G)//生成最小生成樹{inti,j,n,m;intk=1;intparent[M];edgeedges[M];for(i=1;i<G->vexnum;i++){for(j=i+1;j<=G->vexnum;j++){if(G->arc[i][j].adj==1){edges[k].begin=i;edges[k].end=j;edges[k].weight=G->arc[i][j].weight;k++;}}}sort(edges,G);for(i=1;i<=G->arcnum;i++){parent[i]=0;}printf("◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆\n"); printf("\n"); printf("\n"); printf("\n");printf("最