第三章-搜索策略

2024/1/221第3章搜索戰(zhàn)略問(wèn)題求解系統(tǒng)劃分為兩大類(lèi)知識(shí)貧乏系統(tǒng)依托搜索技術(shù)處理問(wèn)題知識(shí)貧乏、缺乏針對(duì)性效率低知識(shí)豐富系統(tǒng)依托推理技術(shù)處理問(wèn)題基于豐富知識(shí)的推理技術(shù)，直截了當(dāng)效率高2024/1/222第3章搜索戰(zhàn)略?xún)纱箢?lèi)搜索技術(shù):1、普通圖搜索、啟發(fā)式搜索2、基于問(wèn)題歸約的與或圖搜索兩種典型的推理技術(shù):1、基于歸結(jié)的演繹推理歸結(jié)反演2、基于規(guī)那么的演繹推理正向演繹推理逆向演繹推理2024/1/2233.1引言對(duì)于給定的問(wèn)題，智能系統(tǒng)的行為普通是找到可以到達(dá)所希望目的的動(dòng)作序列，并使其所付出的代價(jià)最小、性能最好?；诮o定的問(wèn)題，問(wèn)題求解的第一步是目的的表示。搜索就是找到智能系統(tǒng)的動(dòng)作序列的過(guò)程。2024/1/224搜索算法的輸入是給定的問(wèn)題，輸出是表示為動(dòng)作序列的方案。一旦有了方案，就可以執(zhí)行該方案所給出的動(dòng)作了?！矆?zhí)行階段〕因此，求解問(wèn)題包括：目的表示搜索執(zhí)行2024/1/225〔1〕初始形狀集合：定義了初始的環(huán)境。〔2〕操作符集合：把一個(gè)問(wèn)題從一個(gè)形狀變換為另一個(gè)形狀的動(dòng)作集合。〔3〕目的檢測(cè)函數(shù)：用來(lái)確定一個(gè)形狀是不是目的?！?〕途徑費(fèi)用函數(shù)：對(duì)每條途徑賦予一定費(fèi)用的函數(shù)。其中，初始形狀集合和操作符集合定義了問(wèn)題的搜索空間。普通給定問(wèn)題就是確定該問(wèn)題的一些根本信息，一個(gè)問(wèn)題由4部分組成:2024/1/226和通常的搜索空間不同，人工智能中大多數(shù)問(wèn)題的形狀空間在問(wèn)題求解之前不是全部知道的。在人工智能中，搜索問(wèn)題普通包括兩個(gè)重要的問(wèn)題：搜索什么搜索什么通常指的就是目的。在哪里搜索在哪里搜索就是“搜索空間〞。搜索空間通常是指一系列形狀的聚集，因此稱(chēng)為形狀空間。2024/1/227所以，人工智能中的搜索可以分成兩個(gè)階段：形狀空間的生成階段在該形狀空間中對(duì)所求問(wèn)題形狀的搜索搜索可以根據(jù)能否運(yùn)用啟發(fā)式信息分為盲目搜索啟發(fā)式搜索2024/1/228盲目搜索只是可以區(qū)分出哪個(gè)是目的形狀。普通是按預(yù)定的搜索戰(zhàn)略進(jìn)展搜索。沒(méi)有思索到問(wèn)題本身的特性，這種搜索具有很大的盲目性，效率不高，不便于復(fù)雜問(wèn)題的求解。啟發(fā)式搜索是在搜索過(guò)程中參與了與問(wèn)題有關(guān)的啟發(fā)式信息，用于指點(diǎn)搜索朝著最有希望的方向前進(jìn)，加速問(wèn)題的求解并找到最優(yōu)解。2024/1/229根據(jù)問(wèn)題的表示方式分為形狀空間搜索與或圖搜索形狀空間搜索是用形狀空間法來(lái)求解問(wèn)題所進(jìn)展的搜索與/或圖搜索是指用問(wèn)題規(guī)約方法來(lái)求解問(wèn)題時(shí)所進(jìn)展的搜索。2024/1/2210思索一個(gè)問(wèn)題的形狀空間為一棵樹(shù)的方式。寬度優(yōu)先搜索深度優(yōu)先搜索假設(shè)根節(jié)點(diǎn)首先擴(kuò)展，然后是擴(kuò)展根節(jié)點(diǎn)生成的一切節(jié)點(diǎn)，然后是這些節(jié)點(diǎn)的后繼，如此反復(fù)下去。在樹(shù)的最深一層的節(jié)點(diǎn)中擴(kuò)展一個(gè)節(jié)點(diǎn)。只需當(dāng)搜索遇到一個(gè)死亡節(jié)點(diǎn)〔非目的節(jié)點(diǎn)并且是無(wú)法擴(kuò)展的節(jié)點(diǎn)〕的時(shí)候，才前往上一層選擇其他的節(jié)點(diǎn)搜索。2024/1/2211無(wú)論是寬度優(yōu)先搜索還是深度優(yōu)先搜索，遍歷節(jié)點(diǎn)的順序普通都是固定的，即一旦搜索空間給定，節(jié)點(diǎn)遍歷的順序就固定了。這種類(lèi)型的遍歷稱(chēng)為“確定性〞的，也就是盲目搜索。對(duì)于啟發(fā)式搜索，在計(jì)算每個(gè)節(jié)點(diǎn)的參數(shù)之前無(wú)法確定先選擇哪個(gè)節(jié)點(diǎn)擴(kuò)展，這種搜索普通也稱(chēng)為非確定的。2024/1/2212完備性：假設(shè)存在一個(gè)解答，該戰(zhàn)略能否保證可以找到？時(shí)間復(fù)雜性：需求多長(zhǎng)時(shí)間可以找到解答？空間復(fù)雜性：執(zhí)行搜索需求多少存儲(chǔ)空間？最優(yōu)性：假設(shè)存在不同的幾個(gè)解答，該戰(zhàn)略能否可以發(fā)現(xiàn)最高質(zhì)量的解答？搜索戰(zhàn)略評(píng)價(jià)規(guī)范:2024/1/2213有許多智力問(wèn)題(如梵塔問(wèn)題、游覽商問(wèn)題、八皇后問(wèn)題、農(nóng)夫過(guò)河問(wèn)題等)和實(shí)踐問(wèn)題〔如途徑規(guī)劃、機(jī)器人行動(dòng)規(guī)劃等〕都可以歸結(jié)為形狀空間搜索。用形狀空間搜索來(lái)求解問(wèn)題的系統(tǒng)均定義一個(gè)形狀空間，并經(jīng)過(guò)適當(dāng)?shù)乃阉魉惴ㄔ谛螤羁臻g中搜索解答途徑。3.2基于形狀空間圖的搜索技術(shù)2024/1/2214形狀空間搜索

——1.形狀空間及其搜索的表示(1)形狀空間的表示形狀空間記為SP，可表示為二元組：SP=(S,O)S——問(wèn)題求解〔即搜索〕過(guò)程中一切能夠到達(dá)的合法形狀構(gòu)成的集合；O——操作算子的集合，操作算子的執(zhí)行會(huì)導(dǎo)致問(wèn)題形狀的變化；形狀——用于記載問(wèn)題求解〔即搜索〕過(guò)程中某一時(shí)辰問(wèn)題現(xiàn)狀的快照；籠統(tǒng)為矢量方式Q=[q0,q1,…,qn]T每個(gè)元素qi稱(chēng)為形狀分量給定每個(gè)形狀分量qi的值就得到一個(gè)詳細(xì)的形狀 Qk=[q0k,q1k,…,qnk]T2024/1/2215形狀表示形狀的變化操作算子問(wèn)題的形狀空間是一個(gè)表示該問(wèn)題的全部能夠形狀及其變化的有向圖。節(jié)點(diǎn)形狀有向弧形狀的變化弧上的標(biāo)簽導(dǎo)致形狀變化的操作算子用形狀空間搜索來(lái)求解問(wèn)題的系統(tǒng)均定義一個(gè)形狀空間，并經(jīng)過(guò)適當(dāng)?shù)乃阉魉惴ㄔ谛螤羁臻g中搜索解答途徑。2024/1/2216例1：走迷宮是人們熟習(xí)的一種游戲。形狀空間搜索2024/1/2217格子、入口和出口——節(jié)點(diǎn)——形狀通道——有向弧——操作算子迷宮可以由一個(gè)有向圖表示2024/1/2218例2:在一個(gè)3×3的方格棋盤(pán)上放置著1,2,3,4,5,6,7,8八個(gè)數(shù)碼，每個(gè)數(shù)碼占一格，且有一個(gè)空格。這些數(shù)碼可在棋盤(pán)上挪動(dòng)，其挪動(dòng)規(guī)那么是：與空格相鄰的數(shù)碼方可移入空格。 如今的問(wèn)題是：對(duì)于指定的初始棋局和目的棋局，給出數(shù)碼的挪動(dòng)序列。該問(wèn)題稱(chēng)為八數(shù)碼問(wèn)題。56741382初始棋局56748321目的棋局挪動(dòng)數(shù)碼2024/1/2219231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123847652024/1/22202024/1/2221形狀空間搜索

——1.形狀空間及其搜索的表示(2)形狀空間表示的經(jīng)典例子“傳教士和野人問(wèn)題〞問(wèn)題的描畫(huà)：N個(gè)傳教士帶著N個(gè)野人劃船過(guò)河；3個(gè)平安約束條件：1)船上人數(shù)不得超越載重限量，設(shè)為K個(gè)人；2)任何時(shí)辰〔包括兩岸、船上〕野人數(shù)目不得超越傳教士；3)允許在河的某一岸或者在船上只需野人而沒(méi)有傳教士；2024/1/2222形狀空間搜索

