微軟面試中的過(guò)橋問(wèn)題

這是世界著名的微軟公司招聘人才時(shí)的兩道面試題。其中蘊(yùn)含的統(tǒng)籌優(yōu)化的數(shù)學(xué)思想方法，應(yīng)該引起我們的關(guān)注和重視。因?yàn)榕囵B(yǎng)自身在生產(chǎn)生活實(shí)際中尋求合理方案和最優(yōu)解答的能力，是現(xiàn)代人至關(guān)重要的必備素質(zhì)。

【過(guò)橋問(wèn)題1】小明一家過(guò)一座橋，過(guò)橋時(shí)是黑夜，所以必須有燈。現(xiàn)在小明過(guò)橋要1秒， 小明的弟弟要3秒，小明的爸爸要6秒，小明的媽媽要8秒，小明的爺爺要12秒。每 次此橋最多可過(guò)兩人，而過(guò)橋的速度依過(guò)橋最慢者而定，而且燈在點(diǎn)燃后30秒就會(huì)熄滅。問(wèn)：小明一家如何過(guò)橋？

【分析】首先必須明確的是，要節(jié)省時(shí)間，根據(jù)“每次此橋最多可過(guò)兩人”的條件限制，可以確定每次是兩人一起過(guò)橋。

其次因?yàn)橛腥吮仨毞祷卣彰鳎晕覀兘又梢耘袛嗟氖牵詈檬亲層脮r(shí)最少的小明擔(dān)任返回任務(wù)，如果難以實(shí)現(xiàn)，那也應(yīng)該讓用時(shí)較少的弟弟擔(dān)任返回任務(wù)。

再就是為了盡可能節(jié)省時(shí)間，我們應(yīng)該讓用時(shí)較多的人一起過(guò)橋，這樣不至于讓這些人分散多增加耗時(shí)。比如小明的媽媽和爺爺一起過(guò)橋只用時(shí)12秒，而如果分開(kāi)兩次過(guò)橋的話，用時(shí)8+12＝20秒就會(huì)大大增加。

有了這樣前提判斷，那么接下來(lái)我們就不難得到以下優(yōu)化配置：

（1）小明、弟弟過(guò)橋，用時(shí)3秒，緊接著小明持燈返回1秒；

（2）爺爺、媽媽過(guò)橋，用時(shí)12秒，緊接著弟弟持燈返回3秒；

（3）小明、爸爸過(guò)橋，用時(shí)6秒；緊接著小明持燈返回1秒；

（4）小明、弟弟過(guò)橋，用時(shí)3秒，一家五人匯合；

一家過(guò)橋總用時(shí)為3+1+12+

3+6+1+3=29秒，剛好在燈燃盡的范圍內(nèi)。

【過(guò)橋問(wèn)題2】 U2合唱團(tuán)的4名成員伯納、艾吉、埃達(dá)姆、勞瑞趕往演唱會(huì)現(xiàn)場(chǎng)，他們?cè)谕局斜仨毧邕^(guò)一座橋。4個(gè)人到達(dá)橋的一端，準(zhǔn)備過(guò)橋時(shí)，天已經(jīng)黑了。他們只有一只手電筒，一次最多可以有兩人一起過(guò)橋，而且過(guò)橋的時(shí)候必須持有手電筒，所以，就得有人把手電筒帶來(lái)帶去，來(lái)回橋的兩端。注意：手電筒是不能用扔的方式來(lái)傳遞的。4個(gè)人的步行速度各不同，若兩人同行，則以較慢者的速度為準(zhǔn)。伯納需花1分鐘過(guò)橋；艾吉需花2分鐘過(guò)橋；埃達(dá)姆需花5分鐘過(guò)橋；勞瑞需花10分鐘過(guò)橋。請(qǐng)問(wèn)：他們能在17分鐘內(nèi)過(guò)橋嗎？

【分析】 由題意可知，每次最多可以有兩人一起過(guò)橋，而且過(guò)橋的時(shí)候必須持有手電筒，所以，每次要有一人回去送手電筒，直到4個(gè)人全部過(guò)橋。因此他們過(guò)橋的情形只能是：2人去→1人回→2人去→1人回→2人去。也就是說(shuō)，過(guò)橋的總時(shí)間是由五段來(lái)回的時(shí)間組成，這是一個(gè)首要的判斷。

有了這個(gè)判斷，下面就是列舉出所有可能的方案，進(jìn)行試驗(yàn)篩選。從大的方面來(lái)說(shuō)，一種是讓花時(shí)間較多的兩人先過(guò)橋，一種是讓花時(shí)間較少的兩人先過(guò)橋。先來(lái)考察讓花時(shí)間較多的兩人先過(guò)橋的情況：

若讓埃達(dá)姆（5分鐘）和勞瑞（10分鐘）先過(guò)橋，他們?nèi)r(shí)用10分鐘，埃達(dá)姆回去送手電筒用5分鐘；然后，艾吉（2分鐘）和埃達(dá)姆（5分鐘）一起過(guò)橋，去時(shí)用5分鐘，此時(shí)已用去20分鐘，而且只有3人過(guò)了橋，顯然這種方案不可取。

既然如此，我們?cè)賮?lái)考察讓花時(shí)間較少的兩人先過(guò)橋的情況：

如果讓伯納(1分鐘）和艾吉（2分鐘）先過(guò)橋，他們?nèi)r(shí)用2分鐘，伯納回去送手電筒用1分鐘；然后，埃達(dá)姆（5分鐘）和勞瑞（10分鐘）一起過(guò)橋，去時(shí)用10分鐘。這時(shí)，已過(guò)橋的有3人，艾吉（2分鐘）、埃達(dá)姆（5分鐘）和勞瑞（10分鐘），還剩下伯納（1分鐘）沒(méi)過(guò)橋。顯然，應(yīng)該由艾吉回去接伯納，來(lái)回共需2×2=4（分）。這樣，4人過(guò)橋共用時(shí)： 2+l+10+2+2=17（分），滿足要求。

在這兩道難度各異本質(zhì)相同的面試題解答中，我們不難看出統(tǒng)籌規(guī)劃的縮影。它反映出人類(lèi)實(shí)踐活動(dòng)中普遍的最優(yōu)化概念，即要在盡可能節(jié)省人力、物力和時(shí)間前提下，爭(zhēng)取獲得在可能范圍內(nèi)的最佳效果。