《人工智能》（何澤奇）491-6教案 第7課 搜索概述與盲目搜索策略

PAGE10PAGE10PAGE13PAGE13課題搜索概述與盲目搜索策略課時(shí)2課時(shí)（90min）教學(xué)目標(biāo)知識(shí)技能目標(biāo)：（1）熟悉搜索的基本內(nèi)容（2）理解搜索策略的思想（3）學(xué)會(huì)利用自然演繹推理解決問(wèn)題思政育人目標(biāo)：關(guān)注人工智能的最新技術(shù)，推理的相關(guān)知識(shí)，增強(qiáng)探究意識(shí)了解科技前沿新應(yīng)用，開闊視野，抓住機(jī)遇，展現(xiàn)新作為關(guān)注卓越新科技，感受國(guó)家的發(fā)展、民族的強(qiáng)大，增強(qiáng)民族意識(shí)，加深愛(ài)黨、愛(ài)國(guó)的情感教學(xué)重難點(diǎn)教學(xué)重點(diǎn)：搜索的概念、搜索過(guò)程教學(xué)難點(diǎn)：搜索策略的思想教學(xué)方法講授法、討論法、問(wèn)答法教學(xué)用具計(jì)算機(jī)、投影儀、多媒體課件、教材教學(xué)設(shè)計(jì)→→→傳授新知（20min）→→傳授新知（50min）→課堂練習(xí)（7min）→課堂小結(jié)（3min）→作業(yè)布置（2min）教學(xué)過(guò)程主要教學(xué)內(nèi)容及步驟設(shè)計(jì)意圖課前任務(wù)【教師】布置課前任務(wù)，和學(xué)生負(fù)責(zé)人取得聯(lián)系，讓其提醒同學(xué)通過(guò)文旌課堂APP或其他學(xué)習(xí)軟件，完成課前任務(wù)使用搜索引擎搜索一下自己感興趣的內(nèi)容并結(jié)合具體實(shí)際，說(shuō)說(shuō)什么是搜索？【學(xué)生】完成課前任務(wù)通過(guò)課前任務(wù)，使學(xué)生了解本次課程的重點(diǎn)，增加學(xué)生的學(xué)習(xí)興趣考勤

（2min）【教師】通過(guò)文旌課堂APP讓學(xué)生簽到【學(xué)生】簽到，班干部交假條培養(yǎng)學(xué)生的組織紀(jì)律性，掌握學(xué)生的出勤情況問(wèn)題導(dǎo)入（3min）【教師】提出以下問(wèn)題，并邀請(qǐng)學(xué)生回答在求解實(shí)際問(wèn)題的過(guò)程中，常遇到以下兩個(gè)問(wèn)題。（1）如何尋找可利用的知識(shí)，即如何確定推理路線，才能在盡量少付出代價(jià)的前提下圓滿解決問(wèn)題。（2）如果存在多條路線可求解問(wèn)題，如何從中選出一條求解代價(jià)最小的路徑，以提高求解程序的運(yùn)行效率。怎樣解決上述問(wèn)題？【學(xué)生】討論、舉手回答【教師】通過(guò)學(xué)生的回答引入要講的知識(shí)，并板書搜索為解決上述問(wèn)題，常采用搜索法求解問(wèn)題。搜索就是根據(jù)問(wèn)題的實(shí)際情況，按照一定的策略或規(guī)則，從知識(shí)庫(kù)中尋找可利用的知識(shí)，從而構(gòu)造出一條代價(jià)較小的推理路線，使問(wèn)題得到解決的過(guò)程。本節(jié)課主要介紹搜索的相關(guān)知識(shí)?！緦W(xué)生】聆聽(tīng)通過(guò)問(wèn)題導(dǎo)入的方法，引導(dǎo)學(xué)生主動(dòng)思考，激發(fā)學(xué)生的學(xué)習(xí)興趣傳授新知