——1.形狀空間及其搜索的表示(2)形狀空間表示的經(jīng)典例子“傳教士和野人問(wèn)題〞特例：N=3，K=2形狀分量m——傳教士在左岸的實(shí)踐人數(shù)形狀分量c——野人在左岸的實(shí)踐人數(shù)形狀分量b——指示船能否在左岸(1、0)3個(gè)平安約束條件m≧c(左岸平安)且N-m≧N-c(右岸平安);m=0且0≤c≤N(左岸沒(méi)有傳道士，右岸一定平安);N-m=0且0≤N-c≤N(右岸沒(méi)有傳道士，左岸一定平安);2024/1/2223設(shè)初始形狀下傳教士、野人和船都在左岸，目的形狀下這三者均在右岸，問(wèn)題形狀以〔m,c,b〕表示。問(wèn)題的求解義務(wù)可描畫(huà)為：(3,3,1)→(0,0,0)該簡(jiǎn)單問(wèn)題能夠到達(dá)的合法形狀：能夠形狀總數(shù)：4×4×2=32根據(jù)條件得出合法形狀：20m≧c且N-m≧N-c(左岸平安且右岸平安)m=1,c=1；m=2,c=2m=0且0≤c≤N(左岸沒(méi)有傳道士)m=0,c=0,1,2,3N-m=0且0≤N-c≤N(右岸沒(méi)有傳道士)m=3,c=0,1,2,3不能夠到達(dá)的合法形狀：(0,0,1),(0,3,0),(3,0,1),(3,3,0)能夠到達(dá)的合法形狀共16個(gè)2024/1/2224形狀空間搜索

——1.形狀空間及其搜索的表示(2)形狀空間表示的經(jīng)典例子“傳教士和野人問(wèn)題〞定義2類(lèi)操作算子：L(x,y)——指示從左岸到右岸的劃船操作R(x,y)——指示從右岸到左岸的劃船操作x+y≤K=2(船的載重限制)；x和y取值的能夠組合只需5個(gè)10，20，11，01，02(允許在船上只需野人而沒(méi)有傳教士)共有10個(gè)操作算子2024/1/2225渡河問(wèn)題的形狀空間有向圖2024/1/2226形狀空間搜索

——1.形狀空間及其搜索的表示由此例可以看出用形狀空間方法表示問(wèn)題時(shí)，首先必需定義形狀的描畫(huà)方式，經(jīng)過(guò)運(yùn)用這種描畫(huà)方式可把問(wèn)題的一切形狀都表示出來(lái)。另外，還要定義一組操作，經(jīng)過(guò)運(yùn)用這些操作可把問(wèn)題由一種形狀轉(zhuǎn)變?yōu)榱硪环N形狀。問(wèn)題的求解過(guò)程是一個(gè)不斷把操作作用于形狀的過(guò)程。假設(shè)在運(yùn)用某個(gè)操作后得到的新形狀是目的形狀，就得到了問(wèn)題的一個(gè)解。這個(gè)解是從初始形狀到目的形狀所用操作構(gòu)成的序列。2024/1/2227形狀空間搜索

——1.形狀空間及其搜索的表示由此例可以看出要使問(wèn)題由一種形狀轉(zhuǎn)變到另一種形狀時(shí)，就必需運(yùn)用一次操作。這樣，在從初始形狀轉(zhuǎn)變到目的形狀時(shí)，就能夠存在多個(gè)操作序列(即得到多個(gè)解)。那么，其中運(yùn)用操作最少或較少的解才為最優(yōu)解(由于只需在運(yùn)用操作時(shí)所付出的代價(jià)為最小的解才是最優(yōu)解)。對(duì)其中的某一個(gè)形狀，能夠存在多個(gè)操作．使該形狀變到幾個(gè)不同的后繼形狀．那么究竟用哪個(gè)操作進(jìn)展搜索呢?這就有賴(lài)于搜索戰(zhàn)略了．不同的搜索戰(zhàn)略有不同的順序，這就是本章后面要討論的問(wèn)題。2024/1/2228課堂練習(xí)有一農(nóng)夫帶一只狐貍、一只小羊和一籃菜過(guò)河〔從左岸到右岸〕。假設(shè)船太小，農(nóng)夫每次只能帶一樣?xùn)|西過(guò)河；思索到平安，無(wú)農(nóng)夫看管時(shí)，狐貍和小羊不能在一同，小羊和那籃菜也不能在一同。請(qǐng)為該問(wèn)題的處理設(shè)計(jì)形狀空間，并畫(huà)出形狀空間圖。

2024/1/2229解析以變量m、f、s、v分別指示農(nóng)夫、狐貍、小羊、菜,且每個(gè)變量只可取值1(表示在左岸)或0(表示在右岸)。問(wèn)題形狀可以四元組(m、f、s、v)描畫(huà),設(shè)初始形狀下均在左岸,目的形狀下都到達(dá)右岸。從而,問(wèn)題求解義務(wù)可描畫(huà)為

(1,1,1,1)->(0,0,0,0)由于問(wèn)題簡(jiǎn)單,形狀空間中能夠的形狀總數(shù)為2×2×2×2=16,由于要服從平安限制,合法的形狀只需(除初、目形狀外):

1110，1101，1011，1010，0101，0001，0010，0100；

不合法形狀有:0111,1000,1100,0011,0110,1001設(shè)計(jì)二類(lèi)操作算子:Lx、Rx,x為m、f、s、v時(shí)分別指示農(nóng)夫單獨(dú),帶狐貍,帶小羊,帶菜過(guò)河；形狀空間圖如下所示.由于Lx和Rx是互逆操作,故而解答途徑可有無(wú)數(shù)條,但最近的只需二條;都是7個(gè)操作步.思索：為什么不把船的形狀放到形狀空間中去？2024/1/2230解析:四元組(m、f、s、v)2024/1/2231形狀空間搜索

——1.形狀空間及其搜索的表示(3)形狀空間的搜索形狀空間的搜索記為SE，可表示為五元組：SE=(S,O,E,I,G)；E——搜索引擎；I——問(wèn)題的初始形狀，I∈S；G——問(wèn)題的目的形狀集合，GS。搜索引擎E——可以設(shè)計(jì)為實(shí)現(xiàn)任何搜索算法的控制系統(tǒng)。根本思想——經(jīng)過(guò)搜索引擎E尋覓一個(gè)操作算子的調(diào)用序列，使問(wèn)題從初始形狀I(lǐng)變化到目的形狀G之一。解答途徑——初-目變化過(guò)程中的形狀序列或相應(yīng)的操作算子調(diào)用序列。2024/1/2232形狀空間搜索

——1.形狀空間及其搜索的表示或圖〔普通圖〕一個(gè)形狀可以有多個(gè)可供選擇的操作算子；操作算子間的選擇是一種“或〞的關(guān)系;這樣的有向圖稱(chēng)為或圖。2024/1/2233形狀空間搜索

——1.形狀空間及其搜索的表示(3)形狀空間的搜索或圖〔普通圖〕一個(gè)形狀可以有多個(gè)可供選擇的操作算子；操作算子間的選擇是一種“或〞的關(guān)系，這樣的有向圖稱(chēng)為或圖。形狀空間普通都表示為或圖〔普通圖〕搜索圖——在搜索解答途徑的過(guò)程中畫(huà)出搜索時(shí)涉及到的節(jié)點(diǎn)和弧線(xiàn)，構(gòu)成所謂的搜索圖。形狀空間搜索普通圖搜索2024/1/2234形狀空間搜索

——1.形狀空間及其搜索的表示(3)形狀空間的搜索形狀空間、搜索圖和解答途徑之間的關(guān)系S0Sg2024/1/2235形狀空間搜索

——1.形狀空間及其搜索的表示(4)普通圖搜索例子——八數(shù)碼游戲求解的問(wèn)題：給定初始規(guī)劃(即初始形狀)和目的規(guī)劃(即目的形狀)，如何挪動(dòng)數(shù)碼才干從初始規(guī)劃到達(dá)目的規(guī)劃？解答就是一個(gè)合法的棋牌走步序列。初始規(guī)劃目的規(guī)劃挪動(dòng)數(shù)碼2024/1/2236形狀空間搜索

——1.形狀空間及其搜索的表示(4)普通圖搜索例子——八數(shù)碼游戲用普通圖搜索方法處理該問(wèn)題的步驟：1、為問(wèn)題形狀的表示建立數(shù)據(jù)構(gòu)造2、制定操作算子集合3、設(shè)計(jì)搜索引擎第一步：為問(wèn)題形狀的表示建立數(shù)據(jù)構(gòu)造3×3的一個(gè)矩陣S矩陣元素Sij∈{0,1,2,3,4,5,6,7,8},其中1≤i,j≤3數(shù)字0表示空格數(shù)字1-8表示相應(yīng)的棋牌八數(shù)碼問(wèn)題就可表示為：2024/1/2237形狀空間搜索

——1.形狀空間及其搜索的表示初始規(guī)劃目的規(guī)劃挪動(dòng)數(shù)碼(4)普通圖搜索例子——八數(shù)碼游戲2024/1/2238形狀空間搜索

——1.形狀空間及其搜索的表示(4)普通圖搜索例子——八數(shù)碼游戲第二步：制定操作算子集直觀(guān)方法——為每個(gè)棋牌制定一套能夠的走步：左、上、右、下四種挪動(dòng)。需求32個(gè)操作算子簡(jiǎn)易方法——僅為空格制定這4種走步。僅需4個(gè)操作算子第三步：設(shè)計(jì)搜索引擎問(wèn)題形狀空間的大小與問(wèn)題涉及的元素個(gè)數(shù)是程指數(shù)級(jí)爆炸式增長(zhǎng)〔即，組合爆炸問(wèn)題〕如，棋盤(pán)規(guī)劃〔問(wèn)題形狀〕總共有9!=362880個(gè)研討焦點(diǎn)是處理組合爆炸問(wèn)題，經(jīng)過(guò)緊縮搜索空間，提高搜索效率。2024/1/2239形狀空間搜索

——1.形狀空間及其搜索的表示形狀空間、搜索圖和解答途徑之間的關(guān)系S0Sg2024/1/2240形狀空間搜索

