問題和問題求解

實(shí)際問題千變?nèi)f化，我們考慮一種抽象的統(tǒng)一說法：一個(gè)問題就是從一個(gè)實(shí)例描述集合到解集合的映射，。如果I是有窮集，T 就是有窮問題，否則 T 是無窮問題。或稱為問題 T 的實(shí)例，o=T(i ) 稱為問題T 對(duì)應(yīng)i 的解。

計(jì)算機(jī)只會(huì)做一件事，就是自動(dòng)執(zhí)行程序。用計(jì)算機(jī)解決一個(gè)問題，就要寫出一個(gè)解決這個(gè)問題的有窮程序（無窮長(zhǎng)的程序?qū)懖煌辏Ｈ绻槍?duì)問題T 寫了程序P，把T 的任意實(shí)例i作為P 的輸入，P 的輸出總是o=T(i )，我們就可以說P 解決了問題T。

針對(duì)問題寫出程序是計(jì)算機(jī)領(lǐng)域最重要的工作。要完成這種工作，首先要確定一種技術(shù)路線（一種方法），確定需要從問題中挖掘出什么信息（知識(shí)），怎樣利用得到的知識(shí)構(gòu)造程序。參考幾十年的研究和實(shí)踐，本文總結(jié)出三類方法。是否還有第四類？請(qǐng)讀者考慮。

基于算法的系統(tǒng)(Algorithm-Based Systems, ABS)

這個(gè)太顯然。但是，采用這一方法有什么前提條件？在什么情況下有可能得到解決問題的算法，并實(shí)際寫出能解決問題的程序？我們可以提出下面一些條件。

首先，該問題必須是“可計(jì)算的”，這是理論要求。證明問題是否可計(jì)算常常很不容易，但做出算法就是正面的證明。其次，要做出算法，要求我們對(duì)問題及其求解完全理解，知道如何處理問題的任意實(shí)例，能處理求解過程中可能遇到的任何情況。

算法的優(yōu)點(diǎn)是直接針對(duì)具體問題，是專用的，因此效率高。另一方面，我們比較容易把算法轉(zhuǎn)換為解決問題的程序，也比較容易判斷一個(gè)程序是否確實(shí)解決了問題。

注意：任何有窮問題都有算法。由于情況（輸入）有窮，理論上總是可以對(duì)其做窮盡分析，分情況給出解。求解程序如下（假定問題只有n 個(gè)實(shí)例，x 是輸入）：

無窮問題也可能寫出有窮算法，例如求最大公約數(shù)問題。

現(xiàn)在看看用計(jì)算機(jī)下圍棋的問題。圍棋要求對(duì)弈雙方在19×19的棋盤上交替落子，目標(biāo)是占據(jù)最大的地盤。下圍棋程序只需要解決一個(gè)問題：對(duì)任何棋局，確定下一個(gè)棋子的最佳位置。由于局面有窮，本問題為有窮問題。按前面的說法，存在確定最佳位置的算法?；谶@一算法的圍棋程序絕不會(huì)犯錯(cuò)，其棋力不會(huì)弱于（昨天、今天或未來的）任何棋手，或任何下圍棋的程序，包括AlphaGo和AlphaZero。

我們很容易規(guī)劃出一套寫這個(gè)算法的系統(tǒng)化方法，只要有充分的耐心和時(shí)間，就能做出一個(gè)這樣的圍棋程序。但是，由于可能局面太多（約為3³⁶¹≈10¹⁷²），徹底分析每個(gè)局面需要的時(shí)間太長(zhǎng)，這一工作不可能在合理的時(shí)間內(nèi)完成。另一方面，即使能寫出來，程序也太長(zhǎng)，計(jì)算機(jī)沒有足夠的存儲(chǔ)器存放它。這一實(shí)例說明，理論上有算法，但并不代表能用算法解決問題。

