資源描述：
《環(huán)游世界的計劃》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。
1、環(huán)游世界的計劃評閱專家1評閱專家2評閱專家3評閱專家4評閱專家5摘要1，對這個模型我們運用“Floyd算法”計算最短時路徑。2，結果為從倫敦出發(fā)打賭會輸。從上?；蚣~約出發(fā)打賭會贏。9正文部分一、問題重述環(huán)游世界80天在儒勒·凡爾納的著名小說《環(huán)游世界80天》中，英國紳士福格在倫敦與人打賭能夠在80天內環(huán)游世界，這在當時的1872年是一個了不起的壯舉。當時最快的旅行方式是火車和輪船，然而世界上大部分地區(qū)還是靠馬車、大象、驢子或者步行來旅行。下面是一個從倫敦環(huán)游世界9不同路線的交通網(wǎng)絡圖，福格選擇的是往東走，每段路線所需要的
2、天數(shù)顯示在圖上，旅行的時間基于1872年能采用的旅行方式以及距離。1.請設計一個算法為福格選擇一條最佳路徑，即環(huán)游世界天數(shù)最短，你選擇的路徑能讓他贏得賭注嗎？2.如果他在別的地方與人打賭，比如紐約或者上海，結果會怎樣？一、問題分析此題已經簡化為了計算從圖中一點出發(fā)再次回到這一點所需最短時間的問題。由題中題意易知，環(huán)游世界時是利用地球做為球體的性質一直朝東或西方向行進最后回到原位置的。觀察圖中所給點的標號易知由數(shù)值小的標號向數(shù)值大的標號行進的話則為由西相東行進。由于要算得最短旅行所需時間，而旅行線路為一首尾相接的折線。所以
3、從地球上方觀察的話，順逆時針的方向并不影響旅行總時間。然而由西向東行進時會經過一次國際日期變更線使得旅行時間在以出發(fā)地時間計算時會少一天，即所計算時間會比實際時間少一天。同理如果由東向西旅行的話時間9會比實際時間多一天。因此我們默認旅行者均由西向東來環(huán)游世界以算得最短時間。此題為一個求最短路徑的問題，考慮到此題所涉及的數(shù)據(jù)較多，我們認為應該使用“Floyd算法”。一、模型假設1，由問題分析中知，我們假設旅行者除了回到出發(fā)地時外均為由標號小的城市向標號數(shù)值大的城市運行。2，在旅行過程中，假設不會發(fā)生任何意外影響旅行時間。3
4、，圖中由點15-Minsk到點19-Moscow的距離未給出。根據(jù)歷史資料，兩城市間最短行進時間為5天。我們以此數(shù)據(jù)來計算題目。4，圖中由點31-Calcutta到點32-Bangkok的距離未給出。根據(jù)歷史資料，兩城市間最短行進時間為3天。我們以此數(shù)據(jù)來計算題目。二、符號說明為避免計算時城市標號干擾計算數(shù)值，及在程序中方便調用，將城市按其標號順序命名為V1,V2,…。三、模型建立我們運用“Floyd算法”計算最短路徑，將“Floyd算法”編為一個子函數(shù)，然后設置一個TXT文件來輸入環(huán)游世界圖的每個路徑長短，我們將每個地
5、點的位置設為v，下標他們的標號以辨別各個位置，比如倫敦標號為1，即倫敦為v1，上海為37，那上海就被表示為v37。Floyd的核心思路為通過一個圖的權值矩陣求出它的每兩點間的最短路徑矩陣?！ 膱D的帶權另接矩陣A=[a(i,j)]n×n開始，遞歸地進行n次更新，即由矩陣D(0)=A，按一個公式，構造出矩陣D(1)；又用同樣地公式由D(1)構造出D(2)；……9；最后又用同樣的公式由D(n-1)構造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號頂點到j號頂點的最短路徑長度，稱D(n)為圖的距離矩陣，同時還可引入一個后繼
6、節(jié)點矩陣path來記錄兩點間的最短路徑。算法的過程為：1，從任意一條單邊路徑開始。所有兩點之間的距離是邊的權，或者無窮大，如果兩點之間沒有邊相連。 2，對于每一對頂點u和v，看看是否存在一個頂點w使得從u到w再到v比己知的路徑更短。如果是更新它。我們用A[i][j]來表示他們每兩點之間需要的時間，如A[1][6]=1，表示從v1到v6需要的時間為1天。因為題設中提到，福格選擇了向東走，所以我們不妨把圖中的距離變?yōu)橛邢蚓€段，即只能從v1走到v6，不能從v6走到v1。為了能準確的表示從一點到另一點是不能走的，我設置了一個M
7、AX_INT＝10000，來表示他們間的距離是為無窮大。所以我們可以知道A[1][6]=1,但A[6][1]=MAX_INT。在程序中，我將從倫敦,上海和紐約分為3個部分，輸入1，2或3就能分別計算從不同的地方出發(fā)的不同路徑以及時間。因為我們是將圖中的數(shù)據(jù)輸入在TXT文件中的，所以在運用C語言程序的時候，我們要將“INPUT1.txt”“INPUT2.txt”“INPUT3.txt”3個文件都要放入D盤下，這樣在讀入TXT文件的數(shù)據(jù)時，程序的尋址才是正確的，TXT文件中的數(shù)據(jù)才能讀入程序中。TXT文件的格式是每3個數(shù)一排
8、，分別表示路徑的起點終點和路徑走過需要的時間。在倫敦出發(fā)時，為了減少運算量，我們不妨計算一些路徑長短來時程序變得簡易，使數(shù)據(jù)更加簡單，如假設經過v27有條路徑，我將它分別計算了一次，結果表明（v1,v9,v14,v18,v27）這條路徑是最短的，所以我將別的路徑都歸了零，如（v1,v10,v15,v19,v27）,但
