正文

一些方法(2)

暗時(shí)間 作者:劉未鵬


3.反過(guò)來(lái)推導(dǎo)。反過(guò)來(lái)推導(dǎo)是一種極其重要的啟發(fā)法,正如前面提到的,Pappus在他的宏篇巨著中將這種手法總結(jié)為解題的最重要手法。實(shí)際上,反向解題隱含了解題中至為深刻的思想:歸約。歸約是一種極為重要的手法,一個(gè)著名的關(guān)于歸約的笑話這樣說(shuō):有一位數(shù)學(xué)家失業(yè)了,去當(dāng)消防員。經(jīng)過(guò)了一些培訓(xùn)之后,正式上任之前,訓(xùn)練的人考他:如果房子失火了怎么辦?數(shù)學(xué)家答出了所有的正確步驟。訓(xùn)練人又問(wèn)他:如果房子沒(méi)失火呢?數(shù)學(xué)家答:那我就把房子點(diǎn)燃,這樣我就把它歸約為了一個(gè)已知問(wèn)題。人類思維本質(zhì)上善于“順著”推導(dǎo),從一組條件出發(fā),運(yùn)用必然的邏輯關(guān)系,得出推論。然而,如果要求的未知量與已知量看上去相隔甚遠(yuǎn),這個(gè)時(shí)候順著推實(shí)際上就是運(yùn)用另一個(gè)啟發(fā)式方法 — 試錯(cuò) — 了。雖然試錯(cuò)是最常用,也是最有效的啟發(fā)法,然而試錯(cuò)卻并不是最高效的。對(duì)于許多題目而言,其要求的結(jié)論本身就隱藏了推論,不管這個(gè)推論是充分的還是必要的,都很可能對(duì)解題有幫助。如果從結(jié)論能夠推導(dǎo)出一個(gè)充要推論,那么實(shí)際上我們就將問(wèn)題進(jìn)行了一次“雙向”歸約,如果原問(wèn)題不容易解決,那么歸約后的問(wèn)題也許就容易解決了,通過(guò)一層層地歸約,讓邏輯的枝蔓從結(jié)論上一節(jié)節(jié)地生長(zhǎng),我們往往會(huì)發(fā)現(xiàn),離已知量越來(lái)越近。此外,即便是從結(jié)論推導(dǎo)出的必要非充分推論(“單向”歸約),對(duì)問(wèn)題也是有幫助的 — 任何不滿足這個(gè)推論的方案都不是問(wèn)題的解。譬如通過(guò)駐點(diǎn)來(lái)求函數(shù)的最值,我們通過(guò)考察函數(shù)的最值(除了函數(shù)邊界點(diǎn)外),發(fā)現(xiàn)它必然有一個(gè)性質(zhì),即在這個(gè)點(diǎn)上函數(shù)的一階導(dǎo)數(shù)為0,雖然一階導(dǎo)數(shù)為0的點(diǎn)未必是最值點(diǎn),但我們可以肯定的是,任何一階導(dǎo)數(shù)不為0的點(diǎn)都可以排除,這就將解空間縮小到了有窮多個(gè)點(diǎn),剩下的只要做做簡(jiǎn)單的排除法,答案就出現(xiàn)了。再譬如線性規(guī)劃中經(jīng)典的單純形算法(又見(jiàn)《Algorithms》⑥),也是通過(guò)對(duì)結(jié)論的考察揭示出只需遍歷有限個(gè)頂點(diǎn)便必然可以到達(dá)最值的。此外很多我們熟知的經(jīng)典題目也都是這種思路的典范,譬如《How To Solve It》上面舉的例子:通過(guò)一個(gè)9升水的桶和一個(gè)4升水的桶在河里取6升水。這個(gè)題目通過(guò)正向試錯(cuò),很快也能發(fā)現(xiàn)答案,然而通過(guò)反向歸約,則能夠不偏不倚的命中答案。另一些我們耳熟能詳?shù)念}目也是如此,譬如:100根火柴,兩個(gè)人輪流取,每個(gè)人每次只能取1~7根,誰(shuí)拿到最后一根火柴誰(shuí)贏;問(wèn)有必勝策略嗎,有的話是先手還是后手必勝?這個(gè)問(wèn)題通過(guò)試錯(cuò)就不是那么容易發(fā)現(xiàn)答案了。同樣,這個(gè)問(wèn)題的推廣被收錄在《編程之美》⑦里面:兩堆橘子,各為m和n個(gè),兩人輪流拿,拿的時(shí)候你只能選擇某一堆在里面拿(即不能跨堆拿),你可以拿1~這堆里面所有剩下的橘子,誰(shuí)拿到最后一個(gè)橘子誰(shuí)贏;問(wèn)題同上。算法上面很多聰明的算法也都是通過(guò)考察所求結(jié)論隱藏的性質(zhì)來(lái)減小復(fù)雜度的,譬如剛才提到的單純形問(wèn)題,譬如經(jīng)典面試題“名人問(wèn)題”、“和最?。ù螅┑倪B續(xù)子序列”,等等。倒推法之所以是一種極為深刻的思維方法,本質(zhì)上是因?yàn)樗浞掷昧祟}目中一個(gè)最不易被覺(jué)察到的信息 — 結(jié)論。結(jié)論往往蘊(yùn)含著豐富的條件,譬如對(duì)什么樣的解才是滿足題意的解的約束。一般來(lái)說(shuō),借助結(jié)論中蘊(yùn)含的知識(shí),我們便可以更為“智能地”搜索解空間。舉一個(gè)直白的例子,有人要你在地球上尋找一棟滿足如下條件的建筑:__層高(填空自己填),__風(fēng)格,__年代始建,…… (省略若干約束條件)。對(duì)于這樣一個(gè)問(wèn)題,最平凡的解法是窮舉地球上每一棟建筑,直到遇到一個(gè)滿足條件的為止。而更“智能”的(或者說(shuō)更“啟發(fā)”的)方法則是充分利用題目里面的約束信息,譬如假若條件里面說(shuō)要60層樓房,你就不會(huì)去非洲找,如果要拜占庭風(fēng)格的,你估計(jì)也不會(huì)到中國(guó)來(lái)找,如果要始建于很早的年代的,你也不會(huì)去非常新建的城市里面去找,等等。倒推法是如此的重要,以至于笛卡爾當(dāng)時(shí)認(rèn)為可以把一切問(wèn)題歸結(jié)為求解代數(shù)方程組,笛卡爾的萬(wàn)能解題法就是首先將問(wèn)題轉(zhuǎn)化為代數(shù)問(wèn)題,然后設(shè)出未知數(shù),列出方程,最后解這組(個(gè))方程。其中設(shè)未知數(shù)本質(zhì)上就是一種倒推:通過(guò)設(shè)出一個(gè)假想的結(jié)論x,來(lái)將題目對(duì)x的需求表達(dá)出來(lái),然后順勢(shì)而下推導(dǎo)出x。仔細(xì)想想設(shè)未知數(shù)這種手法所蘊(yùn)含的深刻思想,也就難怪笛卡爾會(huì)認(rèn)為它是那個(gè)解決所有問(wèn)題的一般性鑰匙了。


上一章目錄下一章

Copyright ? 讀書網(wǎng) m.ranfinancial.com 2005-2020, All Rights Reserved.
鄂ICP備15019699號(hào) 鄂公網(wǎng)安備 42010302001612號(hào)