——2.普通圖搜索戰(zhàn)略〔1〕搜索術(shù)語(yǔ)1、節(jié)點(diǎn)深度根節(jié)點(diǎn)指示初始形狀，令其深度為0；搜索圖中的其他節(jié)點(diǎn)的深度dn就可以遞歸地定義為其父節(jié)點(diǎn)深度dn-1加1：dn=dn-1+1。根節(jié)點(diǎn)深度=0第n-1層節(jié)點(diǎn)dn-1第n層節(jié)點(diǎn)dn=dn-1+1搜索圖2024/1/2241形狀空間搜索

——2.普通圖搜索戰(zhàn)略〔1〕搜索術(shù)語(yǔ)2、節(jié)點(diǎn)擴(kuò)展運(yùn)用操作算子將上一形狀〔節(jié)點(diǎn)ni〕變化到下一形狀〔節(jié)點(diǎn)nj〕節(jié)點(diǎn)ni稱(chēng)為被擴(kuò)展節(jié)點(diǎn)〔父節(jié)點(diǎn)〕節(jié)點(diǎn)nj稱(chēng)為ni的子節(jié)點(diǎn)節(jié)點(diǎn)ni節(jié)點(diǎn)nj2024/1/2242〔1〕搜索術(shù)語(yǔ)3、途徑節(jié)點(diǎn)ni到nj的途徑是由相鄰節(jié)點(diǎn)間的弧線(xiàn)構(gòu)成的折線(xiàn)要求途徑是無(wú)環(huán)的4、途徑代價(jià)——相鄰節(jié)點(diǎn)ni和ni+1間的途徑代價(jià)記為C(ni,ni+1)通常令恣意相鄰節(jié)點(diǎn)間的途徑代價(jià)一樣，并以途徑長(zhǎng)度1指示。即C(ni,ni+1)=1。形狀空間搜索

——2.普通圖搜索戰(zhàn)略節(jié)點(diǎn)ni節(jié)點(diǎn)ni+1節(jié)點(diǎn)nj2024/1/2243形狀空間搜索

——2.普通圖搜索戰(zhàn)略〔1〕搜索術(shù)語(yǔ)4、途徑代價(jià)目的形狀節(jié)點(diǎn)ng節(jié)點(diǎn)ni節(jié)點(diǎn)nkC(nk,ng)C(ni,nk)C(ni,ng)2024/1/2244形狀空間搜索

——2.普通圖搜索戰(zhàn)略〔2〕普通圖搜索算法符號(hào)闡明：s-初始形狀節(jié)點(diǎn)G-搜索圖OPEN-存放待擴(kuò)展節(jié)點(diǎn)的表CLOSE-存放已被擴(kuò)展的節(jié)點(diǎn)的表MOVE-FIRST(OPEN)-取OPEN表首的節(jié)點(diǎn)作為當(dāng)前要被擴(kuò)展的節(jié)點(diǎn)n，同時(shí)將節(jié)點(diǎn)n移至CLOSE表普通圖搜索算法劃分為二個(gè)階段：1、初始化2、搜索循環(huán)2024/1/2245形狀空間搜索

——2.普通圖搜索戰(zhàn)略〔2〕普通圖搜索算法算法劃分為二個(gè)階段：1、初始化建立只包含初始形狀節(jié)點(diǎn)s的搜索圖G:={s}OPEN:={s}CLOSE:={}2、搜索循環(huán)MOVE-FIRST(OPEN)-取出OPEN表首的節(jié)點(diǎn)n作為擴(kuò)展的節(jié)點(diǎn)，同時(shí)將其移到close表擴(kuò)展出n的子節(jié)點(diǎn),插入搜索圖G和OPEN表適當(dāng)?shù)臉?biāo)志和修正指針排序OPEN表經(jīng)過(guò)循環(huán)地執(zhí)行該算法，搜索圖G會(huì)因不斷有新節(jié)點(diǎn)參與而逐漸長(zhǎng)大，直到搜索到目的節(jié)點(diǎn)。2024/1/2246以下面的八數(shù)碼為例，看普通圖的搜索算法初始規(guī)劃目的規(guī)劃挪動(dòng)數(shù)碼形狀空間搜索

——2.普通圖搜索戰(zhàn)略2024/1/22472024/1/22482024/1/22492024/1/22502024/1/22512024/1/22522024/1/22532024/1/22542024/1/22552024/1/22562024/1/22572024/1/22582024/1/22592024/1/22602024/1/22612024/1/22622024/1/22632024/1/22642024/1/22652024/1/2266形狀空間搜索

——2.普通圖搜索戰(zhàn)略〔2〕普通圖搜索算法——搜索過(guò)程中的指針修正節(jié)點(diǎn)n擴(kuò)展后的子節(jié)點(diǎn)分為3類(lèi)：(i)全新節(jié)點(diǎn)(ii)已出如今OPEN表中的節(jié)點(diǎn)(iii)已出現(xiàn)的CLOSE表中的節(jié)點(diǎn)指針標(biāo)志和修正的方法：(i)類(lèi)節(jié)點(diǎn)：參與OPEN表，建立從子節(jié)點(diǎn)到父節(jié)點(diǎn)n的指針(ii)類(lèi)節(jié)點(diǎn)、(iii)類(lèi)節(jié)點(diǎn)比較經(jīng)由老父節(jié)點(diǎn)、新父節(jié)點(diǎn)n到達(dá)初始形狀節(jié)點(diǎn)的途徑代價(jià)經(jīng)由新父節(jié)點(diǎn)n的代價(jià)比較小，那么將原子節(jié)點(diǎn)指向老父節(jié)點(diǎn)的指針，修正為指向新父節(jié)點(diǎn)n(iii)類(lèi)節(jié)點(diǎn)還得從CLOSE表中移出，重新參與OPEN表。2024/1/2267形狀空間搜索

——2.普通圖搜索戰(zhàn)略Sn4ninjn1n2n3n31n32節(jié)點(diǎn)ni是當(dāng)前擴(kuò)展的節(jié)點(diǎn)；擴(kuò)展出4個(gè)后續(xù)節(jié)點(diǎn)；n1、n2是新節(jié)點(diǎn)，只需建立指向父節(jié)點(diǎn)的指針，并參與OPEN表；2024/1/2268形狀空間搜索

——2.普通圖搜索戰(zhàn)略Sn4ninjn1n2n3n31n32n4曾經(jīng)存在于OPEN表，并且已有父節(jié)點(diǎn)njn4經(jīng)nj的途徑代價(jià)大取消n4指向nj的指針改為建立n4指向新父節(jié)點(diǎn)ni的指針n3曾經(jīng)存在于CLOSE表，并且已有父節(jié)點(diǎn)nj需求做和n4同樣的比較和指針修正任務(wù)。并且要重新參與open表。2024/1/2269形狀空間搜索

——2.普通圖搜索戰(zhàn)略〔2〕普通圖搜索算法OPEN表中節(jié)點(diǎn)簡(jiǎn)單的排序方式：深度優(yōu)先——擴(kuò)展當(dāng)前節(jié)點(diǎn)后生成的子節(jié)點(diǎn)總是置于OPEN表的前端，即OPEN表作為棧，后進(jìn)先出，使搜索優(yōu)先向縱深方向開(kāi)展。2024/1/2270深度優(yōu)先實(shí)例231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123468911131416181912384765目的571012151720212024/1/2271深度優(yōu)先搜索在深度優(yōu)先搜索中，首先擴(kuò)展最新產(chǎn)生的(最深的)節(jié)點(diǎn)，深度相等的節(jié)點(diǎn)可以恣意陳列?！白钔懋a(chǎn)生的節(jié)點(diǎn)最先擴(kuò)展〞起始節(jié)點(diǎn)深度為0任何其他節(jié)點(diǎn)的深度等于其父輩節(jié)點(diǎn)深度加上1:dn=dn-1+12024/1/2272深度優(yōu)先搜索很明顯這樣做，不一定找到最正確解，而且由于深度的限制，能夠找不到解，然而，假設(shè)不加深度限制，能夠沿著一條道路無(wú)限制地?cái)U(kuò)展下去，這當(dāng)然是不允許的。為保證找到解，應(yīng)選擇適當(dāng)?shù)纳疃冉缦?，或者采取不斷加大深度界限的方法，反?fù)搜索，直到找到解。這種改良的方法叫做迭代加深搜索。2024/1/2273ProcedureDepthFirstSearch Begin 把初始節(jié)點(diǎn)壓入棧，并設(shè)置棧頂指針； While棧不空do Begin 彈出棧頂元素； If棧頂元素=goal，勝利前往并終了； Else以恣意次序把棧頂元素的子女壓入棧中； EndWhile End基于棧實(shí)現(xiàn)的深度優(yōu)先搜索算法：2024/1/2274初始節(jié)點(diǎn)放到棧中，棧指針指向棧的最上邊的元素。為了對(duì)該節(jié)點(diǎn)進(jìn)展檢測(cè)，需求從棧中彈出該節(jié)點(diǎn)，假設(shè)是目的，該算法終了，否那么把其子節(jié)點(diǎn)以任何順序壓入棧中。該過(guò)程直到棧變成為空。遍歷一棵樹(shù)的過(guò)程〔以下圖〕。2024/1/2275深度優(yōu)先搜索的性質(zhì)普通不能保證找到最優(yōu)解當(dāng)深度限制不合理時(shí)，能夠找不到解，可以將算法改為可變深度限制最壞情況時(shí)，搜索空間等同于窮舉是一個(gè)通用的與問(wèn)題無(wú)關(guān)的方法2024/1/2276深度優(yōu)先搜索的優(yōu)點(diǎn)是比寬度優(yōu)先搜索算法需求較少的空間，該算法只需求保管搜索樹(shù)的一部分，它由當(dāng)前正在搜索的途徑和該途徑上還沒(méi)有完全展開(kāi)的節(jié)點(diǎn)標(biāo)志所組成。深度優(yōu)先搜索的存儲(chǔ)器要求是深度約束的線(xiàn)性函數(shù)。深度優(yōu)先搜索的優(yōu)點(diǎn)2024/1/2277深度優(yōu)先搜索的缺陷既不是完備的，也不是最優(yōu)的。主要問(wèn)題是能夠搜索到了錯(cuò)誤的途徑上。很多問(wèn)題能夠具有很深甚至是無(wú)限的搜索樹(shù)，假設(shè)不幸選擇了一個(gè)錯(cuò)誤的途徑，那么深度優(yōu)先搜索會(huì)不斷搜索下去，而不會(huì)回到正確的途徑上。這樣一來(lái)對(duì)于這些問(wèn)題，深度優(yōu)先搜索要么墮入無(wú)限的循環(huán)而不能給出一個(gè)答案，要么最后找到一個(gè)答案，但途徑很長(zhǎng)而且不是最優(yōu)的答案。2024/1/2278形狀空間搜索

