問題解決研究及其智能化歷程

問題解決是思維最一般的形式，它既是一個信息加工過程，同時也是一個學習過程。加工來自環境的信息以做出反應，此過程必須利用主體已有的知識作為基礎；學習是獲得知識、豐富主體所儲存信息的過程，此過程會易化信息加工。分析了問題解決研究的各個階段，介紹了目前在該領域內應用比較廣泛、較為智能的啟發式算法。

問題解決智能化啟發式算法一、問題解決的劃分階段

人是一種高級智能動物，最與眾不同的就是能對遇到的問題進行思考，并且試圖為每一個未知的問題尋找答案，人類社會也就是在這種不懈的求索問題答案的過程中前進。從縱向歷史脈絡看，問題解決作為心理學研究的傳統領域，—度受到廣泛關注，心理學家們從各自的觀點、理論框架和研究范式出發，力圖探討問題解決的心理機制，并在這方面積累了大量的資料。對問題解決的心理學研究大致以20世紀中期的“認知革命”為標志劃分成前、后兩大階段，而后一階段先后發生了一些變化，因此又分成兩個時期。

“認知革命”前，最早用實驗方法研究問題解決的是美國心理學家桑代克，根據他的迷籠實驗，桑代克認為動物解決問題的過程，就是不斷嘗試錯誤的漸進過程。后來，格式塔派心理學家苛勒的黑猩猩接竹竿實驗，讓人們了解到“頓悟”，它往往跟隨在一個階段的嘗試與錯誤之后發生，但這種行為不像桑代克所描述的那樣，而更相似于一種“行為假設”的程序，動物在試驗了這些假設以后，便會拋棄它們。動物只有在清楚地認識到整個問題情境中各種成分之間的關系時，頓悟才可能發生。因此，這是一個知覺的重新組織過程，從模糊的、無組織狀態到有意義、有結構、有組織的狀態。

“認知革命”后的第一個時期，不得不提到一個人——西蒙，諾貝爾經濟獎的獲得者。他不但給經濟領域帶來革新，也為心理學找到了一個全新的視角，從信息加工的取向研究問題解決。西蒙將人比喻為計算機，認為人的問題解決采用信息加工模式，可以執行6種功能：輸入、輸出、存儲、復制符號、建立符號結構、條件性遷移，這是“一個單線的、進行系列活動的系統。這個時期所使用的研究材料，主要是定義良好的語義貧乏問題或轉換問題，如各種版本的“河內塔”問題；研究的內容或目標旨在確定通用的問題解決過程或一般性的策略。另一方面，隨著計算機技術的迅速發展，許多心理學家開始醉心于用計算機編程來分析人類問題解決的過程，編寫的程序可以下棋、診斷病情、為宇宙飛船導航、解答各種復雜的數學問題等，其中許多活動都是與人類問題解決過程極為相似的。問題解決的模式應該包括：

(1)對信息加工系統的結構和能力的完整的描述；

(2)對完成問題解決時所經歷的每一個步驟予以描述。

對這兩方面的描述，要盡可能精確到用計算機能夠模擬的程度。

20世紀80年代進入對知識重視的第二階段。某個領域的專家往往有豐富的專業知識和較高的專業技能，這就構成了專長，人們思考它是如何獲得的，專家和新手在問題解決上有什么差異等。在實際應用方面，結合上述理論作為基礎誕生了專家系統。例如，MYCIN醫療專家系統存放有大量傳染病專家長期積累的知識，通過與許多著名的傳染病專家交談，然后經過推理和總結把得到的知識歸納成500多條規則，采用“IF…THEN…”這種形式存放在計算機中。只要將病人數據送入計算機，系統將外來數據不斷與內部知識進行匹配，直到獲得最終結果。計算機以這種形式大大提高了看病的效率和準確度，在一定程度上使得問題解決更加智能化。

二、啟發式算法

