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

1、 編 號： 審定成績： 重慶郵電大學(xué)研究生堂下考試答卷2013-2014學(xué)年第 1 學(xué)期論文題目：最小生成樹在旅游路線選擇中的應(yīng)用學(xué) 院 名 稱 ：學(xué) 生 姓 名 ：專 業(yè) ：學(xué) 號 ： 指 導(dǎo) 教 師 ： 重慶郵電大學(xué)教務(wù)處制摘 要隨著生活節(jié)奏的加快，人民生活水平的提高，人們越來越熱衷于四處旅游，同時，大家也不愿意將大部分的時間花費(fèi)在路途上，人們旅游目的在于放松、賞景、游玩，旅游公司就不得不根據(jù)游客要求做出相應(yīng)的旅游路線安排。很多旅游景點(diǎn)之間都相隔一定的距離，那么如何在眾多旅游景點(diǎn)路線中選擇最近的一條呢？因此，如何做到即保證游覽各個景點(diǎn)又確保路途最近地從眾多可行路線中選出最優(yōu)路線成為了解決此

2、問題的關(guān)鍵。圖論最小生成樹理論常用于交通線路選擇中，本文將其運(yùn)用于旅游交通優(yōu)化與線路組織上，即在賦權(quán)圖中找出一顆最優(yōu)樹，以滿足以最短路徑最小連接各旅游目的城市和最小的建設(shè)成本。我們所學(xué)圖論及其算法教材中介紹了其中的三種算法Prim 算法、Kruskal 算法和破圈法。本文涉及的抽象圖形結(jié)構(gòu)較為簡單，使用各類算法的差別在此并無明顯體現(xiàn)，一般來說，Kruskal 算法應(yīng)用較為普遍，因此本文采用Kruskal 算法實(shí)現(xiàn)最優(yōu)路徑求取。文中通過一個例子應(yīng)用，將最小生成樹的Kruskal 算法實(shí)際化，通過算法步驟分析，以及在VC+6.0中程序的運(yùn)行，最終求出的最小生成樹與實(shí)際相符，該算法思想成立，并具有一

3、般性，能夠增刪節(jié)點(diǎn)、修改權(quán)值，也可運(yùn)用到其他問題的解決中。關(guān)鍵詞：旅游路線問題 Kruskal算法 最優(yōu)路線 最小生成樹一、引言旅游交通是為旅游者由客源地到旅游目的地的往返，以及在旅游目的地各處旅游活動而提供的交通設(shè)施及服務(wù)，其便利程度，是衡量旅游業(yè)發(fā)達(dá)程度的重要標(biāo)志。與一般交通不同，旅游交通過程本身也是旅游體驗(yàn)過程，對于游客來說，立足于最小的時間與經(jīng)濟(jì)成本獲得最多的旅游體驗(yàn)，對于旅游組織者來說，則立足于最小的建設(shè)成本與最大的社會、經(jīng)濟(jì)、生態(tài)效益。道路是交通的載體，具有高度通達(dá)性、完善的旅游服務(wù)功能和景觀化、生態(tài)化、人性化的道路是區(qū)域旅游交通完善的重要標(biāo)志，基于此，有學(xué)者提出“風(fēng)景道”、“旅游

4、交通干道”等規(guī)劃建設(shè)理念與原則。其中，旅游交通系統(tǒng)的優(yōu)化很大程度取決于合理的道路布局，而如何使道路通達(dá)性與建設(shè)成本之間獲得平衡，達(dá)到性價比最優(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ù)。二 、背景知識1、 圖和樹圖論中的圖是由若干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形通常用來描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個事物間具有這

5、種關(guān)系。樹是無圈連通無向圖，如果樹T的節(jié)點(diǎn)數(shù)為n，那么樹的邊數(shù)為n-1。2、 生成樹連通圖 G 上的一個子圖，該子圖連通，無回路且包含圖G 的所有節(jié)點(diǎn)，稱為連通圖的極小連通子圖。一個連通圖可以有多棵不同的生成樹。3、 最小生成樹對一個帶權(quán)連通圖，也有多可不同的生成樹。由于該圖是帶權(quán)圖，各邊的權(quán)值不一定相等，因此這些生成樹的各邊權(quán)值之和也不一定相同，其中權(quán)值最小的生成樹被稱為該帶權(quán)連通圖的最小生成樹4。三 、最小生成樹的求解方法構(gòu)造最小生成樹可以有多種算法。我們所學(xué)圖論及其算法教材中介紹了其中的三種算法 Prim 算法、 Kruskal 算法和破圈法，本文分別用這三種算法來實(shí)現(xiàn)最小生成樹的構(gòu)造。