——2.普通圖搜索戰(zhàn)略〔2〕普通圖搜索算法OPEN表中節(jié)點(diǎn)簡(jiǎn)單的排序方式：深度優(yōu)先——擴(kuò)展當(dāng)前節(jié)點(diǎn)后生成的子節(jié)點(diǎn)總是置于OPEN表的前端，即OPEN表作為棧，后進(jìn)先出，使搜索優(yōu)先向縱深方向開(kāi)展。寬度優(yōu)先——擴(kuò)展當(dāng)前節(jié)點(diǎn)后生成的子節(jié)點(diǎn)總是置于OPEN表的后端，即OPEN表作為隊(duì)列，先進(jìn)先出，使搜索優(yōu)先向橫向方向開(kāi)展。2024/1/2279寬度優(yōu)先實(shí)例23184765283147652318476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目的8234187654910111213141516172024/1/2280寬度優(yōu)先搜索假設(shè)搜索是以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的，那么這種搜索就叫做寬度優(yōu)先搜索。這種搜索是逐層進(jìn)展的，在對(duì)下一層的恣意節(jié)點(diǎn)進(jìn)展搜索之前，必需搜索完本層的一切節(jié)點(diǎn)?！跋犬a(chǎn)生的節(jié)點(diǎn)先擴(kuò)展〞2024/1/2281ProcedureBreadth-first-search Begin 把初始節(jié)點(diǎn)放入隊(duì)列； Repeat 獲得隊(duì)列最前面的元素為current; Ifcurrent=goal 勝利前往并終了；Elsedo Begin 假設(shè)current有子女，那么current的子女 以恣意次序添加到隊(duì)列的尾部； EndUntil隊(duì)列為空 End采用隊(duì)列構(gòu)造，寬度優(yōu)先算法可以表示如下：2024/1/2282寬度優(yōu)先搜索算法原理：假設(shè)當(dāng)前的節(jié)點(diǎn)不是目的節(jié)點(diǎn)，那么把當(dāng)點(diǎn)節(jié)點(diǎn)的子孫以恣意順序添加到隊(duì)列的后面，并把隊(duì)列的前端元素定義為current。假設(shè)目的發(fā)現(xiàn)，那么算法終止。2024/1/2283寬度優(yōu)先搜索的性質(zhì)當(dāng)問(wèn)題有解時(shí)，一定能找到解當(dāng)問(wèn)題為單位代價(jià)時(shí)，且問(wèn)題有解時(shí)，一定能找到最優(yōu)解方法與問(wèn)題無(wú)關(guān)，具有通用性效率較低屬于圖搜索方法2024/1/2284寬度優(yōu)先搜索是一種盲目搜索，時(shí)間和空間復(fù)雜度都比較高，當(dāng)目的節(jié)點(diǎn)間隔初始節(jié)點(diǎn)較遠(yuǎn)時(shí)會(huì)產(chǎn)生許多無(wú)用的節(jié)點(diǎn)，搜索效率低。寬度優(yōu)先搜索中，時(shí)間需求是一個(gè)很大的問(wèn)題，特別是當(dāng)搜索的深度比較大時(shí)，尤為嚴(yán)重，但是空間需求是比執(zhí)行時(shí)間更嚴(yán)重的問(wèn)題。寬度優(yōu)先搜索優(yōu)點(diǎn)：目的節(jié)點(diǎn)假設(shè)存在，用寬度優(yōu)先搜索算法總可以找到該目的節(jié)點(diǎn)，而且是最小〔即最短途徑〕的節(jié)點(diǎn)。寬度優(yōu)先搜索的優(yōu)點(diǎn)和缺陷2024/1/2285總結(jié)適用場(chǎng)所深度優(yōu)先——當(dāng)一個(gè)問(wèn)題有多個(gè)解答或多條解答途徑，且只須找到其中一個(gè)時(shí)；往往應(yīng)對(duì)搜索深度加以限制。寬度優(yōu)先——確保搜索到最短的解答途徑。共同優(yōu)缺陷：可直接運(yùn)用普通圖搜索算法實(shí)現(xiàn)，不需求設(shè)計(jì)特別的節(jié)點(diǎn)排序方法，從而簡(jiǎn)單易行，適宜于許多復(fù)雜度不高的問(wèn)題求解義務(wù)。節(jié)點(diǎn)排序的盲目性，由于不采用領(lǐng)域?qū)ｉT(mén)知識(shí)去指點(diǎn)排序，往往會(huì)在白白搜索了大量無(wú)關(guān)的形狀節(jié)點(diǎn)后才碰到解答，所以也稱(chēng)為盲目搜索。2024/1/2286有界深度搜索和迭代加深搜索有界深度優(yōu)先搜索過(guò)程總體上按深度優(yōu)先算法方法進(jìn)展，但對(duì)搜索深度需求給出一個(gè)深度限制dm，當(dāng)深度到達(dá)了dm的時(shí)候，假設(shè)還沒(méi)有找到解答，就停頓對(duì)該分支的搜索，換到另外一個(gè)分支進(jìn)展搜索。2024/1/2287戰(zhàn)略闡明:〔1〕深度限制dm很重要。當(dāng)問(wèn)題有解，且解的途徑長(zhǎng)度小于或等于dm時(shí)，那么搜索過(guò)程一定可以找到解，但是和深度優(yōu)先搜索一樣這并不能保證最先找到的是最優(yōu)解。但是當(dāng)dm獲得太小，解的途徑長(zhǎng)度大于dm時(shí)，那么搜索過(guò)程中就找不到解，即這時(shí)搜索過(guò)程甚至是不完備的。2024/1/2288〔2〕深度限制dm不能太大。當(dāng)dm太大時(shí)，搜索過(guò)程會(huì)產(chǎn)生過(guò)多的無(wú)用節(jié)點(diǎn)，既浪費(fèi)了計(jì)算機(jī)資源，又降低了搜索效率?！?〕有界深度搜索的主要問(wèn)題是深度限制值dm的選取。2024/1/2289改良方法：〔迭代加深搜索〕先恣意給定一個(gè)較小的數(shù)作為dm，然后按有界深度算法搜索，假設(shè)在此深度限制內(nèi)找到了解，那么算法終了；如在此限制內(nèi)沒(méi)有找到問(wèn)題的解，那么增大深度限制dm，繼續(xù)搜索。2024/1/2290迭代加深搜索，試圖嘗試一切能夠的深度限制：首先深度為0，然后深度為1，然后為2，等等。假設(shè)初始深度為0，那么該算法只生成根節(jié)點(diǎn)，并檢測(cè)它。假設(shè)根節(jié)點(diǎn)不是目的，那么深度加1，經(jīng)過(guò)典型的深度優(yōu)先算法，生成深度為1的樹(shù)。當(dāng)深度限制為m時(shí)，樹(shù)的深度為m。2024/1/2291迭代加深搜索看起來(lái)會(huì)很浪費(fèi)，由于很多節(jié)點(diǎn)都能夠擴(kuò)展多次。然而對(duì)于很多問(wèn)題，這種多次的擴(kuò)展負(fù)擔(dān)實(shí)踐上很小，直覺(jué)上可以想象，假設(shè)一棵樹(shù)的分支系數(shù)很大，幾乎一切的節(jié)點(diǎn)都在最底層上，那么對(duì)于上面各層節(jié)點(diǎn)擴(kuò)展多次對(duì)整個(gè)系統(tǒng)來(lái)說(shuō)影響不是很大。2024/1/2292搜索最優(yōu)戰(zhàn)略的比較表注：b是分支系數(shù)，d是解答的深度，m是搜索樹(shù)的最大深度，l是深度限制。2024/1/2293寬度優(yōu)先搜索、深度優(yōu)先搜索和迭代加深搜索都可以用于生成和測(cè)試算法。寬度優(yōu)先搜索需求指數(shù)數(shù)量的空間，深度優(yōu)先搜索的空間復(fù)雜度和最大搜索深度呈線(xiàn)性關(guān)系。2024/1/2294迭代加深搜索對(duì)一棵深度受控的樹(shù)采用深度優(yōu)先的搜索。它結(jié)合了寬度優(yōu)先和深度優(yōu)先搜索的優(yōu)點(diǎn)。和寬度優(yōu)先搜索一樣，它是最優(yōu)的，也是完備的。但對(duì)空間要求和深度優(yōu)先搜索一樣是適中的。2024/1/2295形狀空間搜索

——2.普通圖搜索戰(zhàn)略〔2〕普通圖搜索算法常用的簡(jiǎn)一方式：深度優(yōu)先寬度優(yōu)先【缺陷：節(jié)點(diǎn)排序的盲目性】在白白搜索了大量無(wú)關(guān)的形狀節(jié)點(diǎn)后才碰到解答，效率低提高普通圖搜索效率的關(guān)鍵優(yōu)化OPEN表中節(jié)點(diǎn)的排序方式盲目搜索2024/1/2296125634最理想情況：每次排序后OPEN表表首元素n總在解答途徑上2024/1/2297啟發(fā)式搜索啟發(fā)式知識(shí)指點(diǎn)OPEN表排序的普通圖搜索：全局排序——對(duì)OPEN表中的一切節(jié)點(diǎn)排序，使最有希望的節(jié)點(diǎn)排在表首。A算法，A*算法〔掌握！〕部分排序——僅對(duì)新擴(kuò)展出來(lái)的子節(jié)點(diǎn)排序，使這些新節(jié)點(diǎn)中最有希望者能優(yōu)先取出調(diào)查和擴(kuò)展；爬山法〔了解，對(duì)深度優(yōu)先法的改良〕；2024/1/2298啟發(fā)式搜索

