四人過(guò)橋分析

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

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

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