四人過橋分析_第1頁
四人過橋分析_第2頁
四人過橋分析_第3頁
四人過橋分析_第4頁
全文預覽已結束

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權，請進行舉報或認領

文檔簡介

1、四人過橋問題重述：有一天晚上，有四個人需要通過架在山谷間的危橋，任意時刻最多只能有兩 個人在橋上，過橋需要一盞閃光燈，這些人只有一盞閃光燈。如果單獨過橋他們 分別需要10、5、2、1分鐘，如果兩人同時過橋則所需時間是較慢者所需的時間。 18分鐘后，沿山谷滾滾而下的山洪將把這座橋沖毀。這四個人能及時過橋嗎？ 不用圖論知識，證明你的結論；并說明如何用圖論知識獲得答案。問題分析：證明：因為只有一盞閃光燈，并且過橋時必須要用到閃光燈，唯一的辦法就是讓2個人一起過橋，然后讓其中的一個在返回來送閃光燈，從橋上走一來回的結果是可以讓1個人通過.當2個人一起過橋時，總是最慢的1個人決定過橋的速 度。把這幾個人

2、按照花費時間的由多到少編號為A,B,C,D,可知道要讓四個人全部過橋至少需要5趟。設A, B, C,D四個人單獨過橋分別需要10、5、2、1分鐘。 注意到A,B兩人單獨過橋需要的時間較多，若 A和B不一起過橋，則A和B過 去至少需要15分鐘（2趟），然后還要有三趟，因為兩人同時過橋則所需時間 是較慢者所需的時間，所以若 C,D一起過去，則需要2分鐘（1趟），然后還有 2趟至少需要2分鐘，則所需時間至少為15+2+2=19分鐘，已經(jīng)超過18分鐘， 所以要想有可能四個人能及時過橋則 A,B必須一起過橋，為了讓時間最少，回來 的時候不能用A或B。因此1. 一開始應該讓C和D先過2分鐘；2. 然后D回

3、來，讓A和B過去1+10分鐘;3. C 回來，C和D一起過去2+2分鐘?？傆脮r為：2+1+10+2+2=17分鐘，即這四個人在18分鐘內(nèi)及時能過橋用圖論知識，可以以4個人在橋兩端的狀態(tài)來作為節(jié)點來構造一個有向圖， 用1表示此人未過橋，用0表示此人已過橋故一共有2A4 = 16種情況。因為要 考慮到燈的問題，必須有燈才能過橋，去程（奇數(shù)次鏈接）只能將 1變0,返程 （偶數(shù)次鏈接）只能將0變1,故在河的則在此岸共有16種可能存在的狀態(tài)， 如下表所示：狀態(tài)點ABCD名字E1111F0011G0101H0110I1001J1010K1100L1110M1101N1011O0111P0001Q0010R0100S1000T0000注釋：E表示閃光燈和四個人全在此岸用這四個人和閃光燈的狀態(tài)點作為圖的節(jié)點來構造一個有向圖，時間作為有向邊的權值，可以得到以下有向圖：要求出最少需要多長時間4人全部通過小橋?qū)嶋H上就是在圖中求出 E節(jié)點到 T節(jié)點間的最短路徑。最后可用 Dijkstra 算法求出最短路徑。 可得最短路徑為

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論