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

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

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

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

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