《世博園區(qū)導(dǎo)游線路圖的規(guī)劃》由會員分享，可在線閱讀，更多相關(guān)《世博園區(qū)導(dǎo)游線路圖的規(guī)劃（15頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、 我們現(xiàn)在的問題:如果從中國館到一個目的地，有好幾種線路可供選擇，怎樣走法才能使花費(fèi)的時(shí)間最?。咳绻胶脦讉€展館游覽，應(yīng)該如何安排順序，才能使花在路上的時(shí)間最短，游遍所有的展館同時(shí)又不重復(fù)；在一個區(qū)域內(nèi)參觀，應(yīng)該怎樣安排參觀線路，既能走遍所有的展館，又能使總的行走路線最短； 游覽路線中的圖論問題 1、游覽線路的選擇最短路問題 2、游覽展館順序的安排旅行售貨員問題 3、展區(qū)內(nèi)游覽線路安排歐拉回路與中國郵遞員問題 1、游覽線路的選擇 最短路問題 如果從中國館出發(fā)要到某地啟他的展館，如果有幾種不同的旅游路線可供選擇，自然希望選擇總長度最短，或者所花費(fèi)的時(shí)間最少，或者所化的費(fèi)用最省的走法。這就是圖論

2、的最短路問題。首先，對于圖上的每一條邊，都給出一個非負(fù)數(shù)，稱為該條邊的權(quán)，用以代表這條邊的長度、或者走過這條邊所花費(fèi)的時(shí)間、費(fèi)用等。每條路上各邊的權(quán)的總和統(tǒng)稱為路的“長度”，這樣圖稱為非負(fù)賦權(quán)圖。而在不同的路中選擇總長度最小的，就是最短路問題。 求最短路的方法 求最短路，圖論中有很多方法。較為常用的是一種標(biāo)號的方法Dijkstra算法。該算法由狄克斯特拉(E.W.Dijkstra)于1959年提出，其基本思想是從起點(diǎn)出發(fā)，逐步找出距離最近的點(diǎn)。在此過程中，同時(shí)記錄下可能作為最短路的方案。 例題：求下圖中A點(diǎn)到其他個點(diǎn)的最 短路及其長度 2、游覽展館的順序安排 旅行售貨員問題 到某個展區(qū)游覽，怎

3、樣走才能游遍所有的展館?這就是圖論中點(diǎn)的行遍性問題。 點(diǎn)的行遍性問題也稱Hamilton問題。這是因?yàn)樽钤缣岢鲞@類問題的是英國的Hamilton爵士。 在一個圖中找一個總長度最短的哈密爾頓回路，這就是旅行售貨員問題，簡稱TSP, 是一個非常著名的世界難題。 在TSP的近似算法中，最簡單的方法稱為“最近鄰點(diǎn)法”：從出發(fā)點(diǎn)出發(fā)，先選擇與其最接近的城市，然后再剩余的城市中選擇與最近的,依次得到各個城市的經(jīng)過次序，最終回到。 求哈密頓圈的方法 3、展區(qū)內(nèi)游覽線路安排 歐拉回路與中國郵遞員問題 在一個展區(qū)內(nèi)游覽，應(yīng)該怎樣安排游覽線路，既能走遍所有的景點(diǎn)，又能使總的行走路線最短？ 構(gòu)造一個圖，使得每個展館

4、都分布在這個圖的邊上，問題就轉(zhuǎn)化為從第一個點(diǎn)出發(fā)，走遍該圖中的每條邊，最后回到出發(fā)點(diǎn)。 最好的情況是所有路都走遍并且沒有重復(fù)，這樣的總路程數(shù)是最少的。這其實(shí)就是一筆畫的問題，因?yàn)槭菤W拉找到解決此類問題的方法，所以也把此類問題稱為歐拉回路。 然而，有些問題是做不到“一筆畫”，也就是有些路必須重復(fù)經(jīng)過，那應(yīng)該重復(fù)那些路呢？才能使總距離最短？事實(shí)上也就是重復(fù)的路線長度最短。這就是“中國郵遞員問題”了。 求解中國郵遞員問題的口訣：先分奇偶點(diǎn)，奇點(diǎn)對對聯(lián)；連線不重疊，重疊需改變；圈上聯(lián)線長，不得過半圈。 假如我們的展館分布如下圖所示 在圖中從第一個點(diǎn)出發(fā)經(jīng)過所有邊至少一次，然后回到出發(fā)點(diǎn)，使得總長度最短。 答 案： 世博會的腳步聲已經(jīng)越來越近了，我們每一個上海人、中國人都應(yīng)該為世博做一些我們力所能及的事情，讓這個城市更加美好