從微觀過程上看，問題解決表現為從初始狀態到目標狀態尋找路徑的過程，即基于狀態空間的路徑搜索。這種路徑搜索概括分為3類:深度優先搜索、寬度優先搜索(或稱廣度優先搜索)和啟發式搜索。前兩種均需在給定的狀態空間中窮舉，以求其中最佳路徑，非常適合狀態空間不大時的求解；但當狀態空間十分大且不預測的情況下則效率極低，甚至不可完成。而啟發式搜索在狀態空間搜索時，對每一個搜索的節點進行評估，得到最佳的節點，再從這個節點進行搜索直到目標節點，可省略大量無謂的搜索路徑，極大提到效率，這使得其在狀態空間較大的領域得到了廣泛應用，如網絡傳輸路徑、自駕車路線、游戲中角色行走路線等。

啟發式算法為了更有效地搜索一個給定的狀態空間，可設計一個估價函數來決定每一次擴展時哪一個節點最有希望到達目標節點，然后搜索就可能沿著這個節點向外擴展。所以，估價函數構造得越準確，則搜索策略越優。一般搜索策略可以通過下面4個準則來評價：

(1)完備性。如果存在一個解答，該策略是否保證能夠找到？

(2)時間復雜性。需要多長時間可以找到解答？

(3)空間復雜性。執行搜索需要多少存儲空間？

(4)最優性。如果存在不同的幾個解答，是否可以發現最高質量的解答？估價函數可表示為：f(n)=g(n)+h(n)：f(n)是節點n的估價函數；g(n)稱為“深度因子”，在狀態空間中從初始節點到節點n的一條最佳路徑的實際代價；h(n)是從節點n到目標節點的一條最佳路徑的估計代價。f(n)的值就是從初始節點開始約束通過節點n的一條最佳路徑的代價，而最小的f(n)值的節點就是所估計的加有最少嚴格約束條件的節點。不難發現，搜索的啟發信息主要由h(n)來體現，因為g(n)是已知的，其代表了搜索廣度的優先趨勢。

A*算法是啟發式算法中到目前為止最快的一種計算最短路徑的算法，如果一個估價函數可以找出最短的路徑，我們稱之為可采納性，h(n)采納就一定能找到最短路徑，但h(n)與實際值h*(n)不能差得太遠。如果差得越遠，A*算法最后的搜索拓撲就接近一個完全的寬度優先搜索，最極端的情況是當h(n)≡0時，A*就完全退化為寬度優先搜索，那么h(n)要可能接近h*(n)。理論上，h(n)=h*(n)是最好的，估計值就是實際值，但在實際中是不可能達到。A*算法中啟發函數h(n)的信息量即為在估計一個結點的值時的約束條件，如果信息越多(或說約束條件越多)，則估價函數越準，排除的結點越多，性能越好。寬度優先搜索之所以不可取，就是因為它的啟發函數h(n)一點啟發信息都沒有。但是，h(n)的信息越多，計算量就越大，耗費的時間也就越多。在實際情況中，通常使用h(n)的實值函數，再通過試驗優化。章沖(2010)通過建模，采用基于三維空間的啟發式搜索A*算法來實現礦井事故救援最優路徑的智能決策。

三、結語

既最好又最快永遠是問題解決追求的目標，是求解過程智能化的最大體現。從試誤到頓悟，到信息加工，到知識結構，到盲目搜索和啟發式搜索，到現在的A*算法，智能化一步步提高。值得注意的是，我們要結合所面臨的問題，在速度和最優中選擇一個平衡點。算法好壞還得根據實際情況，啟發信息在具體問題中要具體分析。研究者可以進一步優化算法，使其效果更加理想。

參考文獻：

\\[1\\]梁寧建.問題解決產生式規則解決物理學問題研究.心理科學，1995，（2）.

\\[2\\]魏唯，歐陽丹彤.結合增量與啟發式搜索的多目標問題處理方法.計算機研究與發展，2010，（47）.

\\[3\\]章沖.基于A-star算法的礦井事故救援研究.成都信息工程學院學報，2010，（25）.

\\[4\\]魏新文.對“問題解決”策略在初中數學教學實踐中的思考.陜西教育，2011，（11）.