南郵自動(dòng)化人工智能3確定性推理

3.1圖搜索戰(zhàn)略3.2盲目搜索3.3啟發(fā)式搜索3.4消解原理3.5規(guī)那么演繹系統(tǒng)1第三章搜索推理技術(shù)3.6產(chǎn)生式系統(tǒng)3.7非單調(diào)推理3.8小結(jié)問題：知識(shí)表示有那些方法？知識(shí)表示的目的是什么？構(gòu)建智能系統(tǒng)的關(guān)鍵是什么？3.1圖搜索戰(zhàn)略思索：形狀空間法的根本特點(diǎn)？根本推理方法？其求解結(jié)果是什么？簡(jiǎn)單回想實(shí)例：猴子與香蕉。2用一個(gè)四元表列〔W，x，Y，z〕表示這個(gè)問題形狀W猴子的程度位置x當(dāng)猴子在箱子頂上時(shí)取x=1；否那么取x=0Y箱子的程度位置z 當(dāng)猴子摘到香蕉時(shí)取z=1；否那么取z=0算符：Goto〔U〕，〔W，0，Y，z〕goto〔U〕〔U，0，Y，z〕Pushbox〔V〕，〔W，0，W，z〕pushbox〔V〕〔V，0，V，z〕Climbbox，〔W，0，W，z〕climbbox〔W，1，W，z〕Grasp，〔c，1，c，0〕grasp〔c，1，c，1〕33.1圖搜索戰(zhàn)略4(b，1，b，0)〔U，0，b，0〕〔V，0，V，0〕〔c，1，c，0〕〔U，0，V，0〕〔c，1，c，1〕〔a，0，b，0〕U=b，climbbox猴子和香蕉問題的形狀空間圖提問：人工搜索求解的解答？目的形狀goto〔U〕goto〔U〕goto〔U〕U=b,pushbox〔V〕pushbox〔V〕goto〔U〕V≠c，climbboxV=c，climbbox3.1圖搜索戰(zhàn)略5猴子和香蕉問題自動(dòng)演示：

猴子香蕉箱子

猴子香蕉箱子

