問題和問題求解

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

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

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

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

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

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

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

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

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

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

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

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

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

• 首先對問題要有完整的認識，對求解過程有全面完整的把握，否則只能考慮其他方法。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1  線性和二次多項式擬合數(shù)據(jù)點示例

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

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

圖2  多種擬合示例

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

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

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

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

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

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

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

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

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

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

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

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

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

作者介紹

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