吳昕宇　羅雪穎

摘要：考慮游客不會(huì)在游覽路線上往返、游覽路線不會(huì)重復(fù)，基于此，本文采用Dijkstra算法解決這個(gè)問題。首先，運(yùn)用圖論知識(shí)，將8個(gè)景點(diǎn)（包括景石）看成一個(gè)賦權(quán)無向圖，各景點(diǎn)為圖的頂點(diǎn)，兩景點(diǎn)之間步行最短路線為圖相應(yīng)兩頂點(diǎn)問的邊，距離為圖兩頂點(diǎn)問邊的權(quán)值，得到賦權(quán)圖。然后，用Dijkstra算法即可求解最短路線。

關(guān)鍵詞：Dijkstra算法圖論知識(shí)最短路線

引言

在物質(zhì)生活條件得到極大發(fā)展的今天，人們?cè)絹碓阶非缶裎拿鞯慕ㄔO(shè)，越來越多的人愛上旅行而背上背包去旅行。這就致使旅游資源供不應(yīng)求，一到假期便游人如織，在這樣的情況下，規(guī)劃游客的最優(yōu)路線，規(guī)劃游客的觀光時(shí)間，最大限度地利用旅游資源便十分重要。

2010年，江蘇省啟動(dòng)潘安湖土地整理項(xiàng)目，在一片廢墟上建成了一個(gè)6500畝湖面的國家級(jí)水利風(fēng)景區(qū)。2016年，賈汪被列為“國家全域旅游示范區(qū)”首批創(chuàng)建單位。本文選取潘安湖景區(qū)的部分景點(diǎn)，完成徐州潘安湖風(fēng)景區(qū)游覽最短路線設(shè)計(jì)問題。

1模型建立

從景石出發(fā)步行游覽①游客服務(wù)中心，②陽光草坪，③森林小劇場(chǎng)，④兒童科普體驗(yàn)區(qū)，⑤兒童戲水場(chǎng)，⑥濕地博物館，⑦濕地商業(yè)街。建立數(shù)學(xué)模型，找出所有景點(diǎn)至少觀光1次的距離最短的路線，計(jì)算該路線的長(zhǎng)度。

本問題要求設(shè)計(jì)從景石出發(fā)，經(jīng)過①②③④⑤⑥各景點(diǎn)，最終到達(dá)⑦濕地商業(yè)街，① ⑥所有景點(diǎn)至少觀光1次的距離最短的路線。在實(shí)際旅游觀光中，游客在各景點(diǎn)的旅游路線不會(huì)重復(fù)，而且游客不會(huì)在旅游路線上往返，基于此，本文將采用Dijkstra算法來解決此問題。

2.1無向圖定義

一個(gè)無向圖G是由一個(gè)非空有限集合V（G）和V（G）中某些元素的無序?qū)螮（G）構(gòu)成的二元組，記為G=（v（G），E（G））。其中，V（G）={v1，v2，L，v，）稱為圖G的頂點(diǎn)集或節(jié)點(diǎn)集，V（G）中的每一個(gè)元素

邊上賦權(quán)的無向圖稱為賦權(quán)無向圖或無向網(wǎng)絡(luò)，題目所給出的各景點(diǎn)之間步行最短距離即為無向圖邊上權(quán)值。

以各景點(diǎn)為圖G的頂點(diǎn)，兩景點(diǎn)之間步行最短路線為圖G相應(yīng)兩頂點(diǎn)間的邊，得到圖G。對(duì)G的每一邊e，賦以一個(gè)實(shí)數(shù)w（e），即景點(diǎn)之間步行最短距離，稱為e的權(quán)，得到賦權(quán)圖G。G的子圖的權(quán)是指子圖的各邊的權(quán)和。

問題便演化為求賦權(quán)圖G中指定的兩個(gè)頂點(diǎn)uo，vo間的具有最小權(quán)的軌。這條軌叫做uo，vo間的距離，記作d（uo，vo）。

2模型求解

本文采用Dijkstra算法編程求解。Dijkstra算法也稱為雙標(biāo)號(hào)法。所謂雙標(biāo)號(hào)，也就是對(duì)圖中的點(diǎn)vf賦予兩個(gè)標(biāo)號(hào)（，（u），1）：第一個(gè)標(biāo)號(hào)（p（v1）表示從起點(diǎn)V1到V1的最短路的長(zhǎng)度，第二個(gè)標(biāo)號(hào)λ3表示在v1到v1的最短路上V1前面一個(gè)鄰點(diǎn)的下標(biāo)，即用來表示路徑，從而可對(duì)終點(diǎn)到始點(diǎn)進(jìn)行反向追蹤，找到U1到vn的最短路。Dijkstra算法適用于每條邊的權(quán)數(shù)都大于或等于零的情況。下面是Dijkstra算法的內(nèi)容：

按距離uo從近到遠(yuǎn)為順序，依次求uo到G各頂點(diǎn)的最短路線距離，直至。

3模型分析

本文建立的最短路線尋求模型可以推廣應(yīng)用于交通運(yùn)輸、車輛路徑規(guī)劃、飛機(jī)航線安排、城市規(guī)劃、經(jīng)濟(jì)管理、物流貨物配送、通訊與網(wǎng)絡(luò)技術(shù)、計(jì)算機(jī)科學(xué)、信息技術(shù)與災(zāi)害應(yīng)急調(diào)度等領(lǐng)域。如交通查詢系統(tǒng)中需要給用戶提供多條可供選擇的最短路徑。

參考文獻(xiàn)

[1]史峰，王輝等.MATLAB智能算法30個(gè)案例分析[D].北京航空航天大學(xué)出版社，178-197.

[2]劉雪塵，基于博弈論的多模式動(dòng)態(tài)路徑規(guī)劃技術(shù)研究[D]，吉林大學(xué)，2017.