Ha!Ha!3.1圖搜索戰(zhàn)略思索：計(jì)算機(jī)的搜索戰(zhàn)略？圖搜索控制戰(zhàn)略:一種在圖中尋覓途徑的方法。圖中每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)形狀;每條連線對(duì)應(yīng)一個(gè)操作符。圖搜索過程〔GraphSearch〕63.1圖搜索戰(zhàn)略7開場(chǎng)把S放入OPEN表OPEN表為空表？把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表n為目的節(jié)點(diǎn)嗎？把n的后繼節(jié)點(diǎn)放入OPEN表的末端，提供前往節(jié)點(diǎn)n的指針修正指針方向重排OPEN表失敗勝利圖3.1圖搜索過程框圖是是否否3.1圖搜索戰(zhàn)略(1)(3)(4)(5)(6)(7)(7)(8)(9)OPENCLOSED(1)(2)寬度優(yōu)先圖搜索的普經(jīng)過程如下：1〕建立一個(gè)只含有起始節(jié)點(diǎn)S的搜索圖G，把S放到一個(gè)叫做OPEN的未擴(kuò)展節(jié)點(diǎn)表中。2〕建立一個(gè)叫做CLOSED的已擴(kuò)展節(jié)點(diǎn)表，其初始為空表.3〕LOOP：假設(shè)OPEN表是空表，那么失敗退出。4〕選擇OPEN表上的第一個(gè)節(jié)點(diǎn)，把它從OPEN表移出并放進(jìn)CLOSED表中。稱此節(jié)點(diǎn)為節(jié)點(diǎn)n5〕假設(shè)n為一目的節(jié)點(diǎn)，那么有解并勝利退出，此解是追蹤圖G中沿著指針從n到S這條途徑而得到的(指針將在第7步中設(shè)置)。83.1圖搜索戰(zhàn)略6〕擴(kuò)展節(jié)點(diǎn)n，同時(shí)生成不是n的祖先的那些后繼節(jié)點(diǎn)的集合M。把M的這些成員作為n的后繼節(jié)點(diǎn)添入圖G中。7〕對(duì)那些未曾在G中出現(xiàn)過的M成員設(shè)置一個(gè)通向n的指針。把M的這些成員加進(jìn)OPEN表。對(duì)曾經(jīng)在OPEN或CLOSED表上的每一個(gè)M成員，確定能否需更改通到n的指針方向。對(duì)已在CLOSED表上的每個(gè)M成員，確定能否需求更改圖G中通向它的每個(gè)后裔節(jié)點(diǎn)的指針方向。8〕按某一恣意方式或按某個(gè)探試值，重排OPEN表。9〕GOLOOP。93.1圖搜索戰(zhàn)略圖搜索戰(zhàn)略圖搜索的本質(zhì)是從問題空間中找出一張包含目的節(jié)點(diǎn)的子圖。圖搜索的結(jié)果：1，一個(gè)完好的搜索圖G。2一個(gè)解途徑，用指針表示的解途徑。ProcedureGraphSearch1G=G0(G0=s),open=(s)//s:初始形狀2closed=()3Loop:ifopen=()thenexit(fall)4n←first(open)remove(n,open),add(n,closed)5ifgoal(n)thenexit(success)6{mj}←expand(n),//mj不含n的先輩節(jié)點(diǎn)7open←add(open，mj)//mj不在open，closed中2024/1/1510標(biāo)志mj每個(gè)到n節(jié)點(diǎn)指針確定能否需求修正已在open，closed中的每個(gè)節(jié)點(diǎn)到n的指針確定能否需求修正已在closed中的每個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)原來的指針。8按照某種方式陳列open表中的節(jié)點(diǎn)，goloop2024/1/15112024/1/15122024/1/1513思索：〔1〕結(jié)果途徑的構(gòu)成中，為什么其節(jié)點(diǎn)順序是明確的？〔2〕OPEN表中的節(jié)點(diǎn)具有什么特點(diǎn)？〔3〕CLOSED表中的節(jié)點(diǎn)具有什么特點(diǎn)？〔4〕對(duì)OPEN表節(jié)點(diǎn)的排序有何意義？提出：盲目搜索與啟發(fā)式搜索。143.1圖搜索戰(zhàn)略3.2盲目搜索盲目搜索又叫做無信息搜索，普通只適用于求解比較簡(jiǎn)單的問題。特點(diǎn)：不需重排OPEN表；種類：寬度優(yōu)先、深度優(yōu)先、等代價(jià)搜索等。153.2.1寬度優(yōu)先搜索〔Breadth-first〕定義：以接近起始節(jié)點(diǎn)的程度逐層擴(kuò)展節(jié)點(diǎn)的搜索方法。特點(diǎn)：一種高代價(jià)搜索，但假設(shè)有解存在，那么必能找到它。16SLOMFPQNFFF寬度優(yōu)先搜索表示圖1〕把起始節(jié)點(diǎn)放到OPEN表中(假設(shè)該起始節(jié)點(diǎn)為一目的節(jié)點(diǎn)，那么求得一個(gè)解答)。2〕假設(shè)OPEN是個(gè)空表，那么沒有解，失敗退出；否那么繼續(xù)。3〕把第一個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)n)從OPEN表移出，并把它放入CLOSED的擴(kuò)展節(jié)點(diǎn)表中。4〕擴(kuò)展節(jié)點(diǎn)n。假設(shè)沒有后繼節(jié)點(diǎn)，那么轉(zhuǎn)向上述第(2)步。5〕把n的一切后繼節(jié)點(diǎn)放到OPEN表的末端，并提供從這些后繼節(jié)點(diǎn)回到n的指針。6〕假設(shè)n的任一個(gè)后繼節(jié)點(diǎn)是個(gè)目的節(jié)點(diǎn)，那么找到一個(gè)解答，勝利退出；否那么轉(zhuǎn)向第(2)步。17寬度優(yōu)先搜索算法：3.2盲目搜索18開場(chǎng)把S放入OPEN表OPEN表為空表？把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表能否有后繼節(jié)點(diǎn)為目的節(jié)點(diǎn)？擴(kuò)展n，把n的后繼節(jié)點(diǎn)放入OPEN表的末端，提供前往節(jié)點(diǎn)n的指針失敗勝利圖3.2寬度優(yōu)先算法框圖是否是否3.2盲目搜索思索：與原始算法比較異同，寬度優(yōu)先的表達(dá)？2024/1/1519寬度優(yōu)先算法Procedruebreadth-First-Search1G=G0(G0=s),open=(s),closed=()//s:初始形狀2Loop:ifopen=()thenexit(fall)3n←first(open)4ifgoal(n)thenexit(success)5remove(n,open),add(n,closed)6{mj}←expand(n),//mj不含n的先輩節(jié)點(diǎn)7open←add(open，mj)//mj不在open，closed中2024/1/1520

