一道面試題及其推廣過橋問題

一、問題

在漆黑的夜裡，四位旅行者來到了一座狹窄而且沒有護欄的橋邊。如果不借助手電筒的話，大家是無論如何也不敢過橋去的。不幸的是，四個人一共只帶了一隻手電筒，而橋窄得只夠讓兩個人同時過。如果各自單獨過橋的話，四人所需要的時間分別是1、2、5、8分鐘;而如果兩人同時過橋，所需要的時間就是走得比較慢的那個人單獨行動時所需的時間。問題是，如何設計一個方案，讓這四人儘快過橋。

假設這四人分別為A、B、C、D。很明顯，開始兩人拿著手電筒過橋後，手電筒就在橋的另一邊了，此時需要已經過橋的那兩人中的一個再把手電筒送回橋這邊。送手電筒回來過橋也要化時間，所以要選一個跑得比較快的。一個很自然的想法就是，每次讓跑得最快的A陪著另一個過橋，然後A快速地跑回來，再陪下一位過去，最後所有人就都可以過橋了。

讓我們來算一下這要多長時間。為了方便起見，我們把旅行者出發的橋的這一邊稱為“此岸”，而把旅行者想要到達的那邊叫“彼岸”。在表達一個過橋方案時，我們用“←”來表示從彼岸到此岸的移動，用“→”表示從此岸到彼岸的移動。前面“A護送大家過河”的方案就可以寫成：(右邊數字為完成此步驟所需時間)

A　B　→　2

A　←　1

A　C　→　5

A　←　1

A　D　→　8

一共就是2+1+5+1+8=17分鐘。

但其實有更快的辦法：

A　B　→　2

A　←　1

C　D　→　8

B　←　2

A　B　→　2

一共是2+1+8+2+2=15分鐘。這個辦法的聰明之處在於讓兩個走得最慢的人同時過橋，這樣花去的時間只是走得最慢的那個人花的時間，而走得次慢的那位就不用另花時間過橋了。可以把所有可能的方案都列舉一遍，就會發現這是最快的方案了。

現在我們把這個問題推廣到N(N≥4)個人過橋的情況：如果有N個旅行者，假設他們有各自所需的過橋時間(正實數)。在只有一隻手電筒的情況下，要過上述的一條橋，怎樣才能找到最快的過橋方案?

假設最快地把N個旅行者從此岸移動到彼岸需要f分鐘時間，那麼我們把所有在f分鐘時間內把N個旅行者從此岸移動到彼岸的方案稱為“最佳方案”。最佳方案很有可能不止一個，我們的目的是要找到一個最佳方案，但是並不需要把所有的最佳方案全都找出來。

二、一個合理的假設

為了討論的方便起見，這一節我們要說明的是，事實上我們可以假設每個旅行者的速度都是不一樣的。這樣當我們說一些人中“最快的那個”，“次慢的那一個”時，都不會有歧義了，因為每個人的速度都是獨一無二的。這個假設在討論中並非必要，只是為了在證明的敘述過程中避免不斷地嗦類似“我們讓兩人中最快的那個過橋，如果兩人一樣快，那就隨便選一人”、“我們選在彼岸最快的那個人回來，如果上一步剛從此岸到彼岸的人中，其中有一個是現在彼岸走得最快的之一，我們就特別選擇讓他回來”之類的話。

為什麼我們可以假設每個旅行者的速度都是不一樣的?原理就在於，我們可以把原來過橋時間相同的旅行者的過橋時間分別加上一個不同的但是非常非常小的量，這樣就能保證旅行者的速度是不一樣的了。但是因為加上去的量都非常小，所以對最終總的過橋時間的影響也非常小。所以這樣改動過後得到的最佳方案在原來的條件下實施的話，也該是原來條件下的最佳方案。

如果你對上面的說明滿意了，就完全可以跳過這一節直接看第三節。這一節後面哩叭嗦的都是為了向一些對嚴格性要求比較高的朋友解釋上面所說的方法的確可行。

首先對於任何一組N個旅行者，假定他們過橋所需的時間分別為a1、a2、……、aN，它們都是大於零的實數。假設這個序列已經從小到大排列了(當然不排除其中有數相等)。每次都由第一個旅行者陪同一個人過橋，然後第一個旅行者回來，這樣一個方案所需要的時間是：

S = (N-2)*a1+a2+……+an

(第一個旅行者要返回N-2次)。所以最佳方案所需要的時間一定不會比S大。

我們把一個過橋方案中讓一個或者兩個人拿著手電筒從橋的一邊走到另一邊的一次移動叫做這個方案中的一次移動或者“一步”，就是前面解四個人的題中使用“→”或“←”來表示的一個步驟。因為一次移動所需要的最少的時間是a1分鐘，所以最佳方案中所需的移動步數一定不會多於K=[S/a1]步，這裡"[]"是取整運算。

讓我們考慮一下所有在K步以內完成的方案。上面的例子表明這樣的方案至少有一個，而且這樣的方案顯然只有有限多個，假設一共有M個。我們又設這些方案執行時要花的時間是

t1、t2、……、tM

我們還可以假設上面這些時間已經從小到大排列了，t1就是最佳方案所需要的時間。

現在是關鍵的步驟。我們要選取一個很小的正實數ε>0。它有多小呢?它必須滿足下面的條件：