——1.A算法〔掌握〕【根本思想】設(shè)計(jì)表達(dá)啟發(fā)式知識(shí)的評(píng)價(jià)函數(shù)f(n)；指點(diǎn)普通圖搜索中OPEN表待擴(kuò)展節(jié)點(diǎn)的排序：【評(píng)價(jià)函數(shù)f(n)=g(n)+h(n)〔掌握〕】n-搜索圖G中的節(jié)點(diǎn)；f(n)-G中從初始形狀節(jié)點(diǎn)s，經(jīng)由節(jié)點(diǎn)n到達(dá)目的節(jié)點(diǎn)ng，估計(jì)的最小途徑代價(jià)；g(n)-G中從s到n，目前實(shí)踐的途徑代價(jià)；h(n)-從n到ng，估計(jì)的最小途徑代價(jià)；2024/1/2299啟發(fā)式搜索

——1.A算法〔掌握〕Snng目的形狀節(jié)點(diǎn)ng初始形狀節(jié)點(diǎn)S節(jié)點(diǎn)n搜索圖Gh(n):n-ng的估計(jì)最小途徑代價(jià)g(n):s-n的實(shí)踐途徑代價(jià)f(n):s-n-ng的估計(jì)最小途徑代價(jià)2024/1/22100啟發(fā)式搜索

——1.A算法〔掌握〕【評(píng)價(jià)函數(shù)f(n)=g(n)+h(n)〔掌握〕】n-搜索圖G中的節(jié)點(diǎn)；f(n)-G中從s經(jīng)n到ng，估計(jì)的最小途徑代價(jià)；g(n)-G中從s到n，目前實(shí)踐的途徑代價(jià)；h(n)-從n到ng，估計(jì)的最小途徑代價(jià)；h(n)值-依賴(lài)于啟發(fā)式知識(shí)加以計(jì)算；h(n)稱(chēng)為啟發(fā)式函數(shù)〔掌握意義！〕。如何用評(píng)價(jià)函數(shù)來(lái)實(shí)現(xiàn)A算法?〔掌握！〕2024/1/22101啟發(fā)式搜索

——1.A算法〔掌握〕A算法的設(shè)計(jì)與普通圖搜索一樣，劃分為二個(gè)階段：1、初始化建立只包含初始形狀節(jié)點(diǎn)s的搜索圖G:={s}OPEN:={s}CLOSE:={}2、搜索循環(huán)MOVE-FIRST(OPEN)-取出OPEN表首的節(jié)點(diǎn)n⑥擴(kuò)展出n的子節(jié)點(diǎn),插入搜索圖G和OPEN表⑦適當(dāng)?shù)臉?biāo)志和修正指針〔子節(jié)點(diǎn)父節(jié)點(diǎn)〕⑧排序OPEN表〔評(píng)價(jià)函數(shù)f(n)的值排序〕經(jīng)過(guò)循環(huán)地執(zhí)行該算法，搜索圖會(huì)因不斷有新節(jié)點(diǎn)參與而逐漸長(zhǎng)大，直到搜索到目的節(jié)點(diǎn)。2024/1/22102啟發(fā)式搜索

——1.A算法〔掌握〕算法A的設(shè)計(jì)與普通圖搜索類(lèi)似，劃分為二個(gè)階段：1、初始化2、搜索循環(huán)MOVE-FIRST(OPEN)-取出OPEN表首的節(jié)點(diǎn)n⑥擴(kuò)展出n的子節(jié)點(diǎn),插入搜索圖G和OPEN表對(duì)每個(gè)子節(jié)點(diǎn)ni,計(jì)算f(n,ni)=g(n,ni)+h(ni)⑦適當(dāng)?shù)臉?biāo)志和修正指針〔子節(jié)點(diǎn)父節(jié)點(diǎn)〕⑧排序OPEN表〔評(píng)價(jià)函數(shù)f(n)的值排序〕2024/1/22103啟發(fā)式搜索

——1.A算法〔掌握〕⑥擴(kuò)展出n的子節(jié)點(diǎn),插入搜索圖G和OPEN表對(duì)每個(gè)子節(jié)點(diǎn)ni,計(jì)算f(n,ni)=g(n,ni)+h(ni)⑦適當(dāng)?shù)臉?biāo)志和修正指針〔子節(jié)點(diǎn)父節(jié)點(diǎn)〕(i)全新節(jié)點(diǎn)：f(ni)=f(n,ni)(ii)已出如今OPEN表中的節(jié)點(diǎn)(iii)已出現(xiàn)的CLOSE表中的節(jié)點(diǎn)IFf(ni)>f(n,ni)THEN修正指針指向新父結(jié)點(diǎn)nf(ni)=f(n,ni)⑧排序OPEN表〔f(n)值從小到大排序〕2024/1/221042.假設(shè)OPEN表是空表，那么失敗退出；算法A3.選擇OPEN表上的第一個(gè)節(jié)點(diǎn)，把它從OPEN表移出并放進(jìn)CLOSE表中，稱(chēng)此節(jié)點(diǎn)為節(jié)點(diǎn)n；1.建立一個(gè)只包含起始節(jié)點(diǎn)S的搜索圖G,把S放到一個(gè)叫OPEN的未擴(kuò)展節(jié)點(diǎn)表中；建立一個(gè)叫做CLOSE的已擴(kuò)展節(jié)點(diǎn)表，其初始為空表；5.擴(kuò)展節(jié)點(diǎn)n，同時(shí)生成不是n的祖先的那些子節(jié)點(diǎn)的集合M,把M的這些成員作為n的后繼節(jié)點(diǎn)添入圖G中；對(duì)于M中每個(gè)子節(jié)點(diǎn)ni,計(jì)算f(n,ni)=g(n,ni)+h(ni);4.假設(shè)n為一目的節(jié)點(diǎn)，那么有解勝利退出，此解是追蹤圖G中沿著指針從n到S這條途徑而得到的；2024/1/221056.對(duì)那些未曾在G中出現(xiàn)過(guò)的M成員〔全新節(jié)點(diǎn)〕設(shè)置一個(gè)通向n的指針。把M的這些成員加進(jìn)OPEN表。對(duì)曾經(jīng)在OPEN表上的每一個(gè)M成員，比較子節(jié)點(diǎn)ni經(jīng)由新、老父節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值f(n,ni)、f(ni);假設(shè)f(n,ni)<f(ni)點(diǎn),那么令f(ni)=f(n,ni),并挪動(dòng)子節(jié)點(diǎn)指向老父節(jié)點(diǎn)的指針，改為指向新父節(jié)點(diǎn)。對(duì)已在CLOSE表上的每個(gè)M成員，作與第2類(lèi)同樣的處置，并把這些子結(jié)點(diǎn)從CLOSE表移出，重新參與OPEN表。7.按f(n)排序OPEN表中的節(jié)點(diǎn)，f(n)值最小者排在首位，重排OPEN表；8.轉(zhuǎn)2。此過(guò)程生成一個(gè)明確的圖G(搜索圖〕和一個(gè)G的子集T(搜索樹(shù)〕。2024/1/22106啟發(fā)式搜索

——1.A算法〔掌握〕A算法實(shí)例——八數(shù)碼游戲1)設(shè)計(jì)評(píng)價(jià)函數(shù)f(n)f(n)=d(n)+w(n),其中d(n)-節(jié)點(diǎn)n在搜索圖中的節(jié)點(diǎn)深度，對(duì)g(n)的度量；w(n)-代表啟發(fā)式函數(shù)h(n),其值是節(jié)點(diǎn)n與目的形狀節(jié)點(diǎn)ng相比較，不思索空格，錯(cuò)位的棋牌個(gè)數(shù)；初始規(guī)劃目的規(guī)劃挪動(dòng)數(shù)碼2024/1/22107啟發(fā)式搜索

——1.A算法〔掌握〕啟發(fā)式算法A實(shí)例——八數(shù)碼游戲1)設(shè)計(jì)評(píng)價(jià)函數(shù)f(n)f(n)計(jì)算實(shí)例初始規(guī)劃s目的規(guī)劃ngw(s):錯(cuò)位的棋牌個(gè)數(shù)d(s):當(dāng)前節(jié)點(diǎn)深度f(wàn)(s)h(n):n-ng的最小途徑代價(jià)g(n):s-n的最小途徑代價(jià)f(n):s-n-ng的最小途徑代價(jià)注：W(S)不思索空格2024/1/22108形狀空間搜索

——2.普通圖搜索戰(zhàn)略〔1〕搜索術(shù)語(yǔ)1、節(jié)點(diǎn)深度根節(jié)點(diǎn)指示初始形狀，令其深度為0；搜索圖中的其他節(jié)點(diǎn)的深度dn就可以遞歸地定義為其父節(jié)點(diǎn)深度dn-1加1：dn=dn-1+1。根節(jié)點(diǎn)深度=0第n-1層節(jié)點(diǎn)dn-1第n層節(jié)點(diǎn)dn=dn-1+1搜索圖G2024/1/22109啟發(fā)式搜索