（20min）4.1搜索概述4.1.1搜索的概念【教師】提問(wèn)：什么是搜索？【學(xué)生】討論、舉手回答【教師】總結(jié)搜索是人工智能中的一個(gè)核心技術(shù)，是推理不可分割的一部分，它直接關(guān)系到智能系統(tǒng)的性能和運(yùn)行效率。在搜索問(wèn)題中，主要的工作是找到正確的搜索策略。搜索策略反映了狀態(tài)空間或問(wèn)題空間擴(kuò)展的方法，也決定了狀態(tài)或問(wèn)題的訪問(wèn)順序。4.1.2搜索過(guò)程狀態(tài)空間表示法用圖結(jié)構(gòu)來(lái)描述問(wèn)題的所有可能狀態(tài)，其問(wèn)題的求解過(guò)程可轉(zhuǎn)化為在狀態(tài)空間圖中尋找一條從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑。搜索策略可看成是一種在狀態(tài)空間圖中尋找路徑的方法。在人工智能中，通過(guò)運(yùn)用搜索策略解決問(wèn)題的基本思想是：首先把問(wèn)題的初始狀態(tài)（即起始節(jié)點(diǎn)）作為當(dāng)前狀態(tài)，選擇適用的操作符對(duì)其進(jìn)行操作，生成一組子狀態(tài)（即后繼節(jié)點(diǎn)），然后檢查目標(biāo)狀態(tài)是否在其中出現(xiàn)。若出現(xiàn)，則搜索成功，找到了問(wèn)題的解；若未出現(xiàn)，則按某種搜索策略從已生成的狀態(tài)中再選一個(gè)狀態(tài)作為當(dāng)前狀態(tài)。重復(fù)上述過(guò)程，直到目標(biāo)狀態(tài)出現(xiàn)或者不再有可供操作的狀態(tài)及操作符為止。【教師】PPT展示“搜索過(guò)程”圖片，并講解搜索過(guò)程在運(yùn)用搜索策略求解問(wèn)題的過(guò)程中，涉及的數(shù)據(jù)結(jié)構(gòu)除了狀態(tài)空間圖之外，還需要兩個(gè)輔助的數(shù)據(jù)結(jié)構(gòu)，即存放已訪問(wèn)但未擴(kuò)展節(jié)點(diǎn)的OPEN表，以及存放已擴(kuò)展節(jié)點(diǎn)的CLOSED表。狀態(tài)空間圖的搜索過(guò)程【學(xué)生】聆聽(tīng)、理解（1）建立一個(gè)只含起始節(jié)點(diǎn)S0的搜索圖，并將S0放入OPEN表中。（2）建立一個(gè)CLOSED表，并將其初始化為空表。（3）判斷OPEN表是否為空表，若為空表，則失敗退出；否則繼續(xù)（4）。（4）選擇OPEN表上的第一個(gè)節(jié)點(diǎn)（稱為節(jié)點(diǎn)n），將其從OPEN表移出，并放入CLOSED表中。（5）判斷節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若n為目標(biāo)節(jié)點(diǎn)，則有解并成功退出，此解為沿著指針從節(jié)點(diǎn)n到S0的這條路徑[指針將在第（7）步中設(shè)置]。否則，執(zhí)行（6）。（6）擴(kuò)展節(jié)點(diǎn)n，生成后繼節(jié)點(diǎn)集合M，并將集合M中的成員作為n的后繼節(jié)點(diǎn)添加入搜索圖中。（7）針對(duì)M中后繼節(jié)點(diǎn)的不同情況，分別做如下處理。①對(duì)那些未曾在搜索圖中出現(xiàn)過(guò)的（既未曾在OPEN表中，也未在CLOSED表中出現(xiàn)過(guò)）M成員，設(shè)置其父節(jié)點(diǎn)指針指向n，并加入OPEN表中。②對(duì)那些原來(lái)已在搜索圖中出現(xiàn)過(guò)，但還沒(méi)有擴(kuò)展的（已經(jīng)在OPEN表或CLOSED表中出現(xiàn)過(guò)）M成員，確定是否需要將其原來(lái)的父節(jié)點(diǎn)更改為n。③對(duì)那些先前已在搜索圖中出現(xiàn)過(guò)，并已經(jīng)擴(kuò)展了的（已在CLOSED表中）M成員，確定是否需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。若修改了其父節(jié)點(diǎn)，則將該節(jié)點(diǎn)從CLOSED表中移出，重新加入OPEN表中?！窘處煛刻嵝眩荷鲜黾螹中后繼節(jié)點(diǎn)的3種情況分別是：①中提到的M成員是新生成的；②中提到的M成員是原生成但未擴(kuò)展的；③中提到的M成員是原生成并已擴(kuò)展的。（8）按某一方式或按某個(gè)估價(jià)值，重排OPEN表。繼續(xù)執(zhí)行步驟（3）。上述搜索過(guò)程可生成一個(gè)搜索圖。不同的搜索策略可得到不同的搜索樹。其中，搜索樹是搜索圖的一個(gè)子集。在搜索樹中，除初始節(jié)點(diǎn)S0外，任意一個(gè)節(jié)點(diǎn)都含有唯一一個(gè)指向其父節(jié)點(diǎn)的指針。從目標(biāo)節(jié)點(diǎn)開始，將指針指向的狀態(tài)回串起來(lái)，即找到一條求解路徑。【教師】重點(diǎn)強(qiáng)調(diào)在搜索過(guò)程中需要解決的基本問(wèn)題有：（1）搜索過(guò)程是否一定能找到一個(gè)解。（2）當(dāng)搜索過(guò)程找到一個(gè)解時(shí)，找到的是否是最佳解。（3）搜索過(guò)程的時(shí)間與空間復(fù)雜性如何。（4）搜索過(guò)程是否能終止運(yùn)行或是否會(huì)陷入一個(gè)死循環(huán)。4.1.3搜索策略根據(jù)搜索過(guò)程中是否運(yùn)用與問(wèn)題有關(guān)的信息，可以將搜索策略分為盲目搜索策略和啟發(fā)式搜索策略。在搜索過(guò)程中對(duì)OPEN表的節(jié)點(diǎn)排序，主要目的是希望從未擴(kuò)展節(jié)點(diǎn)中選出一個(gè)最具有希望的節(jié)點(diǎn)作為下一個(gè)擴(kuò)展節(jié)點(diǎn)使用。若此時(shí)的排序是任意的或者是盲目的，則為盲目搜索；若排序是以各種啟發(fā)式思想或其他準(zhǔn)則為依據(jù)的，則為啟發(fā)式搜索?！窘處煛刻嵝眩好つ克阉鞑呗砸话悴恍枰嘏臤PEN表，啟發(fā)式搜索策略需要根據(jù)不同的規(guī)則重排OPEN表?！窘處煛恐v解匠心筑夢(mèng)相關(guān)內(nèi)容【學(xué)生】聆聽(tīng)、記錄、理解通過(guò)教師的講解和課堂互動(dòng)，使學(xué)生總結(jié)搜索的概念教師結(jié)合例子講解推理的方式以及分類課堂思政，加強(qiáng)學(xué)生的國(guó)家榮譽(yù)感和知識(shí)應(yīng)用方向，了解最新技術(shù)。新知導(dǎo)入（3min）【教師】講解新的知識(shí)盲目搜索策略又稱無(wú)信息搜索策略，也就是說(shuō)，在搜索過(guò)程中，只按照預(yù)先規(guī)定的搜索策略進(jìn)行搜索，而沒(méi)有任何中間信息來(lái)改變這些策略。常用的盲目搜索策略有寬度優(yōu)先搜索、深度優(yōu)先搜索和等代價(jià)搜索等。【學(xué)生】聆聽(tīng)【教師】導(dǎo)入新的知識(shí)點(diǎn)：盲目搜索策略通過(guò)導(dǎo)入環(huán)節(jié)，激發(fā)學(xué)生的學(xué)習(xí)興趣傳授新知（50min）4.2盲目搜索策略【教師】講解盲目搜索策略盲目搜索策略又稱無(wú)信息搜索策略，也就是說(shuō)，在搜索過(guò)程中，只按照預(yù)先規(guī)定的搜索策略進(jìn)行搜索，而沒(méi)有任何中間信息來(lái)改變這些策略。常用的盲目搜索策略有寬度優(yōu)先搜索、深度優(yōu)先搜索和等代價(jià)搜索等。4.2.1寬度優(yōu)先搜索【教師】安排學(xué)生掃描二維碼“寬度優(yōu)先搜索”，了解寬度優(yōu)先搜索的過(guò)程【學(xué)生】掃碼觀看、了解寬度優(yōu)先搜索又稱廣度優(yōu)先搜索，其基本思想是從起始節(jié)點(diǎn)開