標(biāo)志每個(gè)到n節(jié)點(diǎn)指針，按照節(jié)點(diǎn)深度遞增順序陳列open中的節(jié)點(diǎn)8goloop實(shí)際上可以利用寬度優(yōu)先搜索可以找到解，假設(shè)問題有解的話。討論：寬度優(yōu)先算法和深度優(yōu)先算法能夠出現(xiàn)組合爆炸。都沒有利用任何啟發(fā)式信息，所以稱為無信息搜索戰(zhàn)略。2024/1/1521：寬度優(yōu)先例題：由一張桌子T、三個(gè)積木A、B、C組成一個(gè)積木世界，初始形狀是A在B上，B在桌子上，C在桌子上；目的形狀是：A、B、C依次從上到下陳列在桌子上。如圖2024/1/1522解：1〕形狀描畫〔P1，P2，P3〕表示按A、B、C順序依次分別在P1,P2,P3上其中Pi是積木或者桌子。初始形狀時(shí)〔B、T、T〕,目的形狀可以表示〔B、C、T〕2〕定義操作:move(x,y)表示將積木x移到Y(jié)上；約束條件:aX頂部必需是空的b假設(shè)Y是積木，Y的頂部必需是空的c同一種形狀出現(xiàn)不得多于一次。2024/1/15231〕解題過程2〕open表和closed表3〕節(jié)點(diǎn)樣子畫出整個(gè)圖G和解途徑4〕程序何時(shí)終了5〕改用深度優(yōu)先如何？例子

