演算法練邏輯 助大腦思考

醒報編輯部 2018/08/13 11:58 點閱 16193 次

二十個問題?用五個提問解決問題。無論你是否想出了答案,我都可以向你保證,只要我們問一個不同的問題,你就會知道那問題是正確的。

20個問題遊戲

讓我們來玩玩「二十個問題」這個童年遊戲:我想像我是某個名人,由你來問我各種問題,然後試著猜出我是誰。轉折在於我只能用是或不是來回答問題。和朋友玩一次這遊戲,思考一下你在猜測時會問什麼問題,如此來看看遊戲可能進行的方向。

「你是女的嗎?」不是。「你還活著嗎?」不是。「你是個電影明星嗎?」不是。「你來自英國嗎?」是的。「你是個作家嗎?」是的。「你活在二十世紀嗎?」不是。「你活在十九世紀嗎?」不是。「你是莎士比亞嗎?」是的。

玩這個遊戲時,你可能會提出類似的問題。你不太可能會從提問「你是亞里斯多德嗎?」「你是詹姆士.龐德嗎?」「你是居禮夫人嗎?」這樣的問題開始,若用這種方式提問,你可能永遠也沒辦法在二十個問題之內得到答案。

你只有在最後,你已經很確定答案時(就像例子中那樣)才會提出這種問題。相反地,你可能會先提出「你是女的嗎?」之類的問題。

排除其他可能性

做為第一個問題,為什麼這是個好問題呢?這是因為無論答案為何,它都排除了另一半的可能性。如果你提問的是「你是女王嗎?」這樣的問題,若你剛好對了,你可以排除掉百萬種以上的可能性,但如果你是錯的(這種可能性較大),你就只排除掉一人。

換句話說,提出這樣的問題得要有中樂透的運氣,才能玩得好這個遊戲。所以,玩「二十個問題」的秘訣在於,無論答案是什麼,你每一次都要提出能排除一半人選的問題。

這樣做有多好?

完美的二分法

提出這種二分法的問題,比每次只提出一個人名好上許多,但有多好呢?假設一開始我想的是一百萬人中的一個人,那麼透過每次提問來排除掉一半的人,總共需要幾個問題呢?在提出一個問題後,人選只剩下五十萬人;兩個問題後,變成二十五萬人;在提出十個問題後,人選只剩下原本一百萬人當中的一千人了。

持續進行下去……之後每再一個問題分別會剩下五百人、二百五十人、一百二十五人……,而在第二十個問題時,只剩下一個可能人選。因此,如果你每次都能提出完美的二分法問題,你一定可以贏得這個遊戲。你永遠都可以在二十個問題裡猜出答案。

這全都是演算法思考。我們一直在試著找出一個能玩「二十個問題」遊戲的演算法,雖然我們尚未想出一套完整的演算法,但我們確實已想出提出問題的方法。

拆解問題是策略

當你玩這遊戲時,這就是你的問題了。我們在此使用了另一個計算思考的技法:拆解(decomposition)。我們將問題切(拆解)成不同部分,好讓我們能分別專注處理每一個小問題。我們已經想出整體的策略;至於要想出能排除半數人選的問題,則是另一個不同的問題。

拆解是個常見的解決問題策略,也是電腦科學家的一個必要工具。電腦科學家在寫程式或設計處理器(好比你筆電或電腦中的那種)時要解決的問題,數量往往十分龐大。現代電腦晶片比起整個地球的道路網絡還更複雜,可想而知想要一次就設計完成有多困難。只有把它拆解成你可以分別處理的元件,才有可能完成工作的一天。

拆解仰賴的是抽象化,即將細節藏起來。此處,我們將所要提出的確切問題這種細節隱藏起來,只思考該問的問題類型。我們前面在思考我們的演算法效率有多高時,也使用到了拆解。我們將寫完整本作品所需的時間這問題,拆解成溝通單一字母所需的時間,以及將結果轉化為寫完整本書所需時間這兩個問題。

轉變問題幫助解答

所以,在提出正確問題的前提下,最糟情況只需詢問二十個問題,就能從一百萬個可能性中找出我在想的那個人。

將上述遊戲與從二十六個字母中找出病患所想的那個字母平均需要十三個問題(最糟情況是二十六個問題)做比較,我們就會發現,當我們問「是A嗎?是B嗎?」時,我們所做的事等於是在問「你是米老鼠嗎?」「你是尼爾森.曼德拉嗎?」你在試著從許多事中找出我在想的那一個人,一模一樣。再一次,它本質上的確是一樣的問題,就像聯想字詞一樣!

如果這本質上和找出一個人正在想的字母是一樣的問題,那麼很明顯地,同樣的策略能給我們比之前所想到的種種解決方法,都還要好的解答。此處我們再次使用到了模式比對及通化。我們正在轉變問題,好再次使用過去已經得到的解。

演算法思考

那麼,我們的排除半數解決方案使用在字母上,會是怎樣的對應方式呢?我們一開始可以問「這是一個母音嗎?」但剩下來的四個問題該問些什麼呢。

既然我們每一次都需要排除半數的字母,那麼第一個問題顯然會是「這是一個在A到M之間的字母嗎?」如果答案是「是」,那麼我們再問「這是一個在A到F之間的字母嗎?」如果答案是「否」,那麼我們就改問「這是一個在N和S之間的字母嗎?」以此類推。這樣一來,我們就一定能在五個問題內得到那人心裡想的字母,如圖2的決策樹所示那般。

從圖的頂端開始,根據已知的是╱否問題一路向下走。在最糟的情況下,你也永遠會在五個問題後得到一個字母;這就是演算法思考的另一部分。而在可能出現混淆狀況時,我們則需確保雙方同意一致的細節,比如當我們說「這是一個在A到M之間的字母嗎」時,我們需要清楚知道,我們是否有把字母M包括進來(我們有)。

頻率分析技巧

我們甚至可以使用頻率分析技巧,來進一步改善這個解。舉例來說,在二十六個字母中,我們可以用比五個問題更快的方式得出字母E以及其他常用的幾個字母。你可以試試看,設計出一個能做到這件事的決策樹;

我們也可以使用聯想字詞的技巧,來猜測只拼了一部分的單字。我們從早先的演算法所得到的解決方案,仍然適用於此處;我們再次重新使用了過去的解決方案。

看見無所不在的模式。

大腦的經驗模式

有多少次你抬頭仰望夏日晴空中的雲朵,在雲中發現了胖嘟嘟的動物?或是有多少次你在早餐盤裡新鮮的炒蛋中,發現某個電影明星的臉正在盯著你看?這兩個都是我們大腦嘗試從周遭世界尋找模式的例子。在這些例子中,我們的大腦只是在尋找隨機出現的模式,但我們的大腦還發現其他更為重要的模式——它們甚至能夠幫助我們活下去。

尋找並預測模式,無疑是我們大腦的主要工作,包括嘗試找尋視覺模式讓我們看見物體,或是尋找聽覺模式讓我們聽見聲音。其他模式還包含我們做出的決策、採取的行動等等;這些決定的基礎,來自我們對於之前發生過的事所擁有的經驗模式。我們喜歡模式;模式讓我們覺得舒服。

舉例來説,電視新聞按照固定模式進行:它會告訴我們接下來發生什麼事,接著展示新聞,然後再次提醒我們剛剛播了什麼——這就是我們在觀看電視新聞時經驗到的三個階段。

思考的演算:跟著電腦學思考,你也可以成為計算思考大師
作者: 保羅.科松, 彼得.馬克歐文
譯者: 謝雯伃
出版社:八旗文化
出版日期:2018/04/03