姓名：車文揚(yáng) 學(xué)號(hào)：16020199006 ?轉(zhuǎn)載自：https://www.cnblogs.com/sddai/p/5644011.html

【嵌牛導(dǎo)讀】：啟發(fā)式算法的詳解

【嵌牛鼻子】：啟發(fā)式算法

【嵌牛提問】：啟發(fā)式算法有什么作用？

【嵌牛正文】：

（一）物理符號(hào)系統(tǒng)?

1 定性結(jié)構(gòu)定律（Laws of Qualitative Structure）?

All sciences characterize the essential nature of the systems they study. These characterizations are invariably qualitative in nature, for they set the terms within which more detailed knowledge can be developed. Their essence can often be captured in very short, very general statements. One might judge these general laws, due to their limited specificity, as making relatively little contribution to the sum of a science, were it not for the historical evidence that shows them to be results of the greatest importance.?

在研究某個(gè)系統(tǒng)的時(shí)侯烂完，我們可以建立一個(gè)簡單而容易理解的模型來定性地描述這個(gè)系統(tǒng)的性質(zhì)试疙。就像生物學(xué)中的細(xì)胞學(xué)說，一切生物都是由細(xì)胞組成的抠蚣，但任何一種生物的細(xì)胞都有極其復(fù)雜的種類祝旷、形態(tài)和功能。但我們可以建立一個(gè)標(biāo)準(zhǔn)的細(xì)胞模型：細(xì)胞由細(xì)胞核嘶窄、細(xì)胞質(zhì)和細(xì)胞膜組成怀跛，細(xì)胞核中有遺傳物質(zhì)，細(xì)胞質(zhì)中有各種行使不同功能的細(xì)胞器柄冲，細(xì)胞膜包在細(xì)胞質(zhì)外面吻谋，負(fù)責(zé)細(xì)胞核環(huán)境的物質(zhì)交換和信息交流。在此基礎(chǔ)上研究各種細(xì)胞的形態(tài)結(jié)構(gòu)和功能就都顯得比較簡單了现横。同樣的道理漓拾，“智能”是個(gè)相當(dāng)抽象的、讓人有點(diǎn)無從下手的研究對象长赞，物理符號(hào)系統(tǒng)就是一個(gè)用以描述智能的晦攒，（相對來說）簡單而容易理解的模型。?

2 物理符號(hào)系統(tǒng)的定義?

物理符號(hào)系統(tǒng)是“物理的”得哆，就是說它是遵循物理定律的，而且能用工程技術(shù)手段來實(shí)現(xiàn)哟旗，比如說你的計(jì)算機(jī)贩据；它是一種“符號(hào)”系統(tǒng)栋操，但不局限于人類的符號(hào)系統(tǒng)。?

物理符號(hào)系統(tǒng)包括符號(hào)(symbols)饱亮、表達(dá)式(expressions)和過程(Processes)矾芙。符號(hào)是一種物理模式，是實(shí)體近上。符號(hào)組合起來就成了表達(dá)式剔宪，這里的組合方式可以是多種多樣的。系統(tǒng)在任一時(shí)刻都包含著這樣一些表達(dá)式壹无。過程可以作 用于表達(dá)式來對表達(dá)式進(jìn)行創(chuàng)造(creation)葱绒、修正(modification)、再生(reproduction)或破壞 (destruction)斗锭。然而地淀，物理符號(hào)系統(tǒng)內(nèi)的表達(dá)式本身并不能描述一切對象(Such a system exists in a world of objects wider than just these symbolic expressions themselves.不知道可不可以這樣理解)。?

兩個(gè)核心概念：指稱(designation)和解釋(interpretation)?

Designation. An expression designates an object if, given the expression, the system can either affect the object itself or behave in ways dependent on the object.?

Interpretation. The system can interpret an expression if the expression designates a process and if, given the expression, the system can carry out the process.?

Interpretation implies a special form of dependent action: given an expression the system can perform the indicated process, which is to say, it can evoke and execute its own processes from expressions that designate them.?

