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

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

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

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

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

(1)對信息加工系統(tǒng)的結(jié)構(gòu)和能力的完整的描述；

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

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

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

二、啟發(fā)式算法

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

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

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

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

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

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

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

三、結(jié)語

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

參考文獻：

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

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

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

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