——1.A算法〔掌握〕啟發(fā)式算法A實(shí)例——八數(shù)碼游戲1)設(shè)計(jì)評(píng)價(jià)函數(shù)f(n)f(n)計(jì)算實(shí)例初始規(guī)劃s目的規(guī)劃ngw(s):錯(cuò)位的棋牌個(gè)數(shù)d(s):當(dāng)前節(jié)點(diǎn)深度f(wàn)(s)h(n):n-ng的最小途徑代價(jià)g(n):s-n的最小途徑代價(jià)f(n):s-n-ng的最小途徑代價(jià)044注：W(S)不思索空格2024/1/22110初始化OPEN:={s4}CLOSE:={}2024/1/22111循環(huán)1CLOSE:={s4}OPEN:={a b c}OPEN:={a6 b4 c6}OPEN:={b4 a6 c6}2024/1/22112循環(huán)2CLOSE:={s4 b4}OPEN:={a6 c6 d e i}OPEN:={a6 c6 d5 e5 i6}OPEN:={d5 e5 a6 c6 i6}2024/1/22113循環(huán)3CLOSE:={s4 b4 d5}OPEN:={e5 a6 c6 i6 j k}OPEN:={e5 a6 c6 i6 j7 k6}OPEN:={e5 a6 c6 i6 k6 j7}2024/1/22114循環(huán)4CLOSE:={s4,b4,d5,e5}OPEN:={a6 c6 i6 k6 j7 l m}OPEN:={a6 c6 i6 k6 j7 l5 m7}OPEN:={l5 a6 c6 i6 k6 j7 m7}2024/1/22115CLOSE:={s4,b4,d5,e5,l5}循環(huán)5OPEN:={a6 c6 i6 k6 j7 m7 n}OPEN:={a6 c6 i6 k6 j7 m7 n5}OPEN:={n5 a6 c6 i6 k6 j7 m7}2024/1/22116循環(huán)6CLOSE:={s4,b4,d5, e5,l5,n5}OPEN:={a6 c6 i6 k6 j7 m7 o g}OPEN:={a6 c6 i6 k6 j7 m7 o7 g5}OPEN:={g5 a6 c6 i6 k6 j7 m7 o7}2024/1/22117循環(huán)7勝利終了2024/1/22118最理想搜索圖G2024/1/22119判別失誤2024/1/22120例2給定4L和3L的水壺各一個(gè)，水壺上沒(méi)有刻度，可以向水壺中加水。如何在4L的壺中準(zhǔn)確地得到2L水？〔x,y〕——4L壺里的水有xL，3L壺里的水有yL，n表示搜索空間中的任一節(jié)點(diǎn)。那么給出下面的啟發(fā)式函數(shù)：2024/1/22121h(n)=2 假設(shè)0<x<4并且0<y<3=4 假設(shè)0<x<4或者0<y<3 =8 假設(shè)x=0并且y=3 或者x=4并且y=0 =10 假設(shè)x=0并且y=0 或者x=4并且y=3假定g(n)表示搜索樹(shù)中搜索的深度，那么根據(jù)圖搜索戰(zhàn)略得以下圖的搜索空間。2024/1/22122水壺問(wèn)題的形狀空間擴(kuò)展圖在第0步，由節(jié)點(diǎn)O可以得到g+h=10。在第1步，得到兩個(gè)節(jié)點(diǎn)M和N，其估價(jià)函數(shù)值都為1+8=9，因此可以任選一個(gè)節(jié)點(diǎn)擴(kuò)展。2024/1/22123水壺問(wèn)題的形狀空間擴(kuò)展圖假定選擇了節(jié)點(diǎn)M，在第2步擴(kuò)展M得到了兩個(gè)后繼點(diǎn)P和R，對(duì)于P有2+4=6，對(duì)于R有2+10=12。如今，在節(jié)點(diǎn)P、R、N中，節(jié)點(diǎn)P具有最小的估價(jià)函數(shù)值，所以選擇節(jié)點(diǎn)P擴(kuò)展。在第3步，可以得到節(jié)點(diǎn)S，其中3+4=7。如今，在節(jié)點(diǎn)S、R、N中，節(jié)點(diǎn)S的估價(jià)函數(shù)值最小，所以下一步就會(huì)選擇S節(jié)點(diǎn)擴(kuò)展。該過(guò)程不斷進(jìn)展下去，直到到達(dá)目的節(jié)點(diǎn)。2024/1/22124啟發(fā)式搜索

——2.實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵要素〔了解〕實(shí)現(xiàn)啟發(fā)式搜索應(yīng)思索的關(guān)鍵要素：〔1〕搜索算法的可采用性(Admissibility);〔2〕啟發(fā)式函數(shù)h(n)的強(qiáng)弱及其影響；2024/1/22125啟發(fā)式搜索

——2.實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵要素〔1〕搜索算法的可采用性(Admissibility)1)定義在存在從初始形狀節(jié)點(diǎn)到目的形狀節(jié)點(diǎn)解答途徑的情況下，假設(shè)一個(gè)搜索法總能找到最短〔代價(jià)最小〕的解答途徑，那么稱(chēng)該形狀空間中的搜索算法具有可采用性，也叫最優(yōu)性。如，寬度優(yōu)先的搜索算法是可采用的，只是搜索效率不高。2)A算法的可采用性——定義f*(n)=g*(n)+h*(n)n-搜索圖G中最短解答途徑的節(jié)點(diǎn)；f*(n)-s經(jīng)節(jié)點(diǎn)n到ng的最短解答途徑的途徑代價(jià)；g*(n)-該途徑前段〔從s到n〕的途徑代價(jià)；h*(n)-該途徑后段〔從n到ng〕的途徑代價(jià)；2024/1/22126啟發(fā)式搜索

——2.實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵要素〔1〕搜索算法的可采用性(Admissibility)3)評(píng)價(jià)函數(shù)f與f*的比較f(n)、g(n)、h(n)分別是f*(n)、g*(n)、h*(n)的近似值〔估計(jì)值〕理想情況下：假設(shè)g(n)=g*(n)、h(n)=h*(n)，那么搜索過(guò)程中，每次都正確選擇，不擴(kuò)展任何無(wú)關(guān)的節(jié)點(diǎn)。實(shí)踐情況：設(shè)計(jì)接近f*的f是很困難的在算法執(zhí)行過(guò)程中，g(n)容易從曾經(jīng)生成的搜索樹(shù)中計(jì)算出來(lái)Sn搜索圖Gng2024/1/22127啟發(fā)式搜索

——2.實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵要素〔1〕搜索算法的可采用性(Admissibility)3)評(píng)價(jià)函數(shù)f與f*的比價(jià)理想情況下：假設(shè)g(n)=g*(n)、h(n)=h*(n)，不擴(kuò)展無(wú)關(guān)的節(jié)點(diǎn)實(shí)踐情況：設(shè)計(jì)接近f*的f是很困難的在算法執(zhí)行過(guò)程中，g(n)容易從曾經(jīng)生成的搜索樹(shù)中計(jì)算出來(lái)，比如就以節(jié)點(diǎn)深度d(n)當(dāng)做g(n),且有g(shù)(n)>=g*(n)h(n)盡能夠接近h*(n)——A算法的關(guān)鍵。2024/1/22128啟發(fā)式搜索

——2.實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵要素〔1〕搜索算法的可采用性(Admissibility)4)改良啟發(fā)式函數(shù)——八數(shù)碼游戲f(n)=d(n)+w(n),其中w(n)-表示錯(cuò)位的棋牌個(gè)數(shù)，不夠貼切，錯(cuò)誤的擴(kuò)展了節(jié)點(diǎn)d；p(n)-節(jié)點(diǎn)n與目的形狀節(jié)點(diǎn)比較，錯(cuò)位棋牌在不受阻攔的情況下，挪動(dòng)到目的形狀相應(yīng)位置所需走步〔挪動(dòng)次數(shù)〕的總和；p(n)比w(n)更接近于h*(n)-p(n)不僅思索了棋牌的錯(cuò)位要素，還思索了錯(cuò)位的間隔〔挪動(dòng)間隔〕2024/1/22129啟發(fā)式搜索

——2.實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵要素4)改良啟發(fā)式函數(shù)——八數(shù)碼游戲f(s)計(jì)算實(shí)例初始規(guī)劃s目的規(guī)劃ngw(s):錯(cuò)位的棋牌個(gè)數(shù)d(s):當(dāng)前節(jié)點(diǎn)深度f(wàn)(s)044p(s):錯(cuò)位棋牌挪動(dòng)間隔d(s):當(dāng)前節(jié)點(diǎn)深度f(wàn)(s)05511122024/1/22130初始化OPEN:={s5}CLOSE:={}2024/1/22131循環(huán)1CLOSE:={s5}OPEN:={a b c}OPEN:={a7 b5 c7}OPEN:={b5 a7 c7}2024/1/22132循環(huán)2CLOSE:={s5 b5}OPEN:={a7 c7 d e i}OPEN:={a7 c7 d7 e5 i7}OPEN:={e5 a7 c7 d7 i7}2024/1/22133循環(huán)3CLOSE:={s5 b5 e5}OPEN:={a7 c7 d7 i7 l m}OPEN:={a7 c7 d7 i7 l5 m7}OPEN:={l5 a7 c7 d7 i7 m7}2024/1/22134CLOSE:={s5,b5,e5,l5}循環(huán)4OPEN:={a7 c7 d7 i7 m7 n}OPEN:={a7 c7 d7 i7 m7 n5}OPEN:={n5 a7 c7 d7 i7 m7}2024/1/22135CLOSE:={s5,b5, e5,l5, n5}循環(huán)5OPEN:={a7 c7 d7 i7 m7 o g}OPEN:={a7 c7 d7 i7 m7 o7 g5}OPEN:={g5 a7 c7 d7 i7 m7 o7}2024/1/22136循環(huán)6勝利終了最理想搜索圖G2024/1/22137防止了錯(cuò)誤選擇2024/1/22138啟發(fā)式搜索

——2.實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵要素〔1〕搜索算法的可采用性(Admissibility)5)A*算法定義：1、在A(yíng)算法中，規(guī)定h(n)≤h*(n);2、經(jīng)如此限制以后的A算法就是A*算法。A*算法是可采用的，即總能搜索到最短解答途徑【回想：八數(shù)碼游戲的h(n)】w(n)-錯(cuò)位的棋牌個(gè)數(shù)p(n)-錯(cuò)位棋牌在不受阻攔的情況下，挪動(dòng)到目的形狀相應(yīng)位置所需走步〔挪動(dòng)次數(shù)〕的總和；2024/1/22139啟發(fā)式搜索