個(gè)人理解：指稱表示的是一種表達(dá)式與對象的對應(yīng)關(guān)系岖是，就像指針一樣帮毁。解釋（或者譯成翻譯、說明）表示的是一種表達(dá)式與過程的對應(yīng)關(guān)系豺撑，系統(tǒng)可以通過一些表達(dá)式來執(zhí)行相應(yīng)的過程烈疚。?

從定義來看，物理符號(hào)系統(tǒng)與一切通用計(jì)算機(jī)極為相似聪轿，它實(shí)際上也確實(shí)不是什么新的東西爷肝。很多已知的系統(tǒng)都具有這樣的特征，其中最明顯的有兩個(gè)：計(jì)算機(jī)和人腦屹电。?

3 物理符號(hào)系統(tǒng)假設(shè)：物理符號(hào)系統(tǒng)是智能活動(dòng)的充要條件?

The Physical Symbol System Hypothesis：A physical symbol system has the necessary and sufficient means for general intelligent action.?

By "necessary" we mean that any system that exhibits general intelligence will prove upon analysis to be a physical symbol system. By "sufficient" we mean that any physical symbol system of sufficient size can be organized further to exhibit general intelligence. By "general intelligent action" we wish to indicate the same scope of intelligence as we see in human action: that in any real situation behavior appropriate to the ends of the system and adaptive to the demands of the environment can occur, within some limits of speed and complexity.?

其中阶剑，“必要性”的證明是認(rèn)知科學(xué)的任務(wù)，也就是研究人類（或動(dòng)物）的認(rèn)知行為危号，然后用物理符號(hào)系統(tǒng)來解釋這些認(rèn)知行為牧愁。“充分性”是人工智能的任務(wù)外莲，也就是構(gòu)造一些物理符號(hào)系統(tǒng)猪半，看它們能否產(chǎn)生智能。?

西蒙和紐厄爾把信息加工理論引入心理學(xué)偷线，成為信息加工心理學(xué)磨确，也就是認(rèn)知科學(xué)。人工智能的研究離不開認(rèn)知科學(xué)研究中提出的各種假設(shè)声邦。?

剛開始乏奥，人們構(gòu)造一些簡單的程序來讓計(jì)算機(jī)完成一些簡單的、精心設(shè)計(jì)的任務(wù)亥曹，后來覺得不過癮邓了，就把研究工作擴(kuò)展到了建立系統(tǒng)恨诱，如自然語言理解系統(tǒng)、模式識(shí)別系統(tǒng)骗炉、設(shè)計(jì)系統(tǒng)等照宝。但是——?

It would be surprising and unappealing if it turned out that the AI programs performing these diverse tasks had nothing in common beyond their being instances of physical symbol systems. Hence, there has been great interest in searching for mechanisms possessed of generality, and for common components among programs performing a variety of tasks. This search carries the theory beyond the initial symbol system hypothesis to a more complete characterization of the particular kinds of symbol systems that are effective in artificial intelligence.?

完成這些形形色色的任務(wù)的程序之間有沒有什么共性？找到了這些共性句葵，就意味著對智能有了更深層的理解厕鹃。?

In the second section of this paper, we will discuss one example of a hypothesis at this second level specificity: the heuristic search hypothesis（啟發(fā)式搜索假設(shè)）.?

（二）啟發(fā)式搜索?

系統(tǒng)的智能活動(dòng)是通過問題解決來體現(xiàn)的，系統(tǒng)是通過啟發(fā)式搜索來解題的乍丈。啟發(fā)式搜索假設(shè)是AI的第二個(gè)定性結(jié)構(gòu)定律（第一個(gè)是物理符號(hào)系統(tǒng)）剂碴。?

1 啟發(fā)式搜索假設(shè)?

Heuristic Search Hypothesis. The solutions to problems are represented as symbol structures. A physical symbol system exercises its intelligence in problem solving by search--that is, by generating and progressively modifying symbol structures until it produces a solution structure.?