算法的另一個(gè)限制是計(jì)算機(jī)專業(yè)人士最熟悉的：必須足夠高效（復(fù)雜性不高），保證每次執(zhí)行可以在合理時(shí)間內(nèi)完成。例如，如果一個(gè)圍棋程序在求解中，需要檢查的局面?zhèn)€數(shù)可能達(dá)到10¹⁷²，則這個(gè)程序（實(shí)際上）毫無意義。

下面是能用算法解決問題的一些條件：

• 首先對(duì)問題要有完整的認(rèn)識(shí)，對(duì)求解過程有全面完整的把握，否則只能考慮其他方法。

• 建模后得到的抽象問題是可計(jì)算的（理論條件），否則只能考慮解決原問題的恰當(dāng)?shù)目捎?jì)算子問題，或降低要求，解決結(jié)果類似但要求較低的問題。

• 算法存在有窮長(zhǎng)度的描述，而且描述不“過于長(zhǎng)”，可在合理時(shí)間內(nèi)寫完。

• 每個(gè)實(shí)例的求解都能在合理時(shí)間內(nèi)完成。如果效率太低，只能設(shè)法找其他算法，或收縮問題（解決合適的子問題），或降低要求，如最優(yōu)解改為近似解等。

如果找不到算法，或者雖然有算法但不適用，我們就只能考慮其他方法。

基于搜索的系統(tǒng)(Searching-Based Systems, SBS)

用計(jì)算機(jī)解決問題的另一類方法是搜索，也就是通過探查和回溯的方法尋找解。搜索方法并不要求我們對(duì)問題及其求解過程有全面的認(rèn)識(shí)，但需要有一些清晰的知識(shí)片段，以這些知識(shí)片段作為搜索的基礎(chǔ)。例如，對(duì)基于規(guī)則的系統(tǒng)，需要有針對(duì)問題的規(guī)則庫；自動(dòng)推理需要有事實(shí)和推理規(guī)則?；谒阉鞯南到y(tǒng)由兩部分組成：一部分是針對(duì)問題的知識(shí)庫，包含一集知識(shí)片段（規(guī)則）；一部分是搜索算法，它設(shè)法利用知識(shí)庫去拼湊出實(shí)例的解。

人工智能領(lǐng)域研究過許多搜索方法，開發(fā)了一些通用框架（如產(chǎn)生式系統(tǒng)、黑板系統(tǒng)）；提出了許多技術(shù)（如各種啟發(fā)式搜索算法），實(shí)現(xiàn)了一些應(yīng)用（如基于規(guī)則的專家系統(tǒng)）；提出了一些編程泛型（如邏輯程序設(shè)計(jì)、約束程序設(shè)計(jì)）。還有自動(dòng)推理、定理證明等方面的大量研究和成果。赫伯特·西蒙（司馬賀）等人稱搜索為通用問題求解(general problem solving)方法。

只有解決問題的片段知識(shí)（規(guī)則），通常做不出算法。規(guī)則可能不完全，無法處理所有實(shí)例或所有情況，也沒有處理策略（順序和過程）。但規(guī)則可以用于搜索，通過試探和回溯的方式去求解。搜索的特點(diǎn)是，算法不直接針對(duì)問題，而是針對(duì)規(guī)則的使用。規(guī)則可獨(dú)立描述，也可以嵌入搜索算法中。搜索也已廣泛用于實(shí)踐，例如自動(dòng)泊車系統(tǒng)常包含搜索。

關(guān)于計(jì)算機(jī)下棋的研究已有幾十年歷史，基本方法就是博弈樹搜索，評(píng)價(jià)各種可能，選出最佳棋著。圍棋的規(guī)則很簡(jiǎn)單，很容易實(shí)現(xiàn)一個(gè)基于搜索的圍棋程序。為此，我們只需實(shí)現(xiàn)一個(gè)處理博弈的通用搜索引擎，讓它用圍棋規(guī)則去做窮盡搜索，找出最佳棋著。