八數(shù)碼難題〔8-puzzleproblem〕241238456712384567〔目的形狀〕〔初始形狀〕規(guī)定：將牌移入空格的順序?yàn)椋簭目崭褡筮呴_場(chǎng)順時(shí)針旋轉(zhuǎn)。不許斜向挪動(dòng)，也不前往先輩節(jié)點(diǎn)。從圖可見，要擴(kuò)展26個(gè)節(jié)點(diǎn)，共生成46個(gè)節(jié)點(diǎn)之后才求得解〔目的節(jié)點(diǎn)〕。3.2盲目搜索253.2盲目搜索3.2.2深度優(yōu)先搜索(Dephth-first)26定義：首先擴(kuò)展最新產(chǎn)生的(即最深的)節(jié)點(diǎn)。特點(diǎn)：防止搜索過程沿著無益的途徑擴(kuò)展下去，往往給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度——深度界限。與寬度優(yōu)先搜索算法最根本的不同在于：將擴(kuò)展的后繼節(jié)點(diǎn)放在OPEN表的前端。3.2盲目搜索深度優(yōu)先搜索表示圖27SLOMFPQNFFF3.2盲目搜索28開場(chǎng)把S放入OPEN表OPEN表為空表？把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表能否有后繼節(jié)點(diǎn)為目的節(jié)點(diǎn)？擴(kuò)展n，把n的后繼節(jié)點(diǎn)放入OPEN表的前端，提供前往節(jié)點(diǎn)n的指針失敗勝利圖3.6深度優(yōu)先算法框圖是否是否3.2盲目搜索節(jié)點(diǎn)n的深度等于最大深度？否2024/1/1529深度優(yōu)先算法Procedruedepth-First-Search1G=G0(G0=s),open=(s),closed=()//s:初始形狀2Loop:ifopen=()thenexit(fall)3n←first(open)4ifgoal(n)thenexit(success)5remove(n,open),add(n,closed)6{mj}←expand(n),//mj不含n的先輩節(jié)點(diǎn)7open←add(open，mj)//mj不在open，closed中標(biāo)志mj每個(gè)到n節(jié)點(diǎn)指針，按照節(jié)點(diǎn)深度遞減順序陳列open中的節(jié)點(diǎn)8goloop示范：有界深度(4)優(yōu)先的八數(shù)碼問題深度優(yōu)先搜索樹？303.2盲目搜索1238456712384567〔目的形狀〕〔初始形狀〕313.2盲目搜索2024/1/1532討論1：假設(shè)問題有解，用深度優(yōu)先搜索算法，能否可以找到解？不一定.解空間能否有限？討論2：本算法的改良之處是open中節(jié)點(diǎn)按照深度優(yōu)先陳列，但是沒有對(duì)深度加以控制，能夠呵斥搜索代價(jià)太大3.2.3等代價(jià)搜索33定義是寬度優(yōu)先搜索的一種推行，不是沿著等長(zhǎng)度途徑斷層進(jìn)展擴(kuò)展，而是沿著等代價(jià)途徑斷層進(jìn)展擴(kuò)展。搜索樹中每條銜接弧線上的有關(guān)代價(jià),表示時(shí)間、間隔等破費(fèi)。算法在等價(jià)搜索算法中，把從節(jié)點(diǎn)i到其后續(xù)節(jié)點(diǎn)j的銜接弧線記為c(I,j),把從起始節(jié)點(diǎn)S到任一節(jié)點(diǎn)I的途徑代價(jià)記為g(i)。在搜索樹上，假設(shè)g(i)也是從起始節(jié)點(diǎn)S到節(jié)點(diǎn)的最少代價(jià)途徑上的代價(jià)。3.2盲目搜索思索：如何動(dòng)態(tài)計(jì)算g(i)?34開場(chǎng)把S放入OPEN表OPEN表為空表？把具有最小g(i)值的節(jié)點(diǎn)i從OPEN表移至CLOSED表能否有后繼節(jié)點(diǎn)為目的節(jié)點(diǎn)？失敗勝利圖3.8等代價(jià)搜索算法框圖是否是否令g(s)=0S能否目的節(jié)點(diǎn)？是勝利否3.2盲目搜索擴(kuò)展i，計(jì)算其后繼節(jié)點(diǎn)j的g(j)，并把后繼節(jié)點(diǎn)放入OPEN表課后例題講解1.設(shè)有如下圖的一棵與/或樹，請(qǐng)用與/或樹的寬度優(yōu)先搜索及與/或樹的深度優(yōu)先搜索求出解樹。35解：〔1〕與/或樹的寬度優(yōu)先搜索先擴(kuò)展節(jié)點(diǎn)A，得到節(jié)點(diǎn)B和C；再擴(kuò)展節(jié)點(diǎn)B,得節(jié)點(diǎn)t1、t2，由于t1、t2為可解節(jié)點(diǎn)，故節(jié)點(diǎn)B可解，從而可節(jié)點(diǎn)A可解。所以求得解樹為：36〔2〕與/或樹的深度優(yōu)先搜索先擴(kuò)展節(jié)點(diǎn)A,得到節(jié)點(diǎn)B和C；再擴(kuò)展節(jié)點(diǎn)C,得節(jié)點(diǎn)D和t5；t5為可解節(jié)點(diǎn)，再擴(kuò)展節(jié)D，得節(jié)點(diǎn)t3、t4；t3、t4為可解節(jié)點(diǎn)，故節(jié)點(diǎn)D可解，由于節(jié)點(diǎn)D和t5可解故節(jié)點(diǎn)C可解，從而可節(jié)點(diǎn)A可解。所以求得解樹為：372.以下圖是5個(gè)城市的交通圖，城市之間的連線旁邊的數(shù)字是城市之間路程的費(fèi)用。要求從A城出發(fā)，經(jīng)過其它各城市一次且僅一次，最后回到A城，請(qǐng)找出一條最優(yōu)線路。等代價(jià)搜索383.3啟發(fā)式搜索啟發(fā)式信息：用來加速搜索過程的問題領(lǐng)域信息，普通與有關(guān)問題詳細(xì)領(lǐng)域背景有關(guān)，不一定具有通用性。啟發(fā)式搜索：利用啟發(fā)式信息的搜索方法特點(diǎn)：重排OPEN表，選擇最有希望的節(jié)點(diǎn)加以擴(kuò)展種類：有序搜索、A*算法等39根本步驟：初始化，判別OPEN表能否為空，選擇節(jié)點(diǎn)n，判別n能否目的節(jié)點(diǎn)，擴(kuò)展節(jié)點(diǎn)n，重排OPEN表、調(diào)整指針，循環(huán)。各自特點(diǎn)：重排OPEN表的根據(jù)不同。盲目搜索能夠帶來組合爆炸。思索：〔1〕圖搜索方法的根本步驟？〔2〕寬度優(yōu)先、深度優(yōu)先、等代價(jià)方法的特點(diǎn)？ 〔3〕盲目搜索的缺陷？有序搜索〔OrderedSearch〕總是選擇“最有希望〞的節(jié)點(diǎn)作為下一被擴(kuò)展節(jié)點(diǎn)估價(jià)函數(shù)〔EvaluationFunction〕為獲得某些節(jié)點(diǎn)“希望〞的啟發(fā)信息，提供一個(gè)評(píng)定侯選擴(kuò)展節(jié)點(diǎn)的方法，以便確定哪個(gè)節(jié)點(diǎn)最有能夠在通向目的的最正確途徑上。