問題的解也是符號(hào)結(jié)構(gòu)。物理符號(hào)系統(tǒng)解決問題的過程就是產(chǎn)生某種符號(hào)結(jié)構(gòu)诗赌，再一步一步的修正它汗茄，直到它與問題的解的結(jié)構(gòu)相一致。就像解方程AX+B=CX+D一樣铭若，移項(xiàng)得（A-C）X=D-B洪碳，再消去系數(shù)（A-C），得到X=（D-B）/（A-C）叼屠。這就是逐步修正方程的結(jié)構(gòu)瞳腌，最終得到符合X=E的形式的解的過程。?

假如有無限的時(shí)間和存儲(chǔ)空間還后無限的能量供應(yīng)镜雨，那么系統(tǒng)總可以通過窮舉的方式嫂侍，遍歷問題空間中的所有路徑來找到問題的解——這就是傳說中的蠻力搜索。但實(shí)際應(yīng)用中這顯然是不可能的荚坞。實(shí)際應(yīng)用中必須在有限的步驟中挑宠，有限的時(shí)間內(nèi)找到答案，因此就要用啟發(fā)式搜索策略颓影。?

A condition, then, for the appearance of intelligence is that the distribution of solutions be not entirely random, that the space of symbol structures exhibit at least some degree of order and pattern. A second condition is that pattern in the space of symbol structures be more or less detectible. A third condition is that the generator of potential solutions be able to behave differentially, depending on what pattern it detected. There must be information in the problem space, and the symbol system must be capable of extracting and using it.?

符號(hào)系統(tǒng)處于完全混沌的狀態(tài)時(shí)各淀，是不可能表現(xiàn)出智能的。符號(hào)系統(tǒng)的智能體現(xiàn)在它能夠從問題空間中抽取信息诡挂，并運(yùn)用這些信息指導(dǎo)搜索碎浇，從而避開錯(cuò)誤的方向，避免迂回曲折的分叉而高效的解決問題璃俗。所以奴璃，問題空間中必須包含信息瞳秽，或者說砰识，包含某種程度的秩序和結(jié)構(gòu)何什。?

實(shí)際中需要解決的問題不像解一元一次方程那樣只有一條路對應(yīng)一個(gè)固定的解丈屹，而是在每一步都有多種選擇归形，對應(yīng)著多個(gè)結(jié)局邮府，形成一棵搜索樹单默。?

The fact of limited resources allows us, for most purposes, to view a symbol system as though it were a serial, one-process-at-a-time device. If it can accomplish only a small amount of processing in any short time interval, then we might as well regard it as doing things one at a time. Thus "limited resource symbol system" and "serial symbol system" are practically synonymous. The problem of allocating a scarce resource from moment to moment can usually be treated, if the moment is short enough, as a problem of scheduling a serial machine.?

這里好像是說由于資源有限抛猖，在實(shí)際應(yīng)用中是按照線性過程在進(jìn)行搜索的魏颓，是串行的岭辣，一次只能沿著搜索樹的一個(gè)分支走。（不過甸饱，有沒有“多線程”的并行搜索呢沦童？）?

In serial heuristic search, the basic question always is: what shall be done next? In tree search, that question, in turn, has two components: (1) from what node in the tree shall we search next, and (2) what direction shall we take from that node? Information helpful in answering the first question may be interpreted as measuring the relative distance of different nodes from the goal. Best-first search calls for searching next from the node that appears closest to the goal. Information helpful in answering the second question--in what direction to search--is often obtained, as in the algebra example, by detecting specific differences between the current nodal structure and the goal structure described by the test of a solution, and selecting actions that are relevant to reducing these particular kinds of differences. This is the technique known as means-ends analysis, which plays a central role in the structure of the General Problem Solver.?