——2.實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵要素〔1〕搜索算法的可采用性(Admissibility)5)A*算法定義：1、在A(yíng)算法中，規(guī)定h(n)≤h*(n);2、經(jīng)如此限制以后的A算法就是A*算法。A*算法是可采用的，即總能搜索到最短解答途徑證明：【<人工智能上冊(cè)>陸汝鈐P248】1〕假設(shè)存在一條從初始形狀到目的形狀的解答途徑，那么一定存在一條最短解答通路；2〕設(shè)形狀n’是最短解答途徑上的一個(gè)形狀，那么經(jīng)過(guò)有限步后，n’必然會(huì)成為OPEN表的第一個(gè)節(jié)點(diǎn)；3〕由于最短解答途徑只需有限個(gè)節(jié)點(diǎn)n’，所以有限步后算法必然因到達(dá)目的形狀ng。這就是最優(yōu)解。證明終了。2024/1/22140啟發(fā)式搜索

——2.實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵要素〔1〕搜索算法的可采用性(Admissibility)5)滿(mǎn)足可采用性條件的算法——A*算法證明：2〕設(shè)形狀n’是最短解答途徑上的一個(gè)形狀，那么經(jīng)過(guò)有限步后，n’必然會(huì)成為OPEN表的第一個(gè)節(jié)點(diǎn)；f(n’)=g(n’)+h(n’)∵根據(jù)假設(shè)，n’在最短解答途徑上∴經(jīng)過(guò)有限步驟后，g(n’)=g*(n’)∴f(n’)=g*(n’)+h(n’)∵h(yuǎn)(n)≤h*(n)∴f(n’)=g*(n’)+h(n’)≤g*(n’)+h*(n’)=f*(n’)∵f*(n’)=f*(ng)∴f(n’)≤f*(ng)2024/1/22141啟發(fā)式搜索

——2.實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵要素〔1〕搜索算法的可采用性(Admissibility)5)滿(mǎn)足可采用性條件的算法——A*算法證明：2〕設(shè)形狀n’是最短解答途徑上的一個(gè)形狀，那么經(jīng)過(guò)有限步后，n’必然會(huì)成為OPEN表的第一個(gè)節(jié)點(diǎn)；設(shè)OPEN表中n’之前的節(jié)點(diǎn)只需有限個(gè)，設(shè)為N個(gè)，其中估計(jì)值最小者為a1，并稱(chēng)之為第一代節(jié)點(diǎn)；由第一代節(jié)點(diǎn)生成的節(jié)點(diǎn)稱(chēng)為第二代節(jié)點(diǎn)，其中估計(jì)值最小者為a2；a2≥a1+e(其中，e>0，表示每擴(kuò)展一次起碼的代價(jià))擴(kuò)展j代后，aj≥a1+(j-1)e當(dāng)j足夠大時(shí)一定有aj>f*(ng)∵f(n’)≤f*(ng)且OPEN表中n’之前的節(jié)點(diǎn)經(jīng)過(guò)j次擴(kuò)展后的最小估計(jì)值aj>f*(ng)≥f(n’)∴經(jīng)過(guò)有限步后，n’必然會(huì)成為OPEN表的第一個(gè)節(jié)點(diǎn)2024/1/22142啟發(fā)式搜索

——2.實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵要素〔2〕啟發(fā)式函數(shù)的強(qiáng)弱及其影響h(n)接近h*(n)的程度——衡量啟發(fā)式函數(shù)的強(qiáng)弱h(n)<h*(n)且差距較大時(shí)，OPEN表中節(jié)點(diǎn)排序的誤差較大，h(n)過(guò)弱，產(chǎn)生較大的搜索圖；h(n)>h*(n)，h(n)過(guò)強(qiáng)，A算法失去可采用性，不能確保找到最短解答途徑；h(n)=h*(n)是最理想的，OPEN表中節(jié)點(diǎn)排序沒(méi)有誤差，可以確保產(chǎn)生最小的搜索圖，搜索到最短解答途徑；無(wú)法設(shè)計(jì)A*算法搜索問(wèn)題解答的關(guān)鍵h(n)在滿(mǎn)足h(n)≤h*(n)的條件下，越大越好！2024/1/22143啟發(fā)式搜索

——2.實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵要素〔2〕啟發(fā)式函數(shù)的強(qiáng)弱及其影響定理：處理同一問(wèn)題的兩個(gè)A*算法A1和A2，假設(shè)h1(n)≤h2(n)≤h*(n)且g1(n)=g2(n)那么t(A1)≥t(A2)其中，h1、h2分別是算法A1、A2的啟發(fā)式函數(shù)，t指示相應(yīng)算法到達(dá)目的形狀時(shí)搜索圖含的節(jié)點(diǎn)總數(shù)?！咀C明：<人工智能上冊(cè)>陸汝鈐P250〕】八數(shù)碼游戲：w(n)≤p(n)≤h*(n)p(n)擴(kuò)展出的節(jié)點(diǎn)總數(shù)≤t(w(n))2024/1/22144迭代加深A(yù)*算法由于A(yíng)*算法把一切生成的節(jié)點(diǎn)保管在內(nèi)存中，所以A*算法在耗盡計(jì)算時(shí)間之前普通早曾經(jīng)把空間耗盡了。目前開(kāi)發(fā)了一些新的算法，它們的目的是為了抑制空間問(wèn)題。但普通不滿(mǎn)足最優(yōu)性或完備性，如迭代加深A(yù)*算法IDA*、簡(jiǎn)化內(nèi)存受限A*算法SMA*等。下面簡(jiǎn)單引見(jiàn)IDA*算法。2024/1/22145迭代加深搜索算法，它以深度優(yōu)先的方式在有限制的深度內(nèi)搜索目的節(jié)點(diǎn)。在每個(gè)深度上，該算法在每個(gè)深度上檢查目的節(jié)點(diǎn)能否出現(xiàn)，假設(shè)出現(xiàn)那么停頓，否那么深度加1繼續(xù)搜索。而A*算法是選擇具有最小估價(jià)函數(shù)值的節(jié)點(diǎn)擴(kuò)展。2024/1/22146迭代加深A(yù)*搜索算法IDA*是上述兩種算法的結(jié)合。這里啟發(fā)式函數(shù)用做深度的限制，而不是選擇擴(kuò)展節(jié)點(diǎn)的排序。2024/1/22147迭代加深A(yù)*算法ProcedureIDA*算法 Begin(1)初始化當(dāng)前的深度限制c=1(2)把初始節(jié)點(diǎn)壓入棧;并假定(3)While棧不空橋doBegin 彈出棧頂元素nIfn=goal,Then終了,前往n以及從初始節(jié)點(diǎn)到n的途徑ElsedoBeginForn的每個(gè)子節(jié)點(diǎn)If,Then把壓入棧Else EndforEndEndWhile(4)If棧為空并且,Then停頓并退出(5)If棧為空并且,Then,并前往2End2024/1/22148IDA*算法和A*算法相比，主要優(yōu)點(diǎn)是對(duì)于內(nèi)存的需求。A*算法需求指數(shù)級(jí)數(shù)量的存儲(chǔ)空間，由于沒(méi)有深度方面的限制。而IDA*算法只需當(dāng)節(jié)點(diǎn)n的一切子節(jié)點(diǎn)的小于限制值c時(shí)才擴(kuò)展它,這樣就可以節(jié)省大量的內(nèi)存。另一問(wèn)題是當(dāng)啟發(fā)式函數(shù)是最優(yōu)的時(shí)候，IDA*算法和A*算法擴(kuò)展一樣的節(jié)點(diǎn)，并且可以找到最優(yōu)途徑。特點(diǎn)2024/1/22149啟發(fā)式搜索啟發(fā)式知識(shí)指點(diǎn)OPEN表排序的普通圖搜索：全局排序——對(duì)OPEN表中的一切節(jié)點(diǎn)排序，使最有希望的節(jié)點(diǎn)排在表首。A算法，A*算法〔掌握！〕部分排序——僅對(duì)新擴(kuò)展出來(lái)的子節(jié)點(diǎn)排序，使這些新節(jié)點(diǎn)中最有希望者能優(yōu)先取出調(diào)查和擴(kuò)展；爬山法〔了解，對(duì)深度優(yōu)先法的改良〕；2024/1/22150簡(jiǎn)單的搜索戰(zhàn)略：g(n)≡0,f(n)=h(n),部分排序——只排序新擴(kuò)展出來(lái)的子節(jié)點(diǎn)，即部分排序簡(jiǎn)單易行，適用于不要求最優(yōu)解答的問(wèn)題求解義務(wù)。1〕爬山法——實(shí)現(xiàn)啟發(fā)式搜索的最簡(jiǎn)一方法。類(lèi)似于人爬山——只需好爬，總是選取最陡處，以求快速登頂。求函數(shù)極大值問(wèn)題——非數(shù)值解法，依賴(lài)于啟發(fā)式知識(shí)，試探性地逐漸向頂峰逼近適用于能逐漸求精的問(wèn)題。爬山法特點(diǎn)：只能向上，不準(zhǔn)后退，從而簡(jiǎn)化了搜索算法；表達(dá)在：*從當(dāng)前形狀節(jié)點(diǎn)擴(kuò)展出的子節(jié)點(diǎn)〔相當(dāng)于找到上爬的途徑〕中，將h(n)最小的子節(jié)點(diǎn)〔對(duì)應(yīng)于到頂峰最近的上爬途徑〕作為下一次調(diào)查和擴(kuò)展的節(jié)點(diǎn)，其他子節(jié)點(diǎn)全部丟棄。不需設(shè)置OPEN和CLOSE表，由于沒(méi)有必要保管任何待擴(kuò)展節(jié)點(diǎn)；爬山法對(duì)于單一極值問(wèn)題〔登單一山峰〕非常有效而又簡(jiǎn)便,對(duì)于具有多極值的問(wèn)題無(wú)能為力——會(huì)錯(cuò)登上次頂峰而失?。翰荒艿竭_(dá)最頂峰?；厮輵?zhàn)略和爬山法2024/1/2215110J(0,1)用梯度下降算法最小化代價(jià)函數(shù)J(0,1)2024/1/2215201J(0,1)2024/1/221532024/1/221542〕回溯戰(zhàn)略可以有效地抑制爬山法面臨的困難——保管了每次擴(kuò)展出的子節(jié)點(diǎn)，并按h(n)值從小到大陳列。相當(dāng)于爬山的過(guò)程中記住了途經(jīng)的岔路口——途徑搜索失敗時(shí)回溯〔后退〕，向另一途徑方向搜索回溯戰(zhàn)略和爬山法2024/1/221552〕回溯戰(zhàn)略遞歸過(guò)程——實(shí)現(xiàn)回溯戰(zhàn)略的有效方式算法名為BACKTRACK(n),參數(shù)n為當(dāng)前被擴(kuò)展的節(jié)點(diǎn)，初次調(diào)用時(shí)n即為初始形狀節(jié)點(diǎn)s；分兩個(gè)部分：*判別當(dāng)前節(jié)點(diǎn)n的形狀，*作搜索任務(wù)——擴(kuò)展節(jié)點(diǎn)n，遞歸調(diào)用該算法，處置前往結(jié)果。回溯戰(zhàn)略和爬山法2024/1/22156令PATH、SNL、n、n'為部分變量：·PATH--節(jié)點(diǎn)列表，指示解答途徑；·SNL--當(dāng)前節(jié)點(diǎn)擴(kuò)展出的子節(jié)點(diǎn)列表；·MOVE-FIRST(SNL)--把SNL表首的節(jié)點(diǎn)移出，作為下一次要加以擴(kuò)展的節(jié)點(diǎn)；·n、n‘--分別指示當(dāng)前調(diào)查和下一次調(diào)查的節(jié)點(diǎn)。該遞歸過(guò)程的算法就取名為BACKTRACK(n),參數(shù)n為當(dāng)前被擴(kuò)展的節(jié)點(diǎn)，算法的初次調(diào)用式是BACKTRACK(s),s即為初始形狀節(jié)點(diǎn)。算法的步驟如下：〔1〕假設(shè)n是目的形狀節(jié)點(diǎn)，那么算法的本次調(diào)用勝利終了，前往空表；〔2〕假設(shè)n是失敗形狀，那么算法的本次調(diào)用失敗終了，前往'FAIL'；〔3〕擴(kuò)展節(jié)點(diǎn)n，將生成的子節(jié)點(diǎn)置于列表SNL，并按評(píng)價(jià)函數(shù)f(k)=h(k)的值從小到大排序〔k指示子節(jié)點(diǎn)〕；〔4〕假設(shè)SNL為空，那么算法的本次調(diào)用失敗終了，前往'FAIL'；〔5〕n'=MOVE-FIRST(SNL)；〔6〕PATH=BACKTRACK(n')；〔7〕假設(shè)PATH='FAIL',前往到語(yǔ)句〔4〕；〔8〕將n'加到PATH表首，算法的本次調(diào)用勝利終了，前往PATH。2024/1/221572〕回溯戰(zhàn)略三種失敗形狀：不合法形狀〔如傳教士和野人問(wèn)題中所述的那樣〕舊形狀重現(xiàn)〔如八數(shù)碼游戲中某一棋盤(pán)規(guī)劃的重現(xiàn)，會(huì)導(dǎo)致搜索算法死循環(huán)〕，形狀節(jié)點(diǎn)深度超越預(yù)定限制〔例如八數(shù)碼游戲中，指示解答途徑不超越6步〕?；厮輻l件失敗形狀，由算法第〔2〕句指示；搜索進(jìn)入“死胡同〞，由該算法的第(4)句定義。回溯戰(zhàn)略和爬山法2024/1/221582〕回溯戰(zhàn)略解答途徑的生成——從相應(yīng)于目的形狀節(jié)點(diǎn)的空表開(kāi)場(chǎng)，遞歸前往PATH。影響回溯算法效率的關(guān)鍵要素——回溯次數(shù)?；厮荨阉鞯绞⌒螤顣r(shí)的一種彌補(bǔ)行為，準(zhǔn)確選擇下一步搜索調(diào)查的節(jié)點(diǎn)——大幅度減少甚至防止回溯。設(shè)計(jì)好的啟發(fā)式函數(shù)h(n)是至關(guān)重要的?；厮輵?zhàn)略和爬山法2024/1/22159問(wèn)題歸約問(wèn)題歸約是人求解問(wèn)題常用的戰(zhàn)略：把復(fù)雜的問(wèn)題變換為假設(shè)干需求同時(shí)處置的較為簡(jiǎn)單的子問(wèn)題后再加以分別求解只需子問(wèn)題全部處理時(shí)，問(wèn)題才算處理；問(wèn)題的解答由子問(wèn)題的解答結(jié)合構(gòu)成。本節(jié)主要內(nèi)容：?jiǎn)栴}歸約的描畫(huà)〔了解〕與或圖搜索的根本過(guò)程〔了解〕與或圖的啟發(fā)式搜索〔掌握〕2024/1/22160問(wèn)題歸約法

