西電人工智能8確定性推理part1

ArtificialIntelligence(AI)

人工智能主講：戚玉濤Email：qi_yutao@163.com第三章：確定性推理內(nèi)容提要要第三章：：確定性性推理1.推理的基基本概念念2.搜索策略略3.自然演繹繹推理4.歸結(jié)演繹繹推理5.基于規(guī)則則的演繹繹推理內(nèi)容提要要第三章：：確定性性推理1.推理的基基本概念念2.搜索策略略3.自然演繹繹推理4.歸結(jié)演繹繹推理5.基于規(guī)則則的演繹繹推理推理的基基本概念念推理的基基本概念念1.什么是推推理2.推理方法法及其分分類(lèi)3.推理的控控制策略略及其分分類(lèi)推理的基基本概念念什么是推推理所謂推理理就是按按某種策策略由已已知判斷斷推出另另一個(gè)判判斷的思思維過(guò)程程。在人工智智能中，，推理是是由程序序?qū)崿F(xiàn)的的，稱(chēng)為為推理機(jī)機(jī)。智能系統(tǒng)統(tǒng)的推理理過(guò)程實(shí)實(shí)際上就就是一種種思維過(guò)過(guò)程。按按照推理理過(guò)程所所用知識(shí)識(shí)的確定定性，推推理可分分為：確定性推推理（第第三章））不確定性性推理（（第四章章）推理的基基本概念念推理的兩兩個(gè)基本本問(wèn)題推理的方方法：演繹？歸歸納？類(lèi)類(lèi)比？確確定？不不確定？？單調(diào)？？非單調(diào)調(diào)？啟發(fā)發(fā)式？非非啟發(fā)式式？推理的控控制策略略：推理的控控制策略略是指如如何使用用領(lǐng)域知知識(shí)使推推理過(guò)程程盡快達(dá)達(dá)到目標(biāo)標(biāo)的策略略。推理的控控制策略略又可分分為搜索策略略和推理策略略。推理的基基本概念念推理方法法及其分分類(lèi)1.按推理的的邏輯基基礎(chǔ)分類(lèi)類(lèi)演繹推理理:從已知的的一般性性知識(shí)出出發(fā)，推推出蘊(yùn)含含在已知知知識(shí)中中的適合合于某種種個(gè)別情情況的結(jié)結(jié)論。是是一種由由一般到到個(gè)別的的推理方方法，其其核心是三三段論。歸納推理理:是一種由由個(gè)別到到一般的的推理方方法。類(lèi)比歸納納推理:是指在兩兩個(gè)或兩兩類(lèi)事物物有許多多屬性都都相同或或相似的的基礎(chǔ)上上，推出出它們?cè)谠谄渌麑賹傩陨弦惨蚕嗤蚧蛳嗨频牡囊环N歸歸納推理理。推理的基基本概念念推理方法法及其分分類(lèi)1.按推理的的邏輯基基礎(chǔ)分類(lèi)類(lèi)演繹推理理：假言三段段論：A→B，B→C??A→C常用的三三段論是是由一個(gè)個(gè)大前提、一個(gè)小前前提和一個(gè)結(jié)論論這三部分分組成的的。大前提是是已知的的一般性性知識(shí)或或推理過(guò)過(guò)程得到到的判斷斷；小前提是是關(guān)于某某種具體體情況或或某個(gè)具具體實(shí)例例的判斷斷；結(jié)論是由由大前提提推出的的，并且且適合于于小前提提的判斷斷。推理的基基本概念念推理方法法及其分分類(lèi)1.按推理的的邏輯基基礎(chǔ)分類(lèi)類(lèi)演繹推理理：例如，有有如下三三個(gè)判斷斷：①計(jì)計(jì)算機(jī)系系的學(xué)生生都會(huì)編編程序；；（（一般般性知識(shí)識(shí)）②程程強(qiáng)是計(jì)計(jì)算機(jī)系系的一位位學(xué)生；；（（具體體情況））③程程強(qiáng)會(huì)編編程序。。（結(jié)論論）這是一個(gè)個(gè)三段論論推理。。其中，，①是大大前提，，②是小小前提；；③是經(jīng)經(jīng)演繹推推出來(lái)的的結(jié)論。。可見(jiàn)，其結(jié)論是是蘊(yùn)含在在大前提提中的推理的基基本概念念推理方法法及其分分類(lèi)1.按推理的的邏輯基基礎(chǔ)分類(lèi)類(lèi)歸納推理理：按照所選選事例的的廣泛性可分為完全歸納納推理和不完全歸歸納推理理。完全歸納納推理：：是指在進(jìn)進(jìn)行歸納納時(shí)需要要考察相相應(yīng)事物物的全部對(duì)象象，并根據(jù)據(jù)這些對(duì)對(duì)象是否否都具有有某種屬屬性，推推出該類(lèi)類(lèi)事物是是否具有有此屬性性。不完全歸歸納推理理：是指在進(jìn)進(jìn)行歸納納時(shí)只考考察了相相應(yīng)事物物的部分對(duì)象象，就得出出了關(guān)于于該事物物的結(jié)論論。推理的基基本概念念推理方法法及其分分類(lèi)1.按推理的的邏輯基基礎(chǔ)分類(lèi)類(lèi)歸納推理理：按照推理理所使用用的方法可分為枚舉、類(lèi)比、統(tǒng)計(jì)和差異歸納納推理等。枚舉歸納納推理：：是指在進(jìn)進(jìn)行歸納納時(shí)，如如果已知知某類(lèi)事事物的有限可數(shù)數(shù)個(gè)具體體事物都具有某某種屬性性，則可可推出該該類(lèi)事物物都具有有此種屬屬性。例如，設(shè)設(shè)有如下下事例：：王強(qiáng)是計(jì)計(jì)算機(jī)系系學(xué)生，，他會(huì)編編程序；；高華是是計(jì)算機(jī)機(jī)系學(xué)生生，她會(huì)會(huì)編程序序；……當(dāng)這些具具體事例例足夠多多時(shí)，就就可歸納納出一個(gè)個(gè)一般性性的知識(shí)識(shí)：凡是是計(jì)算機(jī)機(jī)系的學(xué)學(xué)生，就就一定會(huì)會(huì)編程序序。推理的基基本概念念推理方法法及其分分類(lèi)1.按推理的的邏輯基基礎(chǔ)分類(lèi)類(lèi)類(lèi)比歸納納推理：：若在兩個(gè)個(gè)或兩類(lèi)類(lèi)事物有有許多屬屬性相同同或相似似，則推推出它們們?cè)谄渌麑傩陨仙弦蚕嗤蛳嗨扑啤＠纾涸O(shè)A、B分別是兩兩類(lèi)事物物的集合合：A={a1,a2,…}，B={b1,b2,…}并設(shè)ai與bi總是成對(duì)對(duì)出現(xiàn)，，且當(dāng)ai有屬性P時(shí)，bi就有屬性性Q與此對(duì)應(yīng)應(yīng)，即P(ai)→Q((bi)（i=1,,2,……..）。當(dāng)A與B中有一新新的元素素對(duì)出現(xiàn)現(xiàn)時(shí)，若若已知a'有屬性P，b'有屬性Q則類(lèi)比歸歸納出結(jié)結(jié)論：P(a'')→Q(b')推理的基基本概念念推理方法法及其分分類(lèi)1.按推理的的邏輯基基礎(chǔ)分類(lèi)類(lèi)類(lèi)比歸納納推理：：類(lèi)比歸納納推理的的基礎(chǔ)是是相似原理理，其可靠靠程度取取決于兩兩個(gè)或兩兩類(lèi)事物物的相似似程度以以及這兩兩個(gè)或兩兩類(lèi)事物物的相同同屬性與與推出的的那個(gè)屬屬性之間間的相關(guān)關(guān)程度。。推理的基基本概念念推理方法法及其分分類(lèi)1.按推理的的邏輯基基礎(chǔ)分類(lèi)類(lèi)演繹推理理與歸納納推理的的區(qū)別：：演繹推理理是在已已知領(lǐng)域域內(nèi)的一一般性知知識(shí)的前前提下，，通過(guò)演演繹求解解一個(gè)具具體問(wèn)題題或者證證明一個(gè)個(gè)結(jié)論的的正確性性。它所得出出的結(jié)論論實(shí)際上上早已蘊(yùn)蘊(yùn)含在一一般性知知識(shí)的前前提中，演繹推推理只不不過(guò)是將將已有事事實(shí)揭露露出來(lái)，，因此它不能增增殖新知知識(shí)。歸納推理理所推出出的結(jié)論論是沒(méi)有有包含在在前提內(nèi)內(nèi)容中的的。這種由由個(gè)別事事物或現(xiàn)現(xiàn)象推出出一般性性知識(shí)的的過(guò)程，，是增殖新新知識(shí)的的過(guò)程。推理的基基本概念念推理方法法及其分分類(lèi)2.按推理過(guò)過(guò)程所用用知識(shí)的的確定性性分類(lèi)確定性推推理不確定性性推理3.按推理過(guò)過(guò)程推出出的結(jié)論論是否單單調(diào)增加加分類(lèi)單調(diào)推理理非單調(diào)推推理4.按推理過(guò)過(guò)程是否否利用問(wèn)問(wèn)題的啟啟發(fā)性知知識(shí)分類(lèi)類(lèi)啟發(fā)式推推理非啟發(fā)式式推理推理的基基本概念念推理的控控制策略略及其分分類(lèi)推理過(guò)程程不僅依依賴(lài)于所所用的推推理方法法，同時(shí)時(shí)也依賴(lài)賴(lài)于推理理的控制制策略。。推理的控控制策略略是指如如何使用用領(lǐng)域知知識(shí)使推推理過(guò)程程盡快達(dá)達(dá)到目標(biāo)標(biāo)的策略略。推理的控控制策略略可分為為：搜索策略略推理策略略推理的基基本概念念推理的控控制策略略及其分分類(lèi)搜索策略略：在知識(shí)庫(kù)庫(kù)中尋找找可利用用的知識(shí)識(shí)，從而而構(gòu)造一一條代價(jià)價(jià)較小的的推理路路線(xiàn)。主主要解決決推理線(xiàn)線(xiàn)路、推推理效果果、推理理效率等等問(wèn)題。。按是否使使用啟發(fā)發(fā)式信息息可分為為：盲目搜索索啟發(fā)式搜搜索按問(wèn)題的的表示方方式可分分為：狀態(tài)空間間搜索與或樹(shù)搜搜索推理的基基本概念念推理的控控制策略略及其分分類(lèi)推理策略略：包括推理理方向控控制策略略、求解解策略、、限制策策略、沖沖突消解解策略等等推理方向向控制策策略：用于確定定推理的的控制方方向，可可分為正正向推理理、逆向向推理、、混合推推理及雙雙向推理理。求解策略略：是指僅求求一個(gè)解解，還是是求所有有解或最最優(yōu)解等等。限制策略略：是指對(duì)推推理的深深度、寬寬度、時(shí)時(shí)間、空空間等進(jìn)進(jìn)行的限限制。沖突消解解策略：：是指當(dāng)推推理過(guò)程程有多條條知識(shí)可可用時(shí)，，如何從從這多條條可用知知識(shí)中選選出一條條最佳知知識(shí)用于于推理的的策略。。推理的基基本概念念推理的控控制策略略及其分分類(lèi)推理方向向控制策策略：正向推理理：從已知事事實(shí)出發(fā)發(fā)、正向向使用推推理規(guī)則則，亦稱(chēng)稱(chēng)為數(shù)據(jù)據(jù)驅(qū)動(dòng)推推理或前前向鏈推推理。正向推理理從用戶(hù)戶(hù)提供的的初始已已知事實(shí)實(shí)出發(fā)，，在知識(shí)識(shí)庫(kù)KB中找出當(dāng)當(dāng)前可適適用的知知識(shí)，構(gòu)構(gòu)成可適適用的知知識(shí)集KS；然后按按某種沖沖突消解解策略從從KS中選出一一條知識(shí)識(shí)進(jìn)行推推理，并并將推出出的新事事實(shí)加入入到數(shù)據(jù)據(jù)庫(kù)DB中，作為為下一步步推理的的已知事事實(shí)。在在此之后后，再在在知識(shí)庫(kù)庫(kù)中選取取可適用用的知識(shí)識(shí)進(jìn)行推推理。如如此重復(fù)復(fù)進(jìn)行這這一過(guò)程程，直到到求得所所要求的的解。推理的基基本概念念推理的控控制策略略及其分分類(lèi)推理方向向控制策策略：正向推理理中，如如何根據(jù)據(jù)已知事事實(shí)到知知識(shí)庫(kù)中中選取可可用知識(shí)識(shí)？當(dāng)知知識(shí)庫(kù)中中有多條條知識(shí)可可用時(shí)應(yīng)應(yīng)該先使使用那一一條知識(shí)識(shí)？這些些問(wèn)題涉涉及到了了知識(shí)的匹匹配方法法和沖突消解解策略。。正向推理理的優(yōu)點(diǎn)點(diǎn)：比較直觀(guān)觀(guān)，允許許用戶(hù)主主動(dòng)提供供有用的的事實(shí)信信息，適適合于診診斷、設(shè)設(shè)計(jì)、預(yù)預(yù)測(cè)、監(jiān)監(jiān)控等領(lǐng)領(lǐng)域的問(wèn)問(wèn)題求解解。正向推理理的缺點(diǎn)點(diǎn)：推理無(wú)明明確目標(biāo)標(biāo)，求解解問(wèn)題是是可能會(huì)會(huì)執(zhí)行許許多與解解無(wú)關(guān)的的操作，，導(dǎo)致推推理效率率較低。。推理的基基本概念念推理的控控制策略略及其分分類(lèi)推理方向向控制策策略：逆向推理理：從某個(gè)假假設(shè)目標(biāo)標(biāo)出發(fā)，，逆向使使用規(guī)則則，亦稱(chēng)稱(chēng)為目標(biāo)標(biāo)驅(qū)動(dòng)推推理或逆逆向鏈推推理。逆向推理理首先選選定一個(gè)個(gè)假設(shè)目目標(biāo)，然然后尋找找支持該該假設(shè)的的證據(jù)，，若所需需的證據(jù)據(jù)都能找找到，則則說(shuō)明原原假設(shè)是是成立的的；若找找不到所所需要的的證據(jù)，，則說(shuō)明明原假設(shè)設(shè)不成立立，此時(shí)時(shí)需要另另作新的的假設(shè)。。推理的基基本概念念推理的控控制策略略及其分分類(lèi)推理方向向控制策策略：逆向推理理的主要要優(yōu)點(diǎn)：：不必尋找找和使用用那些與與假設(shè)目目標(biāo)無(wú)關(guān)關(guān)的信息息和知識(shí)識(shí)，推理理過(guò)程的的目標(biāo)明明確，有有利于向向用戶(hù)提提供解釋釋?zhuān)谠\診斷性專(zhuān)專(zhuān)家系統(tǒng)統(tǒng)中較為為有效。。逆向推理理的主要要缺點(diǎn)：：當(dāng)用戶(hù)對(duì)對(duì)解的情情況認(rèn)識(shí)識(shí)不請(qǐng)時(shí)時(shí)，由系系統(tǒng)自主主選擇假假設(shè)目標(biāo)標(biāo)的盲目目性比較較大，若若選擇不不好，可可能需要要多次提提出假設(shè)設(shè)，會(huì)影影響系統(tǒng)統(tǒng)效率。。推理的基基本概念念推理的控控制策略略及其分分類(lèi)推理方向向控制策策略：混合推理理：把正向推推理和逆逆向推理理結(jié)合起起來(lái)所進(jìn)進(jìn)行的推推理稱(chēng)為為混合推推理。是是一種解解決較復(fù)復(fù)雜問(wèn)題題的方法法?；旌贤评砝矸椒ǖ牡娜N類(lèi)類(lèi)型：1.先正向后后逆向：：這種方法法先進(jìn)行行正向推推理，從從已知事事實(shí)出發(fā)發(fā)推出部部分結(jié)果果，然后后再用逆逆向推理理對(duì)這些些結(jié)果進(jìn)進(jìn)行證實(shí)實(shí)或提高高它們的的可信度度。推理的基基本概念念推理的控控制策略略及其分分類(lèi)推理方向向控制策策略：混合推理理方法的的三種類(lèi)類(lèi)型：2.先逆向后后正向：：這種方法法先進(jìn)行行逆向推推理，從從假設(shè)目目標(biāo)出發(fā)發(fā)推出一一些中間間假設(shè)，，然后再再用正向向推理對(duì)對(duì)這些中中間假設(shè)設(shè)進(jìn)行證證實(shí)。3.雙向混合合：是指正向向推理和和逆向推推理同時(shí)時(shí)進(jìn)行，，使推理理過(guò)程在在中間的的某一步步結(jié)合起起來(lái)。內(nèi)容提要要第三章：：確定性性推理1.推理的基基本概念念2.搜索策略略3.自然演繹繹推理4.歸結(jié)演繹繹推理5.基于規(guī)則則的演繹繹推理搜索策略略搜索策略略搜索的基基本概念念狀態(tài)空間間的搜索索策略與/或樹(shù)的搜搜索策略略搜索的完完備性與與效率搜索的基基本概念念搜索的基基本概念念搜索是人人工智能能中的一一個(gè)基本本問(wèn)題，，并與推推理密切切相關(guān)，，搜索策策略的優(yōu)優(yōu)劣，將將直接影影響到智智能系統(tǒng)統(tǒng)的性能能與推理理效率。。搜索的定定義：依靠經(jīng)驗(yàn)驗(yàn)，利用用已有知知識(shí)，根根據(jù)問(wèn)題題的實(shí)際際情況，，不斷尋尋找可利利用知識(shí)識(shí)，從而而構(gòu)造一一條代價(jià)價(jià)最小的的推理路路線(xiàn)，使使問(wèn)題得得以解決決的過(guò)程程稱(chēng)為搜搜索。搜索的適適用情況況：不良結(jié)構(gòu)構(gòu)或非結(jié)結(jié)構(gòu)化問(wèn)問(wèn)題；難難以獲得得求解所所需的全全部信息息；更沒(méi)沒(méi)有現(xiàn)成成的算法法可供求求解使用用。搜索的基基本概念念搜索的類(lèi)類(lèi)型按是否使使用啟發(fā)發(fā)式信息息：盲目搜索索：按預(yù)定的的控制策策略進(jìn)行行搜索，，在搜索索過(guò)程中中獲得的的中間信信息并不不改變控控制策略略。啟發(fā)式搜搜索：在搜索中中加入了了與問(wèn)題題有關(guān)的的啟發(fā)性性信息，，用于指指導(dǎo)搜索索朝著最最有希望望的方向向前進(jìn)，，加速問(wèn)問(wèn)題的求求解過(guò)程程并找到到最優(yōu)解解。按問(wèn)題的的表示方方式：狀態(tài)空間間搜索：：用狀態(tài)空空間法求求解問(wèn)題題進(jìn)行的的搜索與或樹(shù)搜搜索：用問(wèn)題歸歸約法求求解問(wèn)題題進(jìn)行的的搜索狀態(tài)空間間的搜索索策略狀態(tài)空間間的搜索索策略狀態(tài)空間間搜索的的基本思思想圖搜索的的一般過(guò)過(guò)程狀態(tài)空間間的盲目目搜索廣度優(yōu)先先搜索深度優(yōu)先先搜索代價(jià)樹(shù)搜搜索狀態(tài)空間間的啟發(fā)發(fā)式搜索索啟發(fā)性信信息和估估價(jià)函數(shù)數(shù)A算法和A*算法狀態(tài)空間間的搜索索策略狀態(tài)空間間搜索的的基本思思想先把問(wèn)題題的初始始狀態(tài)作作為當(dāng)前前擴(kuò)展節(jié)點(diǎn)點(diǎn)對(duì)其進(jìn)行行擴(kuò)展，生成一一組子節(jié)節(jié)點(diǎn)。然后檢查查問(wèn)題的的目標(biāo)狀狀態(tài)是否否出現(xiàn)在在這些子子節(jié)點(diǎn)中中。若出出現(xiàn)，則則搜索成成功，找找到了問(wèn)問(wèn)題的解解；若沒(méi)沒(méi)出現(xiàn)，，則再按照某種種搜索策策略從已已生成的的子節(jié)點(diǎn)點(diǎn)中選擇擇一個(gè)節(jié)節(jié)點(diǎn)作為為當(dāng)前擴(kuò)擴(kuò)展節(jié)點(diǎn)點(diǎn)。重復(fù)上述述過(guò)程，，直到目目標(biāo)狀態(tài)態(tài)出現(xiàn)在在子節(jié)點(diǎn)點(diǎn)中或者者沒(méi)有可可供操作作的節(jié)點(diǎn)點(diǎn)為止。。所謂對(duì)一一個(gè)節(jié)點(diǎn)點(diǎn)進(jìn)行“擴(kuò)展””是指對(duì)對(duì)該節(jié)點(diǎn)點(diǎn)用某個(gè)個(gè)可用操操作進(jìn)行行作用，，生成該該節(jié)點(diǎn)的的一組子子節(jié)點(diǎn)。。狀態(tài)空間間的搜索索策略狀態(tài)空間間搜索算算法的數(shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)和符號(hào)號(hào)約定OPEN表：未擴(kuò)展節(jié)節(jié)點(diǎn)表，，用于存存放剛生生成節(jié)點(diǎn)點(diǎn)CLOSED表：已擴(kuò)展節(jié)節(jié)點(diǎn)表，，用于存存放已經(jīng)經(jīng)擴(kuò)展或或?qū)⒁獢U(kuò)擴(kuò)展節(jié)點(diǎn)點(diǎn)的S：用表示問(wèn)問(wèn)題的初初始狀態(tài)態(tài)G：表示搜索索過(guò)程所所得到的的搜索圖圖M：表示當(dāng)前前擴(kuò)展節(jié)節(jié)點(diǎn)新生生成的且且不為自自己先輩輩的子節(jié)節(jié)點(diǎn)集狀態(tài)空間間的搜索索策略圖搜索的的一般過(guò)過(guò)程(1)把初始節(jié)節(jié)點(diǎn)S放入未擴(kuò)擴(kuò)展節(jié)點(diǎn)點(diǎn)表OPEN表，并建建立目前前僅包含含S的圖G；(2)檢查OPEN表是否為為空，若若為空，，則問(wèn)題題無(wú)解，，失敗退退出；(3)把OPEN表的第一個(gè)節(jié)節(jié)點(diǎn)取出放入入已擴(kuò)展展節(jié)點(diǎn)表表CLOSED表，并記記該節(jié)點(diǎn)點(diǎn)為節(jié)點(diǎn)點(diǎn)n；(4)考察節(jié)點(diǎn)點(diǎn)n是否為目目標(biāo)節(jié)點(diǎn)點(diǎn)。若是是則得到到了問(wèn)題題的解，，成功退退出。此此時(shí)的解解為追蹤蹤圖G中沿著指指針（步驟6中設(shè)置的的指針））從n到初始節(jié)節(jié)點(diǎn)S的路徑。。狀態(tài)空間間的搜索索策略圖搜索的的一般過(guò)過(guò)程(5)擴(kuò)展節(jié)點(diǎn)點(diǎn)n，生成一一組子節(jié)節(jié)點(diǎn)。把把這些子子節(jié)點(diǎn)中中不是節(jié)節(jié)點(diǎn)n先輩的那那部分子子節(jié)點(diǎn)記記入集合合M，并把這這些子節(jié)節(jié)點(diǎn)作為為節(jié)點(diǎn)n的子節(jié)點(diǎn)點(diǎn)加入G中(6)針對(duì)M中子節(jié)點(diǎn)點(diǎn)的不同同情況，，分別作作如下處處理：①對(duì)那那些沒(méi)有有在G中出現(xiàn)過(guò)過(guò)的M成員設(shè)置置一個(gè)指指向其父父節(jié)點(diǎn)（（即節(jié)點(diǎn)點(diǎn)n）的指針針，并把把它放入入OPEN表。（新新生成的的）②對(duì)那那些原來(lái)來(lái)已在G中出現(xiàn)過(guò)過(guò)，但還還沒(méi)有被被擴(kuò)展的的M成員，確確定是否否需要修修改它指指向父節(jié)節(jié)點(diǎn)的指指針。（（原生成成但未擴(kuò)擴(kuò)展的））③對(duì)于于那些先先前已在在G中出現(xiàn)過(guò)過(guò)，并已已經(jīng)擴(kuò)展展了的M成員，確確定是否否需要修修改其后后繼節(jié)點(diǎn)點(diǎn)指向父父節(jié)點(diǎn)的的指針。。（原生生成也擴(kuò)擴(kuò)展過(guò)的的）圖搜索的的一般過(guò)過(guò)程(7)按某種策策略對(duì)OPEN表中的節(jié)節(jié)點(diǎn)進(jìn)行行排序。。(8)轉(zhuǎn)第(2)步。狀態(tài)空間間的搜索索策略狀態(tài)空間間的搜索索策略圖搜索的的一般過(guò)過(guò)程的幾幾點(diǎn)說(shuō)明明：上述過(guò)程程是狀態(tài)態(tài)空間的的一般圖圖搜索算算法，它它具有通通用性，，后面所所要討論論的各種種狀態(tài)空空間搜索索策略都都是上述述過(guò)程的的一個(gè)特特例。各種搜索索策略的的主要區(qū)區(qū)別在于于對(duì)OPEN表中節(jié)點(diǎn)點(diǎn)的排列列順序不不同。例如，廣廣度優(yōu)先先搜索把把先生成成的子節(jié)節(jié)點(diǎn)排在在前面，，而深度度優(yōu)先搜搜索則把把后生成成的子節(jié)節(jié)點(diǎn)排在在前面。。狀態(tài)空間間的搜索索策略圖搜索的的一般過(guò)過(guò)程的幾幾點(diǎn)說(shuō)明明：在第(6)步針對(duì)M中子節(jié)點(diǎn)點(diǎn)的不同同情況進(jìn)進(jìn)行處理理時(shí)，如如果發(fā)生生當(dāng)?shù)冖冖诜N情況況，那么么，這個(gè)個(gè)M中的節(jié)點(diǎn)點(diǎn)究竟應(yīng)應(yīng)該作為為哪一個(gè)個(gè)節(jié)點(diǎn)的的后繼節(jié)節(jié)點(diǎn)呢？？一般是是由原始始節(jié)點(diǎn)到到該節(jié)點(diǎn)點(diǎn)路徑上上所付出出的代價(jià)價(jià)來(lái)決定定的，哪哪一條路路經(jīng)付出出的代價(jià)價(jià)小，相相應(yīng)的節(jié)節(jié)點(diǎn)就作作為它的的父節(jié)點(diǎn)點(diǎn)。所謂謂由原始始節(jié)點(diǎn)到到該節(jié)點(diǎn)點(diǎn)路徑上上的代價(jià)價(jià)是指這這條路經(jīng)經(jīng)上的所所有有向向邊的代代價(jià)之和和。如果發(fā)生生第③種種情況，，除了需需要確定定該子節(jié)節(jié)點(diǎn)指向向父節(jié)點(diǎn)點(diǎn)的指針針外，還還需要確確定其后后繼節(jié)點(diǎn)點(diǎn)指向父父節(jié)點(diǎn)的的指針。。其依據(jù)據(jù)也是由由原始節(jié)節(jié)點(diǎn)到該該節(jié)點(diǎn)的的路徑上上的代價(jià)價(jià)。狀態(tài)空間間的搜索索策略圖搜索的的一般過(guò)過(guò)程的幾幾點(diǎn)說(shuō)明明：在搜索圖圖中，除除初始節(jié)節(jié)點(diǎn)外，，任意一一個(gè)節(jié)點(diǎn)點(diǎn)都含有有且只含含有一個(gè)個(gè)指向其其父節(jié)點(diǎn)點(diǎn)的指針針。因此此，由所所有節(jié)點(diǎn)點(diǎn)及其指指向父節(jié)節(jié)點(diǎn)的指指針?biāo)鶚?gòu)構(gòu)成的集集合是一一棵樹(shù)，，稱(chēng)為搜索樹(shù)。在搜索過(guò)過(guò)程的第第(4)步，一旦旦某個(gè)被被考察的的節(jié)點(diǎn)是是目標(biāo)節(jié)節(jié)點(diǎn)，則則搜索過(guò)過(guò)程成功功結(jié)束。。此時(shí)，，由初始始節(jié)點(diǎn)到到目標(biāo)節(jié)節(jié)點(diǎn)路徑徑上的所所有操作作就構(gòu)成成了該問(wèn)問(wèn)題的解解，而路路徑由第第(6)步所形成成的指向向父節(jié)點(diǎn)點(diǎn)的指針針來(lái)確定定。如果搜索索過(guò)程終終止在第第(2)步，即沒(méi)沒(méi)有達(dá)到到目標(biāo)，，且OPEN表中已無(wú)無(wú)可供擴(kuò)擴(kuò)展的節(jié)節(jié)點(diǎn)，則則失敗結(jié)結(jié)束。狀態(tài)空間間的搜索索策略狀態(tài)空間間的搜索索策略狀態(tài)空間間搜索的的基本思思想圖搜索的的一般過(guò)過(guò)程狀態(tài)空間間的盲目目搜索廣度優(yōu)先先搜索深度優(yōu)先先搜索代價(jià)樹(shù)搜搜索狀態(tài)空間間的啟發(fā)發(fā)式搜索索啟發(fā)性信信息和估估價(jià)函數(shù)數(shù)A算法和A*算法廣度優(yōu)先先搜索狀態(tài)空間間的廣度度優(yōu)先搜搜索廣度優(yōu)先先搜索的的基本思思想：從初始節(jié)節(jié)點(diǎn)S開(kāi)始逐層層向下擴(kuò)擴(kuò)展，在在第n層節(jié)點(diǎn)還還沒(méi)有全全部搜索索完之前前，不進(jìn)進(jìn)入第n+1層節(jié)點(diǎn)的的搜索。。未擴(kuò)展節(jié)節(jié)點(diǎn)表OPEN表中的節(jié)節(jié)點(diǎn)總是是按進(jìn)入入的先后后排序，，先進(jìn)入入的節(jié)點(diǎn)點(diǎn)排在前前面，后后進(jìn)入的