下一步搜索從樹的那一個(gè)節(jié)點(diǎn)開始？這就要進(jìn)行不同節(jié)點(diǎn)與目標(biāo)的相對距離測定叹话。佳者優(yōu)先策略要求從那個(gè)看起來離目標(biāo)最近的節(jié)點(diǎn)開始下一步搜索偷遗。從該節(jié)點(diǎn)起應(yīng)取什么方向？這就需要測出當(dāng)前節(jié)點(diǎn)的結(jié)構(gòu)與目標(biāo)結(jié)構(gòu)之間的差異驼壶，并向著最能有效消除差異的方向前進(jìn)氏豌。這就使傳說中的“手段—目的分析法”，在通用問題求解程序（GPS）中起主導(dǎo)作用热凹。?

具體操作中則需要一個(gè)估價(jià)函數(shù)f(n) = g(n) + h(n) 其中f(n) 是節(jié)點(diǎn)n的估價(jià)函數(shù)泵喘，g(n)實(shí)在狀態(tài)空間中從初始節(jié)點(diǎn)到n節(jié)點(diǎn)的實(shí)際代價(jià)，h(n)是從n到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)代價(jià)般妙。在這里主要是h(n)體現(xiàn)了搜索的啟發(fā)信息纪铺，因?yàn)間(n)是已知的。如果說詳細(xì)點(diǎn)碟渺，g(n)代表了搜索的廣度的優(yōu)先趨勢鲜锚。但是當(dāng)h(n) >> g(n)時(shí)，可以省略g(n)苫拍，而提高效率芜繁。（摘自百度百科，不過說實(shí)話這一段我沒看懂绒极，歡迎高手指點(diǎn)）?

Search—successive generation of potentional solution structures--is a fundamental aspect of a symbol system's exercise of intelligence in problem solving but that amount of search is not a measure of the amount of intelligence being exhibited. What makes a problem a problem is not that a large amount of search is required for its solution, but that a large amount would be required if a requisite level of intelligence were not applied. When the symbolic system that is endeavoring to solve a problem knows enough about what to do, it simply proceeds directly towards its goal; but whenever its knowledge becomes inadequate, when it enters terra incognita, it is faced with the threat of going through large amounts of search before it finds its way again.?

并不是搜索越多就意味著智能越高骏令，正相反，智能高的表現(xiàn)恰恰是不用經(jīng)過大量搜索也能解決問題集峦。?

啟發(fā)式搜索會(huì)造成這樣的結(jié)果：找到的解雖然是令人滿意的伏社，卻不是最優(yōu)的；或者說塔淤，雖不是最優(yōu)的卻能令人滿意摘昌。實(shí)際上在認(rèn)知心理學(xué)研究中也表明，動(dòng)物在進(jìn)行決策的時(shí)候采取的也是啟發(fā)式策略高蜂，尤其是在資源（時(shí)間聪黎、食物等）不充足的情況下。這樣做出的決策往往不是最優(yōu)的，不過至少是有效的稿饰。這個(gè)就是西蒙“有限理性”的理論來源锦秒，使得西蒙后來獲得了諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。?

2 幾個(gè)啟發(fā)式搜索的實(shí)例?

這部分參考《人工科學(xué)——復(fù)雜性面面觀》 司馬賀著 武夷山譯?

http://www.douban.com/subject/1195595/?

例一 通用解題者（General Problem Solver喉镰，GPS）P113-114?

“……在輸入或感官一側(cè)旅择，GPS必須能表現(xiàn)想望狀況或想望物（就是上面說的目標(biāo)結(jié)構(gòu)），表現(xiàn)目前狀況侣姆，它也必須能表現(xiàn)想望狀況與目前狀況的差別生真。 在傳出側(cè)，GPS必須能表現(xiàn)改變實(shí)物或狀況的行動(dòng)捺宗。為了有目的的行動(dòng)柱蟀，GPS必須能不時(shí)地選擇這樣一些特定的行動(dòng)，它們有可能消除系統(tǒng)探測到的目前狀態(tài)與 想望狀態(tài)之間的差別蚜厉。在GPS這部機(jī)器中长已，這種選擇是通過一張關(guān)聯(lián)表實(shí)現(xiàn)的。該表將每種可探測到的差別與對減小那一差別有作用的行動(dòng)聯(lián)系起來昼牛。GPS的這 些聯(lián)系（表現(xiàn)為產(chǎn)生過程）將傳入狀況與傳出狀況掛上了鉤术瓮。由于通常需要一系列行動(dòng)才能實(shí)現(xiàn)某一目標(biāo)，由于某些努力也許是無效的匾嘱，GPS也必須有探測自己的 進(jìn)度（現(xiàn)實(shí)狀態(tài)與想望狀態(tài)間差別的變化）和試行新路子的手段斤斧。”?