當(dāng)然，稍微了解計(jì)算機(jī)的人都會(huì)說上述方案不可行。規(guī)模為10¹⁷²的狀態(tài)空間太大，樸素搜索方法實(shí)際無用。這個(gè)不可行的原因是實(shí)際計(jì)算開銷，而不是理論不正確。這也說明了搜索方法的一個(gè)重要弱點(diǎn)：求解中需要探查的空間通常以相對(duì)于實(shí)例規(guī)模的指數(shù)方式增長(zhǎng)。因此，對(duì)復(fù)雜一些的問題或規(guī)模較大的實(shí)例，我們可能無法等到結(jié)果。

實(shí)際圍棋程序（包括AlphaGo和AlphaZero）都采用了一些策略，如限制最大搜索深度（或限制搜索時(shí)間），加入隨機(jī)性因素等。設(shè)法在不能窮盡搜索的情況下合理地評(píng)估局面，只能評(píng)估檢查到的那些局面，并從中選擇可能通向“最佳路徑”的棋著等。

搜索方法的優(yōu)勢(shì)是有可能利用部分知識(shí)解決問題，但也存在許多固有的缺陷：

• 搜索策略或規(guī)則選擇策略不當(dāng)，可能使搜索進(jìn)入無窮的或巨大的無解區(qū)域，導(dǎo)致實(shí)際有解，但卻（很長(zhǎng)時(shí)間）找不到。也難保證對(duì)不同實(shí)例的（時(shí)間）行為一致性。

• 搜索狀態(tài)爆炸的本質(zhì)性問題。

• 規(guī)則集不完全，可能導(dǎo)致某些實(shí)例無法求解；而規(guī)則集越大，狀態(tài)爆炸問題越嚴(yán)重（規(guī)則集豐富表示對(duì)問題的認(rèn)識(shí)豐富。這是搜索方法的一個(gè)固有矛盾）。

假設(shè)有了一集規(guī)則，在采用基于搜索的方法時(shí)，需要考慮搜索策略（寬度優(yōu)先、深度優(yōu)先、其他），規(guī)則選擇策略（固定順序、估值序、隨機(jī)等），還需考慮狀態(tài)評(píng)估，可能的剪枝策略，局部搜索（限制搜索深度、與評(píng)估結(jié)合）等問題。

基于實(shí)例的系統(tǒng)(Case-Based Systems, CBS)

如果對(duì)問題的了解非常少，或基本上沒有有關(guān)求解的知識(shí)，還能用計(jì)算機(jī)嗎？實(shí)際情況經(jīng)常如此：我們認(rèn)為面臨的是一個(gè)問題，有需要處理的情況，人能得到有用的結(jié)果。例如，醫(yī)生看了檢查報(bào)告說“可能××有炎癥”，或圍棋大師看到一個(gè)局面說“感覺不錯(cuò)”。

假設(shè)我們“認(rèn)定”了一組輸入和結(jié)果是一個(gè)問題的實(shí)例，就可能實(shí)現(xiàn)一個(gè)簡(jiǎn)單的求解程序（設(shè)x 為輸入）：

這個(gè)程序與前面類似，但本質(zhì)不同。這里的實(shí)例可能只是所有可能實(shí)例中的一部分。

人們通常不滿意這種“死記硬背”，希望推而廣之，這樣就需要“歸納”或“學(xué)習(xí)”。用計(jì)算機(jī)自動(dòng)推廣就是“機(jī)器學(xué)習(xí)”，也就是第三種方法——基于（實(shí)例）學(xué)習(xí)的求解方法，設(shè)法通過自動(dòng)處理一些“情況-解”實(shí)例，得到一個(gè)能處理該問題的更多實(shí)例的系統(tǒng)。