6、1、Prim 算法算法思想：普里姆算法通過逐個往生成樹上添加頂點(diǎn)來構(gòu)造連通網(wǎng)的最小生成樹。算法具體步驟：（1） 開始：選取連通網(wǎng)中的任意一個頂點(diǎn)添加到最小生成樹中。（2） 重復(fù)執(zhí)行以下操作：Ø 連通網(wǎng)的頂點(diǎn)集合分成兩個部分：已經(jīng)添加到最小生成樹中的頂點(diǎn)集合和尚未添加到最小生成樹中的頂點(diǎn)集合；Ø 找出所有連通這兩個集合中頂點(diǎn)的邊；Ø 從中選取一條權(quán)值最小的邊添加到生成樹中，同時將與這條邊相連的頂點(diǎn)也添加到生成樹中。（3）結(jié)束：所有的頂點(diǎn)都被添加到最小生成樹中。2 、Kruskal 算法算法思想：通過逐個往生成樹上添加邊來構(gòu)造連通網(wǎng)的最小生成樹。算法具體步驟：（1）

7、將連通網(wǎng)中的所有頂點(diǎn)添加到最小生成樹中，構(gòu)造一個森林；（2） 將各邊按照權(quán)值從小到大排序；（3） 按照排好的順序向生成樹中添加不使森林中產(chǎn)生回路的邊 (若構(gòu)成回路則不添加，繼續(xù)考察下一條邊)。直至該森林變成一棵樹為止。3、 破圈法算法思想：通過逐個從連通網(wǎng)中刪除邊來構(gòu)造最小生成樹。算法具體步驟：（1） 將連通網(wǎng)中各邊按照權(quán)值從大到小排序；（2） 按照排好的順序從連通網(wǎng)中刪除權(quán)值最大的邊，條件是使刪除該邊后的子圖仍然保持連通(若刪除后子圖不連通則改邊保留，繼續(xù)刪除下一條邊)。直至子圖中任何一條邊都不能刪除 （即刪除任意一條邊都會造成該子圖不連通）為止。4 、三種算法的比較（1） 普里姆算法：主要

8、是對頂點(diǎn)進(jìn)行操作；采用鄰接矩陣作為存儲結(jié)構(gòu)，在行過程中對連通網(wǎng)中的每一個頂點(diǎn)都考察到了。普里姆算法適用于求邊稠密的連通網(wǎng)的最小生成樹。（2） 克魯斯卡爾算法：主要是對邊進(jìn)行操作，時間復(fù)雜度主要取決于對邊按照權(quán)值進(jìn)行排序的時間，邊的個數(shù)為e，排序的時間復(fù)雜度可以做到O (eloge)，因此算法的時間復(fù)雜度為 O(eloge)。克魯斯卡爾算法適用于求邊稀疏的連通網(wǎng)的最小生成樹。（3） 破圈法：主要是對邊進(jìn)行操作，時間復(fù)雜度主要取決于對邊按照權(quán)值進(jìn)行排序的時間，邊的個數(shù)為e，排序的時間復(fù)雜度可以做到 O (eloge)，因此算法的時間復(fù)雜度為 O(eloge)。該算法適用于求邊稀疏的連通網(wǎng)的最小生成