可以看出GPS解決的是具有“良結(jié)構(gòu)”（well structured）的問題霎烙。也就是說撬讽，等待解決的問題的當(dāng)前狀態(tài)、目標(biāo)狀態(tài)以及搜索空間中的路徑都很清楚悬垃。不能滿足此條件的問題稱為結(jié)構(gòu)不良問題（poorly structured problem）?

例二 “理解”（understand）P88?

這是一個(gè)可以解決結(jié)構(gòu)不良問題的程序游昼。?

“有一個(gè)名叫“理解”的程序，它模擬人們對飲茶儀式這種問題建立內(nèi)部表象（即進(jìn)行理解）的過程尝蠕『嫱悖“理解”分兩階段進(jìn)行工作：先對問題指令的句子進(jìn)行語法分析，然后根據(jù)經(jīng)過語法分析的句子摘取出的信息構(gòu)造一個(gè)表象看彼。?

……分析的任務(wù)就是根據(jù)線性詞串推斷出隱含著的詞組和從句的層級(jí)結(jié)構(gòu)廊佩。“理解”程序是用相當(dāng)正統(tǒng)的方式（類似于現(xiàn)有的其他語法分析程序）完成這一 步驟的靖榕。第二階段（構(gòu)造）更為有趣标锄。這里。對經(jīng)過語法分析的句子進(jìn)行考察茁计，以期發(fā)現(xiàn)提到了哪些賓詞和賓詞集料皇，提到了賓詞的那些性質(zhì)，這些性質(zhì)之間的關(guān)系是 什么，哪些謂詞與關(guān)系描述了狀態(tài)践剂，哪些描述了步驟鬼譬，目標(biāo)狀態(tài)是什么⊙犯“理解”接著構(gòu)造一個(gè)表現(xiàn)狀態(tài)的規(guī)則优质，產(chǎn)生出步驟符合規(guī)定（通過將一個(gè)狀態(tài)轉(zhuǎn)變?yōu)榱硪?狀態(tài)）的程序∧锌撸”?

這個(gè)看上去似乎挺牛的盆赤，不過實(shí)際上它的功能非常有限。在西蒙的《思想模型》（Models of Thought）一書的7.1章到7.3章有關(guān)于“理解”程序的詳細(xì)描述歉眷。?

例三 培根（BACON）P99?

這是個(gè)具有發(fā)現(xiàn)能力的程序。?

“BACON程序的目的是發(fā)現(xiàn)大量數(shù)據(jù)中的不變量颤枪。給定各行星至太陽的距離與它們的軌道周期的數(shù)據(jù)汗捡，該程序發(fā)現(xiàn)，對于所有的行星畏纲，軌道周期的立方 與行星至太陽的距離的平方之比都是一樣的（開普勒第三定律）扇住。根據(jù)電流隨電路中電阻線長度而變化的數(shù)據(jù)，它推出了歐姆定律盗胀。同理艘蹋，它發(fā)現(xiàn)了氣體定律、伽利 略自由落體定律和許多其他定律票灰。?

為了解釋發(fā)現(xiàn)的不變量女阀，BACON就引入新概念。給定數(shù)據(jù)表明屑迂，當(dāng)兩個(gè)物體互相加速時(shí)浸策，兩者加速度的比值總是相同的。BACON程序由此發(fā)明了質(zhì)量的概念惹盼，并給每一物體一個(gè)質(zhì)量庸汗。同理，它發(fā)明了折射率手报，以及比熱和化學(xué)價(jià)的概念蚯舱。?