用機(jī)器學(xué)習(xí)方法解決問題，需要設(shè)計(jì)一種具有可調(diào)整要素的（數(shù)據(jù)）結(jié)構(gòu)S，一個(gè)（能利用實(shí)例調(diào)整S 的）學(xué)習(xí)算法L，和一個(gè)使用S 解決問題的算法U。對(duì)已有的實(shí)例集E，學(xué)習(xí)算法得到L(E, S ) = S'，而U[S'] 就是利用調(diào)整后的結(jié)構(gòu)解決問題的程序。學(xué)習(xí)算法L有效，首先要求將U[S'] 應(yīng)用于E中的實(shí)例輸入時(shí)，得到的結(jié)果近似于。

例如，多層神經(jīng)網(wǎng)絡(luò)是目前常用的一種結(jié)構(gòu)，其中的可調(diào)整要素就是神經(jīng)元之間的連接系數(shù)。針對(duì)這種結(jié)構(gòu)，人們提出了一些學(xué)習(xí)算法，該結(jié)構(gòu)的使用算法很簡(jiǎn)單。

復(fù)雜性使我們無法通過窮盡搜索的方法評(píng)價(jià)圍棋棋局。以前人們利用專家知識(shí)做評(píng)價(jià)，主觀而且不準(zhǔn)確。AlphaGo的創(chuàng)新就在于通過機(jī)器學(xué)習(xí)自動(dòng)產(chǎn)生評(píng)價(jià)函數(shù)。AlphaZero和AlphaGo的差異在于學(xué)習(xí)實(shí)例的來源，AlphaGo用歷史上的圍棋實(shí)戰(zhàn)作為實(shí)例，AlphaZero用自對(duì)弈棋局作為實(shí)例。結(jié)合其他機(jī)制，Alpha系列程序取得了令人矚目的戰(zhàn)績(jī)。

實(shí)際上，機(jī)器學(xué)習(xí)就是用某一類函數(shù)去“擬合”一組數(shù)據(jù)。數(shù)學(xué)抽象就是：有一組數(shù)據(jù)和一個(gè)函數(shù)類，設(shè)法找到能最好地表達(dá)這組數(shù)據(jù)的函數(shù)表示。圖1是一個(gè)用線性和二次多項(xiàng)式擬合幾個(gè)數(shù)據(jù)點(diǎn)的例子。那么，哪個(gè)結(jié)果更好地表達(dá)了數(shù)據(jù)中蘊(yùn)含的關(guān)系呢？

圖1  線性和二次多項(xiàng)式擬合數(shù)據(jù)點(diǎn)示例

我們的目標(biāo)是希望擬合得到的函數(shù)能用于處理其他實(shí)例。但是，目前對(duì)問題的理解只有這一組數(shù)據(jù)（而且數(shù)據(jù)可能有誤差），因此我們無法回答“哪一個(gè)更好”這個(gè)問題。

對(duì)具體的基函數(shù)組，可以設(shè)計(jì)一種評(píng)價(jià)標(biāo)準(zhǔn)（某種最小偏差）。而對(duì)這組數(shù)據(jù)的擬合，則無法確認(rèn)這種標(biāo)準(zhǔn)。真正的標(biāo)準(zhǔn)應(yīng)該來自問題，基于對(duì)被處理問題的全面理解。只有目前這組實(shí)例，不可能做出“正確”判斷。即使擬合函數(shù)對(duì)現(xiàn)有數(shù)據(jù)都完全重合，也未必是最好的預(yù)測(cè)。例如，對(duì)4項(xiàng)數(shù)據(jù)可以做一個(gè)3次多項(xiàng)式，使之經(jīng)過每個(gè)點(diǎn)。圖2表示了擬合函數(shù)的情況。人們一般都不認(rèn)為這個(gè)擬合更好。

圖2  多種擬合示例

對(duì)函數(shù)擬合的研究提出了兩個(gè)重要情況。欠擬合：由于函數(shù)結(jié)構(gòu)太簡(jiǎn)單，無法反映問題的重要特征，對(duì)應(yīng)于機(jī)器學(xué)習(xí)中使用的結(jié)構(gòu)過于簡(jiǎn)單。過擬合：函數(shù)類過于豐富，反映具體實(shí)例的過多細(xì)節(jié)，掩蓋了目標(biāo)問題的本質(zhì)性特征，對(duì)應(yīng)于機(jī)器學(xué)習(xí)中使用的結(jié)構(gòu)過于復(fù)雜，導(dǎo)致結(jié)果函數(shù)震蕩劇烈，降低了學(xué)習(xí)結(jié)果的預(yù)測(cè)能力。從有關(guān)函數(shù)擬合的討論中，可以看到學(xué)習(xí)方法固有的局限性：由于沒有對(duì)問題的完整理解，我們無法討論學(xué)習(xí)結(jié)果的正確性，只能問得到的結(jié)果“好不好”，而“好不好”也只能通過實(shí)例來檢驗(yàn)。

常見檢驗(yàn)方法有兩種：一種是在真實(shí)世界里檢驗(yàn)，例如自動(dòng)駕駛，只能在實(shí)際道路上試驗(yàn)，希望車輛不出事故、不撞車、不撞物撞人等。另一種方法是把已有實(shí)例分為不相交的兩部分R = R1 ⊕ R2，其中的R1用于學(xué)習(xí)，R2用于檢驗(yàn)學(xué)習(xí)效果。

實(shí)際上，基于學(xué)習(xí)的方法還有一些未說明的假設(shè)，只有在這些條件下，學(xué)習(xí)方法才可能有效：首先是假設(shè)問題實(shí)例和解的關(guān)系是連續(xù)的；其次是假設(shè)每個(gè)樣本（實(shí)例和解）都必定包含了一些反映問題的整體性質(zhì)的全局信息，因此樣本越多越好，信息越多偏差越小。實(shí)際上，這些假定都是有疑問的。另外，在不理解問題的情況下，這些條件都無法檢查。因此機(jī)器學(xué)習(xí)系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)有很大的主觀性和試探性，最后只能是“結(jié)果決定一切”。

