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

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

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

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

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

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

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

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

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

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

二、啟發(fā)式算法

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

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

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

(2)時(shí)間復(fù)雜性。需要多長(zhǎng)時(shí)間可以找到解答？

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

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

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

三、結(jié)語

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

參考文獻(xiàn)：

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

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

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

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