擺渡過(guò)河和四人過(guò)橋

1.擺渡過(guò)河：一只狼、一頭山羊和一籮卷心菜在河的同側(cè)。一個(gè)擺渡人要將它們運(yùn)過(guò)河去，但由于船小，他一次只能運(yùn)三者之一過(guò)河。顯然，不管是狼和山羊，還是山羊和卷心菜，都不能在無(wú)人監(jiān)視的情況下留在一起。問(wèn)擺渡人應(yīng)怎樣把它們運(yùn)過(guò)河去？分析：由于擺渡人每次只能運(yùn)載狼、山羊和卷心菜中的一樣，那么必然有兩樣物品要同時(shí)留在岸上。但是狼和山羊，山羊和卷心菜之間分別存在捕食關(guān)系，不能同時(shí)留在岸上。所以擺渡人在第一次渡河時(shí)應(yīng)先運(yùn)羊過(guò)河，留狼和卷心菜在岸上；將羊放在對(duì)岸后，擺渡人空船返回。第二次渡河時(shí)運(yùn)狼（或卷心菜），到達(dá)河對(duì)岸后放下狼（或卷心菜），將山羊運(yùn)回。第三次渡河時(shí)將卷心菜（或狼）運(yùn)到對(duì)岸，空船返回。第四次渡河時(shí)再將山羊運(yùn)到對(duì)岸，即完成了渡河任務(wù)。2.四人過(guò)橋：有一天晚上，有四個(gè)人需要通過(guò)架在山谷間的危橋，任意時(shí)刻最多只能有兩個(gè)人在橋上，過(guò)橋需要一盞閃光燈，這些人只有一盞閃光燈。如果單獨(dú)過(guò)橋他們分別需要10、5、2、1分鐘，如果兩人同時(shí)過(guò)橋則所需時(shí)間是較慢者所需的時(shí)間。18分鐘后，沿山谷滾滾而下的山洪將把這座橋沖毀。這四個(gè)人能及時(shí)過(guò)橋嗎？不用圖論知識(shí)，證明你的結(jié)論；并說(shuō)明如何用圖論知識(shí)獲得答案。分析及證明：由于這座橋最多只能有兩個(gè)人同時(shí)通過(guò)，并且過(guò)橋需要一盞閃光燈，但是四個(gè)人只有一盞閃光燈，那么唯一的辦法就是讓其中的2個(gè)人一起過(guò)橋，然后讓其中的1個(gè)人再返回來(lái)送閃光燈。將四人按照其單獨(dú)過(guò)橋時(shí)所花費(fèi)時(shí)間由短到長(zhǎng)編號(hào)為A、B、C、D。當(dāng)兩個(gè)人一起過(guò)橋時(shí)所花時(shí)間是兩個(gè)人中最慢的人的單獨(dú)過(guò)橋時(shí)間。無(wú)論誰(shuí)和D一起過(guò)橋都要花費(fèi)10分鐘，為了盡量節(jié)省時(shí)間，D和C肯定需要一起過(guò)橋，并且不能由C或D回來(lái)送閃光燈。因此，首先應(yīng)該讓A和B先過(guò)橋（2分鐘）；然后再讓A回來(lái)送燈，讓C和D過(guò)橋（1+10分鐘）；最后讓B回來(lái)，A和B一起過(guò)橋（2+2分鐘）?？偣灿脮r(shí)是：2+1+10+2+2=17分鐘＜18分鐘，所以說(shuō)這四個(gè)人在18分鐘內(nèi)能及時(shí)過(guò)橋。用圖論知識(shí)說(shuō)明：以4個(gè)人在橋兩端的狀態(tài)來(lái)作為節(jié)點(diǎn)來(lái)構(gòu)造一個(gè)有向圖，以已經(jīng)過(guò)橋了的人的狀態(tài)作為圖的節(jié)點(diǎn)，初始時(shí)沒(méi)有人過(guò)橋，所以以空表示，第一輪有兩個(gè)人過(guò)橋，有6種可能的組合，（1，2）（1，5）（1，10）（2，5）（2，10）（5，10），從空的狀態(tài)轉(zhuǎn)換到這些狀態(tài)的需要的時(shí)間分別為2，5，10，5，10，10分鐘，時(shí)間就作為有向邊的權(quán)值。當(dāng)有兩個(gè)人過(guò)橋后，需要一個(gè)人拿手電筒回去接其他人，這時(shí)有四種可能的情況，分別是1，2，5，10中的一人留在了河的對(duì)岸，（1，2）這種狀態(tài)只能轉(zhuǎn)換到（1）（2）兩種狀態(tài)，對(duì)應(yīng)的邊的權(quán)值分別為2，1分鐘，（1，2）轉(zhuǎn)換到（1）時(shí)也就是2返回了，返回需要耗時(shí)2分鐘，以此類推可以建立圖論模型。要求出最少需要多長(zhǎng)時(shí)間4人全部通過(guò)小橋?qū)嶋H上就是在圖中求出（空）節(jié)點(diǎn)到（1,2，5，10）節(jié)點(diǎn)間的最短路徑。最后可用Dijkstra算法求出最短路徑。

空集,0255222101丁5'21055521010分?5■1010)5.0510502,5210)510)2,10)空集,0255222101丁5'21055521010分?5■1010)5.0510