基于（實(shí)例）學(xué)習(xí)系統(tǒng)的另一個(gè)缺點(diǎn)是學(xué)習(xí)代價(jià)可能很高。例如，AlphaGo采用超級(jí)計(jì)算機(jī)，學(xué)習(xí)中對(duì)弈超過3000萬盤。AlphaGo Zero自對(duì)弈3天（約500萬盤），水平可超越之前的AlphaGo，自對(duì)弈30天可以超越后來的AlphaGo Master版本。由于圍棋的特點(diǎn)，實(shí)例易得。但很多問題難以得到大量實(shí)例，采用這種技術(shù)路線的有效性存疑。

根據(jù)上面討論，我們可以總結(jié)出適合用機(jī)器學(xué)習(xí)求解的問題的一些特點(diǎn)。首先，問題具有信息完全的場(chǎng)景（靜態(tài)的、公開的）。一些棋類有這種性質(zhì)，包括圍棋，但許多問題不是這樣。其次，存在（或容易得到）大量可用實(shí)例。圍棋有很多積累，而且容易自動(dòng)生成。再次，學(xué)習(xí)效果比較容易判斷。例如圍棋的勝負(fù)和統(tǒng)計(jì)可以作為評(píng)價(jià)。最后，由于學(xué)習(xí)結(jié)果的不可控性，機(jī)器學(xué)習(xí)慎用于安全攸關(guān)的應(yīng)用（否則就需要其他安全措施）。