〔ProblemReductionRepresentation〕子問(wèn)題1子問(wèn)題n原始問(wèn)題子問(wèn)題集本原問(wèn)題2024/1/22161問(wèn)題歸約可以用三元組表示：〔S0，O，P〕，其中S0是初始問(wèn)題，即要求解的問(wèn)題；P是本原問(wèn)題集，其中的每一個(gè)問(wèn)題是不用證明的，自然成立的，如公理、知現(xiàn)實(shí)等，或已證明過(guò)的問(wèn)題；O是操作算子集，它是一組變換規(guī)那么，經(jīng)過(guò)一個(gè)操作算子把一個(gè)問(wèn)題化成假設(shè)干個(gè)子問(wèn)題。2024/1/22162問(wèn)題歸約表示方法就是由初始問(wèn)題出發(fā)，運(yùn)用操作算子產(chǎn)生一些子問(wèn)題，對(duì)子問(wèn)題再運(yùn)用操作算子產(chǎn)生子問(wèn)題的子問(wèn)題，這樣不斷進(jìn)展到產(chǎn)生的問(wèn)題均為本原問(wèn)題，那么問(wèn)題得解。2024/1/22163看如下符號(hào)積分問(wèn)題： 初始問(wèn)題——∫f(x)dx 變換規(guī)那么——積分規(guī)那么 本原問(wèn)題——可直接求原函數(shù)和積分，如∫sin(x)dx，∫cos(x)dx等。 一切問(wèn)題歸約的最終目的是產(chǎn)生本原問(wèn)題。2024/1/22164

符號(hào)積分問(wèn)題

∫〔sin3x+x4/(x2+1)〕dx

=∫sin3xdx+∫(x4/(x2+1))dx

=∫-(1-cos2x)dcosx+∫(x2-1+1/(1+x2))dx

=(∫-dcosx+cos2xdcosx)+(∫x2dx-∫dx+∫(1/(1+x2))dx〕

=-cosx+cos3x/3+x3/3-x+arctgx

2024/1/22165分子構(gòu)造識(shí)別問(wèn)題

如何區(qū)分分子式一樣但分子構(gòu)造不同的有機(jī)化合物成為重要而又困難的問(wèn)題。著名的專(zhuān)家系統(tǒng)DENDRAL能用于有效地識(shí)別分子構(gòu)造，該系統(tǒng)建立了一套重寫(xiě)規(guī)那么去把分子式重寫(xiě)為原子數(shù)較少的分子式和原子間結(jié)合關(guān)系的混合構(gòu)造2024/1/22166問(wèn)題歸約的本質(zhì)：從目的(要處理的問(wèn)題)出發(fā)逆向推理，建立子問(wèn)題以及子問(wèn)題的子問(wèn)題，直至最后把初始問(wèn)題歸約為一個(gè)平凡的本原問(wèn)題集合。2024/1/22167運(yùn)用問(wèn)題歸約戰(zhàn)略得到的形狀空間圖，也稱(chēng)為“與或圖〞邏輯“與〞關(guān)系——用圓弧將幾條節(jié)點(diǎn)間關(guān)聯(lián)弧銜接在一同表示問(wèn)題分解為子問(wèn)題；子問(wèn)題的形狀結(jié)合起來(lái)構(gòu)成問(wèn)題形狀。子問(wèn)題全部處理才會(huì)導(dǎo)致問(wèn)題的處理；邏輯“或〞關(guān)系：①問(wèn)題可以有多種分解方式；②問(wèn)題〔子問(wèn)題〕能夠激活多個(gè)形狀變化操作；只需一種分解方式或形狀變化操作能導(dǎo)致最終的解答勝利即可；導(dǎo)致多個(gè)能夠的解答。與或圖2024/1/22168用AND-OR圖把問(wèn)題歸約為子問(wèn)題交換集合。如，假設(shè)問(wèn)題A既可經(jīng)過(guò)問(wèn)題C1與C2，也可經(jīng)過(guò)問(wèn)題C3、C4和C5，或者由單獨(dú)求解問(wèn)題C6來(lái)處理，如以下圖所示。圖中各節(jié)點(diǎn)表示要求解的問(wèn)題或子問(wèn)題。與或圖2024/1/22169梵塔問(wèn)題問(wèn)題描畫(huà)：初始形狀下三個(gè)盤(pán)按A、B、C順序堆放在1號(hào)柱子上；目的形狀下三個(gè)盤(pán)以同樣次序順序堆放在3號(hào)柱子上；盤(pán)子的搬移規(guī)那么：每次只能搬一個(gè)盤(pán)子；較大盤(pán)不能壓放在較小盤(pán)之上；CAB初始形狀(111)目的形狀(333)CAB132132與或圖2024/1/22170梵塔問(wèn)題——形狀空間圖(1,1,1)(3,3,3)(1,1,1)(2,2,1)(2,2,1)(2,2,3)(2,2,3)(3,3,3)(2,2,1)132CAB(2,2,3)123ABC目的形狀(333)CAB1322024/1/22171梵塔問(wèn)題——形狀空間圖(1,1,1)(3,3,3)(1,1,1)(2,2,1)(2,2,1)(2,2,3)(2,2,3)(3,3,3)(1,1,1)(3,1,1)(3,2,1)(2,2,1)(3,1,1)(3,2,1)(1,2,3)(1,3,3)(2,2,3)(1,2,3)(1,3,3)(3,3,3)2024/1/2217