f(n)——表示節(jié)點(diǎn)n的估價(jià)函數(shù)值運(yùn)用節(jié)點(diǎn)“希望〞程度〔估價(jià)函數(shù)值〕重排OPEN表；有序搜索也稱為最正確優(yōu)先搜索；估價(jià)函數(shù)舉例：〔1〕棋局的得分；〔2〕間隔目的形狀的間隔量度；〔3〕TSP問題中的途徑；思索：f函數(shù)的計(jì)算，重排序的方法？403.3.1啟發(fā)式搜索戰(zhàn)略和估價(jià)函數(shù)3.3啟發(fā)式搜索413.3.2有序搜索〔OrderedSearch；Best－firstSearch〕本質(zhì)：選擇OPEN表上具有最小f值的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。3.3啟發(fā)式搜索Nilsson〔尼爾遜〕方法：一個(gè)節(jié)點(diǎn)的“希望〞越大，那么其f值越小。被選擇的節(jié)點(diǎn)是估價(jià)函數(shù)最小的節(jié)點(diǎn)。思索：假設(shè)把寬度優(yōu)先、深度優(yōu)先、等代價(jià)搜索方法作為有序搜索的特例，那么它們的f函數(shù)如何計(jì)算？ 舉例示范。42開場(chǎng)把S放入OPEN表，計(jì)算估價(jià)函數(shù)f(s)OPEN表為空表？選取OPEN表中f值最小的節(jié)點(diǎn)i放入CLOSED表i為目的節(jié)點(diǎn)嗎？擴(kuò)展i，得后繼節(jié)點(diǎn)j，計(jì)算f(j)，提供前往節(jié)點(diǎn)i的指針，利用f(j)對(duì)OPEN表重新排序，調(diào)整親子關(guān)系及指針失敗勝利圖3.9有序搜索算法框圖是否是否3.3啟發(fā)式搜索算法八數(shù)碼難題43〔2〕如下的八數(shù)碼難題〔8-puzzleproblem〕12384567〔目的形狀〕12384567〔初始形狀〕〔3〕八數(shù)碼難題的有序搜索樹見以下圖：3.3啟發(fā)式搜索〔1〕估價(jià)函數(shù)設(shè)置： f(n)=d(n)+W(n)d(n):節(jié)點(diǎn)n的深度；W(n):錯(cuò)放的棋子數(shù)443.3啟發(fā)式搜索f函數(shù)的重要性有序搜索的有效性直接取決于f,是提高搜索效率的關(guān)鍵；假設(shè)f不準(zhǔn)確，能夠失去最正確解，也能夠失去全部解；f普通選擇戰(zhàn)略搜索時(shí)間與空間的折衷；保證有解或有最正確解；f選擇的三種典型情況：〔1〕最優(yōu)解答：形狀空間中有多條解答途徑，求解最優(yōu)解答，如A*算法；〔2〕搜索代價(jià)與解答質(zhì)量的綜合：?jiǎn)栴}類似于〔1〕，但搜索過程能夠超出時(shí)間與空間的界限。在適當(dāng)?shù)乃阉鲗?shí)驗(yàn)中找到稱心解答，并限制稱心解答與最優(yōu)解答的差別程度；如：TSP問題；〔3〕最小搜索代價(jià)：不思索解答的最優(yōu)化〔只需一個(gè)解答或多個(gè)解答間無差別〕，盡量使搜索代價(jià)最?。蝗纾憾ɡ碜C明。思索：〔1〕f不能識(shí)別某些節(jié)點(diǎn)的真實(shí)“希望〞值會(huì)怎樣樣？〔2〕f過多估計(jì)了全部節(jié)點(diǎn)又會(huì)怎樣樣？453.3啟發(fā)式搜索3.3.3A*算法思索：經(jīng)過節(jié)點(diǎn)n的最正確途徑，怎樣表示？怎樣求解最優(yōu)解答途徑。估價(jià)函數(shù)f*：對(duì)節(jié)點(diǎn)n定義f*(n)=g*(n)+h*(n),表示從S開場(chǎng)經(jīng)過節(jié)點(diǎn)n的一條最正確途徑的代價(jià)。其中g(shù)*(n)表示從起始節(jié)點(diǎn)S到n的最正確途徑，h*(n)表示從n到某目的節(jié)點(diǎn)的最正確途徑。估價(jià)函數(shù)f：f(n)=g(n)+h(n)；其中g(shù)是g*的估計(jì)，h是h*的估計(jì)；g的一個(gè)選擇就是搜索樹中從S到n的這