目前機(jī)器學(xué)習(xí)領(lǐng)域非常熱，許多研究者和企業(yè)投入其中，也有一些原因：首先是做出了一些有影響的實(shí)例，特別是AlphaGo及其后續(xù)工作；再就是已經(jīng)取得了一些成果，使人們看到一些用傳統(tǒng)方法不能處理的問題有了新的解決途徑。人類不清楚如何解決的問題大量存在，因此存在豐富的有可能用機(jī)器學(xué)習(xí)去探索的問題和應(yīng)用領(lǐng)域。隨著有關(guān)研究工作的開展，人們也開發(fā)出各種與神經(jīng)網(wǎng)絡(luò)類似或有些不同的模型，這些情況都推動(dòng)著機(jī)器學(xué)習(xí)領(lǐng)域研究和應(yīng)用的開展。另一方面，計(jì)算機(jī)能力增強(qiáng)也是機(jī)器學(xué)習(xí)取得進(jìn)展的重要原因。

但學(xué)習(xí)方法屬于試探性方法，類似于實(shí)驗(yàn)科學(xué)，與計(jì)算機(jī)科學(xué)技術(shù)的常規(guī)方法距離比較遠(yuǎn)。通過學(xué)習(xí)，從實(shí)例得到的結(jié)果能外推到什么程度，實(shí)際上是不清楚的。因此，機(jī)器學(xué)習(xí)方法更適合于那些只有優(yōu)良程度要求（而非判定性要求）的應(yīng)用。例如：要求精確結(jié)果的整函數(shù)通常無法學(xué)習(xí)，如斐波那契函數(shù)、最大公因子等。我們也應(yīng)該注意機(jī)器學(xué)習(xí)的性質(zhì)和本質(zhì)弱點(diǎn)，避免可能的危害。

三種方法的比較和總結(jié)

從前提條件看：采用算法，需要有對(duì)問題及其求解的完整知識(shí)；采用搜索方法，需要有對(duì)問題及其求解的片段知識(shí)；采用學(xué)習(xí)方法，只需要問題和解的實(shí)例，無需其他知識(shí)。

從技術(shù)上看：算法只需要一個(gè)直面問題的解決方案；采用搜索，通過一個(gè)間接的搜索算法去應(yīng)用有關(guān)問題的片段知識(shí)。學(xué)習(xí)方法需要一個(gè)結(jié)構(gòu)和兩個(gè)算法：一個(gè)具有可調(diào)要素的結(jié)構(gòu)承載學(xué)習(xí)結(jié)果，一個(gè)利用實(shí)例調(diào)整該結(jié)構(gòu)的算法和一個(gè)利用該結(jié)構(gòu)處理實(shí)例的算法。

從效果看：正確的算法必定給出正確的解，求解效率可以預(yù)估，但也有復(fù)雜性太高的可能性。由于知識(shí)有限，搜索方法通常不能保證得到解，得到解的代價(jià)也很難預(yù)估，但有可能保證解的正確性。另一方面，搜索通常不能保證得到一個(gè)解。由于知識(shí)貧乏，我們只能說學(xué)習(xí)方法得到的結(jié)果可能有用，其他方面都沒有保證。

可見，這三類方法各有各的前提條件、優(yōu)勢(shì)，以及固有的缺陷。遇到一個(gè)問題時(shí)，我們應(yīng)該根據(jù)對(duì)問題的潛在認(rèn)識(shí)程度、問題的實(shí)際需要等選擇合適的求解方法。

請(qǐng)注意，為了簡(jiǎn)單起見，本文對(duì)各方面情況做了極度簡(jiǎn)化。實(shí)際應(yīng)用這些方法時(shí)可能有很大變化，也完全可能在一個(gè)求解系統(tǒng)里融合了多種方法的要素，特此說明。

作者介紹

裘宗燕 CCF杰出會(huì)員，CCF中小學(xué)計(jì)算機(jī)教育發(fā)展委員會(huì)委員。北京大學(xué)數(shù)學(xué)學(xué)院信息科學(xué)系教授（退休）。主要研究方向?yàn)檐浖碚?、程序設(shè)計(jì)語言及其理論基礎(chǔ)、形式化方法等。