始，逐層對(duì)節(jié)點(diǎn)進(jìn)行依次擴(kuò)展（或搜索），同時(shí)考察它是否為目標(biāo)節(jié)

點(diǎn)?！窘處煛刻嵝眩涸趯?duì)下層節(jié)點(diǎn)進(jìn)行擴(kuò)展（或搜索）之前，必須完成對(duì)當(dāng)前層所有節(jié)點(diǎn)的擴(kuò)展（或搜索）。【教師】用PPT展示“寬度優(yōu)先搜索”圖片，進(jìn)行舉例說(shuō)明例如，如圖4-2所示的搜索樹，其搜索順序應(yīng)為

?！緦W(xué)生】聆聽(tīng)、理解【教師】講解寬度優(yōu)先搜索算法【教師】用PPT展示“寬度優(yōu)先搜索算法”圖片，進(jìn)行講解寬度優(yōu)先搜索的搜索過(guò)程可用圖示算法進(jìn)行描述?！緦W(xué)生】聆聽(tīng)、理解【教師】用PPT展示“貓和老鼠的位置表示”圖片，進(jìn)行提問(wèn)貓捉老鼠問(wèn)題，貓位于A處，它發(fā)現(xiàn)K處有一只老鼠，請(qǐng)用寬度優(yōu)先搜索算法幫貓尋找捕捉路線?！緦W(xué)生】舉手回答【教師】總結(jié)講解使用寬度優(yōu)先搜索算法解決貓捉老鼠問(wèn)題的步驟如下。（1）貓所在的位置A是起始節(jié)點(diǎn)，將A放入OPEN表中。（2）判斷該起始節(jié)點(diǎn)A是否為一目標(biāo)節(jié)點(diǎn)，若是，則求得一個(gè)解并成功退出；否則繼續(xù)。節(jié)點(diǎn)A不是老鼠所在的位置，所以不是目標(biāo)節(jié)點(diǎn)。（3）判斷OPEN表是否為空表，若是空表，則沒(méi)有解，失敗退出；否則繼續(xù)。OPEN表中有節(jié)點(diǎn)A，非空，繼續(xù)執(zhí)行。（4）把OPEN表中的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）移出，并放入CLOSED表中。將節(jié)點(diǎn)A從OPEN表中移出，并放入CLOSED表中。（5）判斷節(jié)點(diǎn)n是否有后繼節(jié)點(diǎn)，若有，則繼續(xù)；否則，轉(zhuǎn)向（3）。節(jié)點(diǎn)A有后繼節(jié)點(diǎn)，繼續(xù)執(zhí)行。（6）擴(kuò)展節(jié)點(diǎn)n，把節(jié)點(diǎn)n的所有后繼節(jié)點(diǎn)放入OPEN表的末端，并提供從這些后繼節(jié)點(diǎn)回到父節(jié)點(diǎn)n的指針。即擴(kuò)展節(jié)點(diǎn)A，其后繼節(jié)點(diǎn)有B和C，將它們放入OPEN表的末端，并提供回到父節(jié)點(diǎn)A的指針。（7）判斷剛產(chǎn)生的這些后繼節(jié)點(diǎn)中是否存在一個(gè)目標(biāo)節(jié)點(diǎn)，若存在，則找到一個(gè)解，成功退出。解可從目標(biāo)節(jié)點(diǎn)到起始節(jié)點(diǎn)的返回指針中得到。否則轉(zhuǎn)向（3）。后繼節(jié)點(diǎn)B和C都不是目標(biāo)節(jié)點(diǎn)，轉(zhuǎn)向（3）?！窘處煛坑肞PT展示“OPEN表和CLOSED表的狀態(tài)變化”圖片，進(jìn)行講解循環(huán)執(zhí)行上述操作，其OPEN表和CLOSED表的狀態(tài)變化如表所示?！緦W(xué)生】聆聽(tīng)、理解【教師】總結(jié)講解在搜索過(guò)程中，OPEN表中的節(jié)點(diǎn)排序準(zhǔn)則是后進(jìn)入的節(jié)點(diǎn)排在先進(jìn)入的節(jié)點(diǎn)后面。例如，表4-1的第3次循環(huán)中，節(jié)點(diǎn)F、G在節(jié)點(diǎn)D、E之后進(jìn)入OPEN表中，所以節(jié)點(diǎn)F、G排在節(jié)點(diǎn)D、E的后面。因此，OPEN表是一個(gè)隊(duì)列結(jié)構(gòu)，節(jié)點(diǎn)進(jìn)出OPEN表的順序是先進(jìn)先出。CLOSED表是一個(gè)順序表，表中各節(jié)點(diǎn)按順序標(biāo)號(hào)，正在考察的節(jié)點(diǎn)在表中編號(hào)最大。例如，表4-1的第7次循環(huán)后得到的CLOSED表中的節(jié)點(diǎn)按照從1至7的順序編號(hào)，其中正在考察的節(jié)點(diǎn)G的編號(hào)為7?！窘處煛坑肞PT展示“寬度優(yōu)先搜索樹”圖片，進(jìn)行講解在第7次循環(huán)中，步驟（7）判斷G產(chǎn)生的后繼節(jié)點(diǎn)K是目標(biāo)節(jié)點(diǎn)。此時(shí)，找到一個(gè)解，成功退出。便可得到貓捉老鼠的捕捉路線為。該搜索結(jié)束后得到的搜索樹如圖所示?！緦W(xué)生】聆聽(tīng)、理解【教師】提醒如果問(wèn)題有解，目標(biāo)節(jié)點(diǎn)必出現(xiàn)在OPEN表中，根據(jù)返回指針，在CLOSED表中回溯得到求解路徑。【教師】重點(diǎn)強(qiáng)調(diào)如下問(wèn)題寬度優(yōu)先搜索是一個(gè)通用的與問(wèn)題無(wú)關(guān)的方法，其性質(zhì)有：（1）當(dāng)問(wèn)題有解時(shí)，一定能找到解，且得到的是路徑最短的解。（2）當(dāng)目標(biāo)節(jié)點(diǎn)和起始節(jié)點(diǎn)較遠(yuǎn)時(shí)將會(huì)產(chǎn)生許多無(wú)用節(jié)點(diǎn)，搜索效率低?！緦W(xué)生】聆聽(tīng)、記錄、理解4.2.2深度優(yōu)先搜索【教師】講解深度優(yōu)先搜索【教師】安排學(xué)生掃描二維碼“深度優(yōu)先搜索”，了解深度優(yōu)先搜索基本思想【學(xué)生】掃碼觀看、了解度優(yōu)先搜索基本思想深度優(yōu)先搜索的基本思想是從起始節(jié)點(diǎn)開始，在其子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)進(jìn)行考察，如果不是目標(biāo)節(jié)點(diǎn)，則在該子節(jié)點(diǎn)的子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)進(jìn)行考察，一直如此向下搜索，如果發(fā)現(xiàn)不能到達(dá)目標(biāo)節(jié)點(diǎn)，則返回到上一個(gè)節(jié)點(diǎn)，然后選擇該節(jié)點(diǎn)的另一個(gè)子節(jié)點(diǎn)往下搜索，如此反復(fù)，直到搜索到目標(biāo)節(jié)點(diǎn)或搜索完全部節(jié)點(diǎn)為止?！窘處煛坑肞PT展示“深度優(yōu)先搜索”圖片，進(jìn)行舉例說(shuō)明例如，如圖所示的搜索樹，其搜索順序應(yīng)為。【學(xué)生】聆聽(tīng)、理解節(jié)點(diǎn)深度的定義如下。（1）起始節(jié)點(diǎn)（即根節(jié)點(diǎn)）的深度為0。例如，圖4-6中節(jié)點(diǎn)A的深度為0。（2）任何其他節(jié)點(diǎn)的深度等于其父節(jié)點(diǎn)深度加1。例如，圖4-6中節(jié)點(diǎn)D的深度是2，等于其父節(jié)點(diǎn)B的深度1加1。深度相等的節(jié)點(diǎn)可以任意排列。例如，圖4-6中節(jié)點(diǎn)B和C的排列也可以是先C后B。對(duì)于許多問(wèn)題，其狀態(tài)空間搜索樹的深度可能為無(wú)限深，或者可能至少要比某個(gè)可接受的解答序列的已知深度的上限還要深。為了防止搜索過(guò)程沿著無(wú)益的路徑擴(kuò)展下去，往往需要給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度，即深度界限。任何節(jié)點(diǎn)的深度如果達(dá)到了深度界限，那么都將它們作為沒(méi)有后繼節(jié)點(diǎn)處理?！窘處煛刻嵝眩杭词箲?yīng)用了深度界限的規(guī)定，所求得的解路徑也并不一定就是最短路徑?！窘處煛坑肞PT展示圖片“有界深度優(yōu)先搜索算法”，講解算法并提問(wèn)學(xué)生含有深度界限的深度優(yōu)先搜索的搜索過(guò)程可用如圖所示的算法描述。請(qǐng)用含有深度界限的深度優(yōu)先搜索算法解決貓捉老鼠問(wèn)題?！緦W(xué)生】觀看了解、舉手回答【教師】講授深度優(yōu)先搜索算法使用含有深度界限的深度優(yōu)先搜索算法解決貓捉老鼠問(wèn)題的步驟如下。（1）（3）判斷OPEN表是否為空表，若是空表，則沒(méi)有解，失敗退出；否則繼續(xù)。OPEN表中有節(jié)點(diǎn)A，非空，繼續(xù)執(zhí)行。（4）把OPEN表中的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）移出，并放入CLOSED表中。將節(jié)點(diǎn)A從OPEN表中移出，并放入CLOSED表中。（5）判斷節(jié)點(diǎn)n的深度是否等于深度界限，若等于，則轉(zhuǎn)向（3）；否則繼續(xù)。針對(duì)貓捉老鼠問(wèn)題，將深度界限設(shè)為3。第1次循環(huán)中節(jié)點(diǎn)A的深度為0，不等于深度界限。（6）判斷節(jié)點(diǎn)n是否有后繼節(jié)點(diǎn)，若有，則繼續(xù)；否則，轉(zhuǎn)向（3）。節(jié)點(diǎn)A有后繼節(jié)點(diǎn)，繼續(xù)執(zhí)行。（7）擴(kuò)展節(jié)點(diǎn)n，（8）判斷剛產(chǎn)生的這些后繼節(jié)點(diǎn)中是否存在一個(gè)目標(biāo)節(jié)點(diǎn)，若存在，則找到一個(gè)解，成功退出。解可從目標(biāo)節(jié)點(diǎn)到起始節(jié)點(diǎn)的返回指針中得到。否則轉(zhuǎn)向（3）。后繼節(jié)點(diǎn)B和C都不是目標(biāo)節(jié)點(diǎn)，轉(zhuǎn)向（3）?！窘處煛坑肞PT展示“OPEN表和CLOSED表的狀態(tài)變化”，講解搜索過(guò)程【學(xué)生】觀看了解循環(huán)執(zhí)行上述操作，第1次循環(huán)結(jié)束后，OPEN表的節(jié)點(diǎn)依次是B、C，然后進(jìn)行第2次循環(huán)，擴(kuò)展第一個(gè)節(jié)點(diǎn)B，其后繼節(jié)點(diǎn)有D和E，將它們放入OPEN表的前端，并提供回到父節(jié)點(diǎn)B的指針?？梢?jiàn)，經(jīng)過(guò)第2次循環(huán)后，OPEN表的節(jié)點(diǎn)依次為D、E、C。在整個(gè)搜索過(guò)程中，OPEN表和CLOSED表的狀態(tài)變化如表4-2所示?！窘處煛刻嵝眩荷疃冉缦逓?，故在第4次循環(huán)中，H可視為沒(méi)有后繼節(jié)點(diǎn)。在深度優(yōu)先搜索過(guò)程中，OPEN表中的節(jié)點(diǎn)排序準(zhǔn)則是后進(jìn)入的節(jié)點(diǎn)排在先進(jìn)入的節(jié)點(diǎn)前面。例如，表4-2的第2次循環(huán)中，節(jié)點(diǎn)D、E在節(jié)點(diǎn)C之后進(jìn)入OPEN表中，所以節(jié)點(diǎn)D、E排在節(jié)點(diǎn)C的前面。因此，OPEN表是一個(gè)棧結(jié)構(gòu)，節(jié)點(diǎn)進(jìn)出OPEN表的順序是后進(jìn)先出。CLOSED表的結(jié)構(gòu)和性質(zhì)與寬度優(yōu)先搜索中CLOSED表相同。【教師】用PPT展示“深度優(yōu)先搜索樹”圖片，進(jìn)行舉例說(shuō)明從表可以看出，貓捉老鼠的捕捉路線為。該搜索結(jié)束后得到的搜索樹如圖所示?！緦W(xué)生】聆聽(tīng)、理解【教師】提醒：在深度優(yōu)先搜索過(guò)程中，當(dāng)搜索到某一個(gè)節(jié)點(diǎn)，且后繼節(jié)點(diǎn)既不是目標(biāo)節(jié)點(diǎn)又不能繼續(xù)擴(kuò)展時(shí)，才考慮另一條替代的路徑。替代路徑是在前面已試過(guò)路徑的基礎(chǔ)上僅改變最后n步得到的，而且要求n盡可能小?！窘處煛恐攸c(diǎn)強(qiáng)調(diào)如下問(wèn)題深度優(yōu)先搜索策略也是一個(gè)通用的與問(wèn)題無(wú)關(guān)的方法，其性質(zhì)有：（1）一般不能保證找到路徑最短的解。（2）當(dāng)深度界限設(shè)置不合理時(shí)，可能找不到解。（3）在最壞情況下，搜索空間等同于窮舉?！緦W(xué)生】聆聽(tīng)、記錄、理解【教師】提醒：寬度優(yōu)先搜索策略和深度優(yōu)先搜索策略的唯一區(qū)別是在對(duì)節(jié)點(diǎn)n進(jìn)行擴(kuò)展時(shí)，其后繼節(jié)點(diǎn)在OPEN表中的存放位置不同。4.2.3等代價(jià)搜索【教師】講解等代價(jià)搜索【教師】安排學(xué)生掃描二維碼“等代價(jià)搜索”，了解等代價(jià)搜索【學(xué)生】掃碼觀看、了解在求解實(shí)際問(wèn)題的過(guò)程中，搜索所做的每一步操作的代價(jià)并不一定相同，因此，由寬度優(yōu)先搜索找到的最短路徑并不等同于最優(yōu)解。但是，通常人們希望找到具有某種特性的解，尤其是最小代價(jià)解。要解決尋找最小代價(jià)的路徑問(wèn)題，可采用寬度優(yōu)先搜索的推廣策略，即等代價(jià)搜索?！窘處煛刻嵝眩涸趯?duì)下層節(jié)點(diǎn)進(jìn)行擴(kuò)展（或搜索）之前，必須完成對(duì)當(dāng)前層所有節(jié)點(diǎn)的擴(kuò)展（或搜索）。搜索樹中的每條連接弧線上的有關(guān)代價(jià)可表示時(shí)間、距離和花費(fèi)等。如果所有的連接弧線具有相等的代價(jià)，那么等代價(jià)搜索就可簡(jiǎn)化為寬度優(yōu)先搜索。在等代價(jià)搜索算法中，把從節(jié)點(diǎn)n到其后繼節(jié)點(diǎn)m的連接弧線的代價(jià)記為，把從起始節(jié)點(diǎn)S0到任一節(jié)點(diǎn)n的路徑代價(jià)記為。在搜索樹上，假設(shè)是從起始節(jié)點(diǎn)S0到節(jié)點(diǎn)n的最小代價(jià)路徑上的代價(jià)，并且它是唯一的路徑?！窘處煛坑肞PT展示“等代價(jià)搜索算法”圖片，進(jìn)行講解人類經(jīng)過(guò)多年的觀察發(fā)現(xiàn)，每當(dāng)大雨即將來(lái)臨的時(shí)候，就會(huì)看到成群結(jié)隊(duì)的螞蟻在搬家，于是就把“螞蟻搬家”和“大雨將至”這兩個(gè)信息關(guān)聯(lián)在一起，得到了相應(yīng)的知識(shí)，即如果螞蟻搬家，則大雨將至。【學(xué)生】聆聽(tīng)、理解等代價(jià)搜索以的遞增順序擴(kuò)展其節(jié)點(diǎn)，其搜索過(guò)程可用如圖4-9所示的算法描述?！窘處煛坑肞PT展示“等貓和老鼠位置表示”圖片，進(jìn)行講解【學(xué)生】聆聽(tīng)、理解使用等代價(jià)搜索算法求貓捉老鼠所消耗的體力值，其步驟如下。（1）令（2）判斷OPEN表是否為空表，若是空表，則沒(méi)有解，失敗退出；否則繼續(xù)。OPEN表中有節(jié)點(diǎn)A，非空，繼續(xù)執(zhí)行。（3）循環(huán)，OPEN表中只有節(jié)點(diǎn)A，將節(jié)點(diǎn)A從OPEN表中移至CLOSED表中。（4）判斷節(jié)點(diǎn)n是否為一目標(biāo)節(jié)點(diǎn)，若是，則求得一個(gè)解且貓消耗的體力值為，（5）判斷節(jié)點(diǎn)是否有后繼節(jié)點(diǎn)，若有，則繼續(xù)；否則，轉(zhuǎn)向（2）。節(jié)點(diǎn)A有后繼節(jié)點(diǎn)，繼續(xù)執(zhí)行。（6）擴(kuò)展節(jié)點(diǎn)n，對(duì)其后繼節(jié)點(diǎn)m，計(jì)算，并把所有后繼節(jié)點(diǎn)m放入OPEN表，同時(shí)提供回到父節(jié)點(diǎn)n的指針，最后轉(zhuǎn)向（2）。將節(jié)點(diǎn)A的后繼節(jié)點(diǎn)B和C放入OPEN表中，且、。【教師】用PPT展示“OPEN表和CLOSED表的狀態(tài)變化”，進(jìn)行講解循環(huán)執(zhí)行上述操作，第1次循環(huán)結(jié)束后，OPEN表的節(jié)點(diǎn)依次是B、C，然后進(jìn)行第2次循環(huán)，擴(kuò)展路徑代價(jià)值最小的節(jié)點(diǎn)C，其后繼節(jié)點(diǎn)有F和G，將它們放入OPEN表中，并提供回到父節(jié)點(diǎn)C的指針。可見(jiàn)，經(jīng)過(guò)第2次循環(huán)后，OPEN表的節(jié)點(diǎn)依次為B、F、G。在整個(gè)搜索過(guò)程中，OPEN表和CLOSED表的狀態(tài)變化如表所示?！緦W(xué)生】聆聽(tīng)、理解如果有多個(gè)節(jié)點(diǎn)都使的值最小，那么就要選擇一個(gè)目標(biāo)節(jié)點(diǎn)作為節(jié)點(diǎn)n（若有目標(biāo)節(jié)點(diǎn)的話）；否則，就從這些節(jié)點(diǎn)中任選一個(gè)作為節(jié)點(diǎn)n。例如，在第5次循環(huán)結(jié)束，循環(huán)中，選節(jié)點(diǎn)K作為下一個(gè)要執(zhí)行的節(jié)點(diǎn)n?！窘處煛坑肞PT展示“等代價(jià)搜索樹”圖片，進(jìn)行講解從表4-3可以看出，在第6次循環(huán)中，步驟（4）判斷的節(jié)點(diǎn)n是目標(biāo)節(jié)點(diǎn)K。此時(shí)，找到一個(gè)解，成功退出。便可得到貓捉老鼠的捕捉路線為，貓消耗的體力值為。該搜索結(jié)束后得到的搜索樹如圖所示?！緦W(xué)生】聆聽(tīng)、理解4.2.4案例：寶匣上的拼圖【教師】展示“寶匣”圖片，提出問(wèn)題：某小說(shuō)中講述了一個(gè)曲折離奇的故事。在故事中，某人得到了藏有皇家寶藏秘密的寶匣，但是寶匣上面有一個(gè)9宮格拼圖密碼（見(jiàn)圖4-12），只有將圖片拼完整才可以打開寶匣。請(qǐng)采用盲目搜索策略完成拼圖任務(wù)?！緦W(xué)生】舉手回答老師提出的問(wèn)題【教師】總結(jié)，展示“拼圖的初始狀態(tài)”和“拼圖的目標(biāo)狀態(tài)”圖片，講解解法（1）用數(shù)字表示9宮格內(nèi)的圖片塊，則該拼圖的初始狀態(tài)如圖4-13所示，目標(biāo)狀態(tài)如圖所示。（2）移動(dòng)拼圖中空白的圖塊，可執(zhí)行的操作有上、下、左、右，其中，需要約束空白圖塊不能移出9宮格之外?！窘處煛刻嵝眩浩磮D中需要移動(dòng)的圖塊共有8個(gè)，若給每個(gè)圖塊都設(shè)置上、下、左、右操作，則需要32個(gè)操作算子，實(shí)現(xiàn)復(fù)雜。因此，可換一種思路，在拼圖過(guò)程中只有空白圖塊可以移動(dòng)，這樣就可以減少操作算子，實(shí)現(xiàn)簡(jiǎn)易。拼圖中需要移動(dòng)的圖塊共有8個(gè)，若給每個(gè)圖塊都設(shè)置上、下、左、右操作，則需要32個(gè)操作算子，實(shí)現(xiàn)復(fù)雜。因此，可換一種思路，在拼圖過(guò)程中只有空白圖塊可以移動(dòng)，這樣就可以減少操作算子，實(shí)現(xiàn)簡(jiǎn)易。【教師】展示“拼圖任務(wù)的寬度優(yōu)先搜索樹”圖片，進(jìn)行講解（3）使用寬度優(yōu)先搜索完成拼圖任務(wù)，其搜索順序如圖所示?！窘處煛刻岢鰡?wèn)題，請(qǐng)用深度優(yōu)先搜索完成拼圖任務(wù)，并畫出搜索樹?！緦W(xué)生】舉手回答老師提出的問(wèn)題【學(xué)生】聆聽(tīng)、記錄、理解通過(guò)老師講解，讓學(xué)生了解推理規(guī)則的一般形式課堂練習(xí)（7min）【教師】安排學(xué)生完成以下題目（1）下列不屬于按推理的邏輯基礎(chǔ)分類的是（）。A．演繹推理 B．單調(diào)推理C．歸納推理 D．默認(rèn)推理（2）推理是指從（）出發(fā)，按照某種策略運(yùn)用已掌握的知識(shí)，推導(dǎo)出其中（）或歸納出某些新的結(jié)論的過(guò)程。（3）推理方向用來(lái)確定推理的驅(qū)動(dòng)方式，包括（）和（）。（4）自然演繹推理是指從一組已知為真的事實(shí)出