9、樹5。四、 應(yīng)用利用最小生成樹來解決旅游路線問題，將旅游路線問題中的旅游景點(diǎn)看做圖中的頂點(diǎn)，各個景點(diǎn)之間的路線看做圖中頂點(diǎn)之間的邊，景點(diǎn)之間路線的長度看做圖中各邊上的權(quán)值。這樣，我們就把旅游路線問題轉(zhuǎn)換成了求一個有向連通網(wǎng)的最小生成樹問題。此時，假設(shè)景點(diǎn)個數(shù)為6，分別為v1,v2,v3,v4,v5,v6。并設(shè)其對應(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算法步驟依次

10、添加邊（1,3）, （4,5）, （2,6）, （3,6）, （3,4），并依次添加對應(yīng)節(jié)點(diǎn)，各個步驟結(jié)果如下圖： 第一步 第二步 第三步 第四步 第五步（2） 仿真及結(jié)果分析在vc+6.0環(huán)境下，首先輸入圖的頂點(diǎn)數(shù)和邊數(shù)，然后輸入第一條邊的起始點(diǎn)和終點(diǎn)，以及這條邊的權(quán)值，直到輸完為止自動將權(quán)從小到大排序，并且得出最小生成樹，如下圖運(yùn)行結(jié)果所示。五、總結(jié)本文首先將實(shí)際的旅游路線選擇問題轉(zhuǎn)化成了圖論的最小生成樹問題，然后選用Kruskal算法編寫相應(yīng)的C語言程序最終實(shí)現(xiàn)。這樣一方面可以得到一條最有效的路線，使得路途觀賞性和時間效率都得到提高，另一方面還可以增加景點(diǎn)（頂點(diǎn)數(shù)），改變邊的權(quán)值（景點(diǎn)之

11、間的距離）等等，具有靈活、準(zhǔn)確、簡便等特點(diǎn)，由于它的一般性，不僅僅解決了旅游路線選擇的問題，同時還適用于其他問題的解決。參考文獻(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é)出版社，20065李曉莉，王發(fā)曾，羅軍.中原城市群軌道交通干線選擇研究J.2008,10附錄Kruskal算法程序：#include<stdi

12、o.h>#include<stdlib.h>#define M 20#define MAX 20typedef struct /構(gòu)造邊 int begin; int end; int weight; /權(quán)值edge;typedef struct int adj; int weight;AdjMatrixMAXMAX;typedef struct AdjMatrix arc; int vexnum, arcnum; /頂點(diǎn)數(shù)和邊數(shù)MGraph;void CreatGraph(MGraph *); /函數(shù)申明 構(gòu)造圖void sort(edge* ,MGraph *); /函數(shù)申

13、明 對邊的排序void MiniSpanTree(MGraph *); /最小生成樹int Find(int *, int ); void Swapn(edge *, int, int); /交換兩條邊的權(quán)值和它們的起點(diǎn)和終點(diǎn) void CreatGraph(MGraph *G) /構(gòu)件圖G int i, j,n, m; printf("請輸入圖的頂點(diǎn)數(shù)和邊數(shù):"); scanf("%d %d",&G->vexnum,&G->arcnum); for (i = 1; i <= G->vexnum; i+) /初始化

14、圖 for ( j = 1; j <= G->vexnum; j+) G->arcij.adj = G->arcji.adj = 0; for ( i = 1; i <= G->arcnum; i+) /輸入邊和權(quán)值 printf("n請輸入邊的起始點(diǎn)和終點(diǎn):"); scanf("%d %d",&n,&m); while(n < 0 | n > G->vexnum | m < 0 | m > G->vexnum) printf(" n");prin

15、tf(" n"); printf("輸入的數(shù)字不符合要求 請重新輸入:"); scanf("%d%d",&n,&m); G->arcnm.adj = G->arcmn.adj = 1; getchar(); printf("n請輸入%d與%d之間的權(quán)值: ", n, m); scanf("%d",&G->arcnm.weight); /輸入權(quán)值 void sort(edge edges,MGraph *G) /對權(quán)值進(jìn)行排序 int i, j; for

16、( i = 1; i < G->arcnum; i+) for ( j = i + 1; j <= G->arcnum; j+) if (edgesi.weight > edgesj.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&quo

17、t;); for (i = 1; i <= G->arcnum; i+) printf(" <<%d %d>> %dn", edgesi.begin, edgesi.end, edgesi.weight); void Swapn(edge *edges,int i, int j) /交換權(quán)值 以及頭和尾 int temp; temp = edgesi.begin; edgesi.begin = edgesj.begin; edgesj.begin = temp; temp = edgesi.end; edgesi.end = edgesj

18、.end; edgesj.end = temp; temp = edgesi.weight; edgesi.weight = edgesj.weight; edgesj.weight = temp; void MiniSpanTree(MGraph *G)/生成最小生成樹 int i, j, n, m; int k = 1; int parentM;edge edgesM; for ( i = 1; i < G->vexnum; i+) for (j = i + 1; j <= G->vexnum; j+) if (G->arcij.adj = 1) edgesk.begin = i; edgesk.end = j; edgesk.weight = G->arcij.weight; k+; sort(edges, G); for (i = 1; i <= G->arcnum; i+) parenti = 0; printf("n");printf(" n");printf(" n");printf(" n");