1) 對於任何兩個過橋時間不同的旅行者(假設他們的過橋時間是a和b分鐘)，必須滿足ε<|a-b|/N。換句話說，Nε要小於不同的旅行者過橋時間之間的差別。

2) 對於任何兩個所需的完成時間不同的K步以內的方案(假設它們的所需時間是t和s分鐘)，必須滿足ε<|t-s|/K。換句話說，Kε要小於不同的方案完成時間之間的差別。

因為旅行者的數目和方案的數目都是有限的，所以我們必然可以選取這樣一個ε。至於這兩個條件有什麼用，我們馬上就可以看到。

假設若干個旅行者過橋的時間都是一樣的a分鐘，我們就把題目改一下，使得他們的過橋時間分別為

a、a+ε/N、a+2ε/N、a+3ε/N……

如果有其他的旅行者過橋時間相互一樣，也按照同樣方式修改題目。這時在修改後的題目中，如果原來兩個旅行者所需的過橋時間相同，那麼現在就變得不同，差一個非常小的量(不會超過ε);如果原來兩個旅行者所需的過橋時間不同，那麼根據上面的條件1)，現在還是不同，而且原來誰比較快，現在仍舊是他比較快。

我們看看這個修改後的題目的最佳方案和原來的題目的最佳方案有什麼聯絡。

假設我們已經有一個關於修改後的題目的最佳方案，那麼它所需要的時間必定是這個模樣的：

a + bε

我們知道bε部分是修改時把旅行者過橋時間“微調”了以後造成的，而且每走一步這部分的改變不會超過ε，所以我們有0

如果我們把這個最佳移動方案照搬到原來的題目中去，所需要的時間就是a分鐘。這個方案應該同樣是原來題目中的最佳方案。否則的話，假設我們有另一個方案，所需時間為a，而且a

a < a + Kε

把這個耗時a的方案搬到改動過的題目裡去的話，所需的時間就會是

a + bε

其中0

a + bε < a + bε

這就和a+bε是改動後題目的最佳方案所需的時間矛盾了。

所以只要找到一個修改過的題目中的最佳方案，我們就得到了原來題目中的一個最佳方案，於是我們只要考慮所有旅行者的速度都不同的題目就可以了。

三、一個“很顯然”的結論

編個計算機程式，把所有步數少於上一節中所計算的K=[S/a1]的可能的過橋方案都列舉一遍，然後找出最快的，當然是一種方法，這理論上也是可行的，因為少於K步的`方案只有有限多個，計算機程式必定能夠將它們全部列舉出來。只是當人數N增大時，過橋方案數會增加得很快。事實上，如果我們只考慮“每次過去兩個人，然後這兩個人中其中一個人回來”這類方案的數目的數量就已經遠遠超過N!個了，想像一下如果N=1000的話所需要的計算量!況且還有更多數量的其他型別方案。特別是，我們是在做智力題，不是在學程式設計。當然你還可以說，如果人多的話，所需要的時間超過了12小時，那時天已經亮了，不再需要手電筒，大家可以直接過橋唉!我們是在做智力題，不是在做抬槓式的腦筋急轉彎我們可以假設是在有漫長極夜的極地嘛，要不然，這橋是在一個黑暗山洞裡，就象電影《指環王》中的那樣……

但是如果不用列舉法的話，我們有一個重要的任務要做，就是不僅要說明如何找到一個我們自以為最快的方案，而且還要證明這樣的方法的確給出了一個最佳方案。

在我們的直覺當中，最快的方案必然有這樣一個特徵：每次過橋去彼岸的一定是兩個人，然後一定只有一個人把手電筒送回此岸(當然要除去最後一次過橋的情況，那時就不需有人把手電筒送回來了)。但是為什麼一定是這樣的呢?為什麼不可能有一個意想不到的巧妙方案，在那裡有某一步居然需要一個人單獨過到彼岸去，或者需要有兩個人把手電筒送回此岸來?這是個看起來很顯而易見但是我們不能支吾不回答的問題。

在討論中我們經常需要說明，在某一時刻，橋的兩邊分別有哪些人，手電筒又在哪一邊。這樣的說明稱為一個“局面”。當然，一個局面必須是合理的。比如說，不能夠所有人都在橋的一邊，而手電筒卻在橋的另一邊;一個人必須處在橋的某一邊，而且只能處在橋的某一邊。

比如說，在四個旅行者的問題裡，如果某一個時刻A、B和C在此岸，而D在彼岸，手電筒也在彼岸，這就給出了一個局面(這個局面看起來有點奇怪，大概是D拿著手電筒一個人跑過橋去了，接下去除了他再拿著手電筒回來別無它法)。所有人和手電筒都在此岸，就是一個特殊的局面，叫作初始局面;而所有人和手電筒都在彼岸，也是一個特殊的局面，叫完結局面;所有其他的局面我們稱為中間局面。

想像一下現在有兩種局面。在兩種局面中，手電筒都在橋的同一邊(都在此岸或都在彼岸);而且在第一種局面裡所有在彼岸的旅行者，在第二種局面裡也都在彼岸，而且有這樣的旅行者，在第一種局面中他在此岸，而第二種局面中他在彼岸。那麼我們就說第二種局面“優於”第一種局面。

比如說，在四個旅行者的問題裡，第一種局面是A、B和C在此岸，而D在彼岸，手電筒也在彼岸;第二種局面是A和B在此岸，C和D在彼岸，手電筒也在彼岸。那麼第二種局面就優於第一種局面。很顯然，除了初始