……BACON的基本構(gòu)造沒有多少新東西。給定兩組數(shù)據(jù)掩蛤，如果它發(fā)現(xiàn)一組數(shù)據(jù)隨另一組數(shù)據(jù)單調(diào)變化枉昏，就檢驗(yàn)一下它們的比值（或乘積）是否不變。如 果成功了盏档，它就發(fā)現(xiàn)了數(shù)值之間的定律關(guān)系凶掰；如果失敗了，它也定義了一個(gè)新的變量，可將此變量加到其他變量上去懦窘，再重復(fù)這一過程前翎。該系統(tǒng)的行為了不起的地方 是，通過這些步驟發(fā)現(xiàn)上述種種定律并不需要大量的搜索畅涂。為找到一個(gè)不變量港华，很少需要考察原變量的十幾個(gè)以上的函數(shù)∥缢ィ”?

科學(xué)家要失業(yè)了嗎立宜？不會(huì)的。BACON以及后來出現(xiàn)的一大堆發(fā)現(xiàn)程序雖然能發(fā)現(xiàn)一些定律臊岸，但并不能解釋其中的內(nèi)涵橙数。我上小學(xué)的時(shí)候就知道E=mc2，可是到現(xiàn)在還是不懂狹義相對論帅戒。?

這些發(fā)現(xiàn)程序在化學(xué)學(xué)科中做了一些貢獻(xiàn)灯帮，但主要被用于深化對人類發(fā)現(xiàn)過程的認(rèn)識(shí)÷咦。“例如钟哥，人們將BACON程序的模擬結(jié)果與物理學(xué)和化學(xué)的發(fā)現(xiàn)的 歷史事例進(jìn)行了比較，還在實(shí)驗(yàn)室中庸一些受試者進(jìn)行了并行實(shí)驗(yàn)瞎访，看看他們憑借BACON程序努力做出的發(fā)現(xiàn)和基于科學(xué)史中記載的資料努力做出發(fā)現(xiàn)的情形有 什么差異腻贰。”?

總結(jié)一下?

AI的兩個(gè)定性結(jié)構(gòu)定律：?

1 智能存在于物理符號(hào)系統(tǒng)中扒秸；?

2 符號(hào)系統(tǒng)是通過生成潛在可能的解播演，并對其進(jìn)行檢驗(yàn)，也就是通過搜索的方式來解題的鸦采。?

符號(hào)系統(tǒng)是許多模式和過程的集合體宾巍，過程能夠產(chǎn)生、破壞或修正模式渔伯。模式能指稱對象顶霞、過程或其他模式，當(dāng)它們指稱過程的時(shí)候锣吼，它們就能得到解釋选浑，完成被指稱的過程。在我們所了解的符號(hào)系統(tǒng)中有兩類意義最為重大玄叠，就是人類和計(jì)算機(jī)古徒。?

符號(hào)系統(tǒng)的智能體現(xiàn)在它能夠從問題空間中抽取信息，并通過搜索來解決問題读恃。啟發(fā)式搜索就是一種這樣的搜索策略隧膘，通過估價(jià)函數(shù)來決定下一步搜索的起始點(diǎn)和方向代态，以有效率的解決問題。?

通過認(rèn)知心理學(xué)對人類及動(dòng)物認(rèn)知過程的研究疹吃，提出了很多關(guān)于智能的假設(shè)蹦疑。以這些假設(shè)為依據(jù)，人們開發(fā)了一堆各種各樣的智能程序萨驶，能完成很多看起來 很復(fù)雜的任務(wù)歉摧，比如語義理解，定律發(fā)現(xiàn)等腔呜。但是每一種程序都有它的局限性叁温。相信隨著認(rèn)知科學(xué)研究的不斷深入，會(huì)有更多更牛的程序誕生