【正文】 LOSED表，它們的結(jié)構(gòu)如下： ? Open 表 ? 狀態(tài)節(jié)點(diǎn) 父節(jié)點(diǎn) ? ┆ ? ? Closed表 ? 編號 狀態(tài)節(jié)點(diǎn) 父節(jié)點(diǎn) ? ┆ 狀態(tài)空間的一般搜索過程 ? 其中 open表存放剛生成的節(jié)點(diǎn)，對于不同的搜索策略，節(jié)點(diǎn)在 open表中的排列順序是不同的．例如對寬度優(yōu)先搜索是先生成的節(jié)點(diǎn)排在前面，而對深度優(yōu)先搜索則是后生成的節(jié)點(diǎn)排在前面． ? Closed表用于存放將要擴(kuò)展或者已經(jīng)擴(kuò)展的節(jié)點(diǎn)．搜索的一般過程如下： 狀態(tài)空間的一般搜索過程 ? (1)把初始節(jié)點(diǎn) S0放進(jìn) open表，并建立只包含 S0的圖，記為Ｇ． ? (2)檢查 open表是否為空，若為空則問題無解，退出． ? (3)把 open表的第一個(gè)節(jié)點(diǎn)取出放入 closed表，并記該節(jié)點(diǎn)為 n. ? (4)考察節(jié)點(diǎn) n是否為目標(biāo)節(jié)點(diǎn)，若是，則求得了問題的解，退出． ? (5)擴(kuò)展節(jié)點(diǎn) n，生成一組子節(jié)點(diǎn)．把其中不是 狀態(tài)空間的一般搜索過程 ? 節(jié)點(diǎn) n的先輩的那些子節(jié)點(diǎn)記作集合Ｍ，并把這些子節(jié)點(diǎn)作為節(jié)點(diǎn) n的子節(jié)點(diǎn)加入Ｇ中． ? (6)針對Ｍ中子節(jié)點(diǎn)的不同情況，分別進(jìn)行如下處理： ? Ａ )對那些未曾在Ｇ中出現(xiàn)過的Ｍ成員設(shè)置一個(gè)指向父節(jié)點(diǎn)（即節(jié)點(diǎn) n）的指針，并把它們放入 open表． ? Ｂ )對于那些先前已在Ｇ中出現(xiàn)的Ｍ成員，確定是否需要修改它指向父節(jié)點(diǎn)的指針． ? Ｃ )對于那些先前已在Ｇ中出現(xiàn)并且已經(jīng)擴(kuò)展 狀態(tài)空間的一般搜索過程 ? 了的Ｍ成員，確定是否是需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針． ? (7)按某種搜索策略對 open表中的節(jié)點(diǎn)進(jìn)行排序． ? (8)轉(zhuǎn)第２步 ? 說明：上面對狀態(tài)空間的搜索過程具有通用性，后面討論的各種搜索策略都可看作是它的一個(gè)特例．各種搜索策略的主要區(qū)別僅在于 open表中節(jié)點(diǎn)的排序準(zhǔn)則不同．例如在寬度優(yōu)先搜索中是先生成的節(jié)點(diǎn)排在前，在深度優(yōu)先搜索中是后生成的節(jié)點(diǎn)排在前等． 狀態(tài)空間的一般搜索過程 ? 一個(gè)節(jié)點(diǎn)經(jīng)一個(gè)算符操作后一般只生成一個(gè)子節(jié)點(diǎn)，但適用于一個(gè)節(jié)點(diǎn)的算符可能有多個(gè)，此時(shí)就會生成一組子節(jié)點(diǎn)．在這些子節(jié)點(diǎn)中可能有些是當(dāng)前擴(kuò)展節(jié)點(diǎn) (即節(jié)點(diǎn) n)的父節(jié)點(diǎn)，祖父節(jié)點(diǎn)等，此時(shí)不能把這些先輩節(jié)點(diǎn)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)的子節(jié)點(diǎn)．余下的子節(jié)點(diǎn)記作集合Ｍ，并加入圖Ｇ中． ? 一個(gè)新生成的節(jié)點(diǎn)，它可能是第一次被生成的節(jié)點(diǎn)，也可能是先前已作為其它節(jié)點(diǎn)的后繼節(jié)點(diǎn)被生成過，當(dāng)前又作為另一個(gè)節(jié)點(diǎn)的后繼節(jié) 狀態(tài)空間的一般搜索過程 ? 點(diǎn)被再次生成．此時(shí)，它應(yīng)該作為哪一個(gè)節(jié)點(diǎn)的后繼呢？一般由原始節(jié)點(diǎn)到該節(jié)點(diǎn)上所付出的代價(jià)來決定，哪條路徑付出的代價(jià)小，相應(yīng)的節(jié)點(diǎn)就作為它的父節(jié)點(diǎn)． ? ? 深度和廣度優(yōu)先搜索 ? 深度優(yōu)先搜索、廣度優(yōu)先搜索、有界深度優(yōu)先搜索及最好優(yōu)先搜索都與 backtrack方法類似，所不同的是，它們實(shí)現(xiàn)了另外一些搜索策略，為求解提供了更靈活的手段。 /*成功，返回路徑狀態(tài)的表 */ ? if CS沒有子狀態(tài)（不包括 DE， SL和 NSL中已有的狀態(tài)） ? then begin ? while((SL非空） and(CS = SL中第一個(gè)元素 )) 圖搜索的實(shí)現(xiàn)（續(xù)） ? do begin ? 將 CS加入 DE； /*標(biāo)明此狀態(tài)不可解 */ ? 從 SL中刪除第一個(gè)元素； /*回溯 */ ? 從 NSL中刪去第一個(gè)元素； ? CS： =NSL中第一個(gè)元素； ? end。 CS :=Start。 NSL:= [Start]。若 CS沒有子狀態(tài)，就要從 SL， NSL中刪除它，將其加入 DE， 然后回溯查找 NSL中的下一個(gè)狀態(tài)。博弈中走步用的推理規(guī)則或者其他合適的問題求解操作都可應(yīng)用于CS， 得到一些新狀態(tài)，即 CS的子狀態(tài)的有序集，重新視該集合中第一個(gè)狀態(tài)為當(dāng)前狀態(tài)，其余的按次序放入 NSL中，用于以后的搜索。 圖搜索的實(shí)現(xiàn)（續(xù)） ? 當(dāng)前正在搜索的結(jié)點(diǎn)叫 CS， 即當(dāng)前狀態(tài)。 ? 為了在最普遍的情況下（是圖而不是樹）定義回溯算法，有必 要檢測并刪除多次出現(xiàn)的某些狀態(tài)，以避免造成路徑循環(huán)。 DE不可解端點(diǎn)集 ,列出了找不到解題路徑的狀態(tài)。如果找到了目標(biāo)，SL就是解題路徑上狀態(tài)的有序集。 ? ? 1 A ? ? 2 B 8 C 10 D ? ? E 3 6 F 9 G ? ? H I J ? 4 5 7 ? 一個(gè)假設(shè)狀態(tài)空間的深度優(yōu)先回溯搜索 圖搜索的實(shí)現(xiàn) （ 續(xù) ） ? 下面定義一個(gè)回溯搜索的算法：算法使用 3張表保存狀態(tài)空間中的結(jié)點(diǎn)。 圖搜索的實(shí)現(xiàn)（續(xù)） ? 算法就是以這種方式執(zhí)行直到找到目標(biāo)或遍歷了狀態(tài)空間為止。如果在以 Schild1為根的子圖中沒有找到目標(biāo)，就對它的兄弟Schild2調(diào)用此過程。若找到目標(biāo)，就退出搜索，返回解題路徑，若遇到不可解結(jié)點(diǎn)，就回溯到路徑中最近的父結(jié)點(diǎn)上，查看是否有當(dāng)前結(jié)點(diǎn)的兄弟結(jié)點(diǎn)未擴(kuò)展，并沿這些分支繼續(xù)搜索?；厮菔且环N經(jīng)常使用的技術(shù)。若在選擇解題路徑時(shí)能給出絕對可靠的預(yù)言或絕對正確的機(jī)制，那就不需要搜索了，求解時(shí)會一次成功地穿過空間到達(dá)目標(biāo)，構(gòu)造出一條求解路徑來。 圖搜索的實(shí)現(xiàn) ? 無論是目標(biāo)還是數(shù)據(jù)驅(qū)動(dòng)的搜索，其求解問題都是要在狀態(tài)空間圖中找到從初態(tài)到目標(biāo)狀態(tài)的路徑。這種方法稱為目標(biāo)驅(qū)動(dòng)的推理或反向推理。搜索就通過反向的、連續(xù)的子目標(biāo)不斷地進(jìn)行，一直到找到問題給定的條件為止。 ? 另一種求解方法是：先從欲想達(dá)到的目標(biāo)開始，看哪些規(guī)則或合法移動(dòng)能產(chǎn)生該目標(biāo)以及應(yīng)用這些規(guī)則產(chǎn)生目標(biāo)時(shí)需要哪些條件。搜索的過程是應(yīng)用規(guī)則從給定的條件產(chǎn)生新的條件，再用規(guī)則從新的條件產(chǎn)生更多的新條件。 狀態(tài)空間搜索 狀態(tài)空間搜索策略 數(shù)據(jù)驅(qū)動(dòng)和目標(biāo)驅(qū)動(dòng)的搜索 圖搜索的實(shí)現(xiàn) 深度和廣度優(yōu)先搜索 有界深度優(yōu)先搜索 謂詞演算推理的狀態(tài)空間表示法 邏輯的狀態(tài)空間描述 與 /或圖 討論 ? 基于遞歸的搜索 ? 遞歸 ? 遞歸搜索 ? 模式驅(qū)動(dòng)搜索 ? 產(chǎn)生式系統(tǒng) ? 定義與歷史 ? 產(chǎn)生式系統(tǒng)示例 ? 產(chǎn)生式系統(tǒng)搜索的控制 ? 產(chǎn)生式系統(tǒng)的優(yōu)點(diǎn) ? 狀態(tài)空間搜索策略 ? 數(shù)據(jù)驅(qū)動(dòng)和目標(biāo)驅(qū)動(dòng)的搜索 ? 狀態(tài)空間可以從兩個(gè)方向進(jìn)行搜索：從實(shí)際問題的給定數(shù)據(jù)向目標(biāo)搜索或者從目標(biāo)到數(shù)據(jù)進(jìn)行搜索。 ? 數(shù)據(jù)驅(qū)動(dòng)搜索，也稱為正向推理。這個(gè)過程持續(xù)到有一條滿足目標(biāo)要求的路徑產(chǎn)生為止。這些條件就成為我們要達(dá)到的新目標(biāo)，即子目標(biāo)。這樣就找到了一條從數(shù)據(jù)到目標(biāo)的移動(dòng)或規(guī)則組成的鏈，盡管搜索方向和它正好相反。 ? 在實(shí)際的搜索系統(tǒng)中可能兩種方法同時(shí)使用，即一方面從數(shù)據(jù)驅(qū)動(dòng)向目標(biāo)進(jìn)行，可能搜索到某一個(gè)子目標(biāo)；另一方面又從目標(biāo)向數(shù)據(jù)方面進(jìn)行搜索，剛好也搜索到該子目標(biāo)，這時(shí)推理也結(jié)束，即假設(shè)的目標(biāo)正確。而路徑上弧的序列就對應(yīng)解題的先后步驟。但實(shí)際問題中沒有絕對可靠的預(yù)言，求解時(shí)必須嘗試多條路徑直到找到目標(biāo)為止。 圖搜索的實(shí)現(xiàn)（續(xù)） ? 帶回溯的搜索從初始狀態(tài)出發(fā)，不停地尋找路徑一直到它到達(dá)目標(biāo)或“不可解端點(diǎn)”。算法在每個(gè)結(jié)點(diǎn)上的檢查過程遵循下面的遞歸方式： 圖搜索的實(shí)現(xiàn)（續(xù)） ? 若當(dāng)前狀態(tài) S未到達(dá)目標(biāo)的要求，就對它的第一子狀態(tài) Schild1遞歸調(diào)用回溯過程。此過程重復(fù)進(jìn)行到某個(gè)結(jié)點(diǎn)的后裔是目標(biāo)或者所有子結(jié)點(diǎn)都搜索完為止。下圖給出的是一個(gè)假設(shè)的狀態(tài)空間的深度優(yōu)先回溯搜索。 ? SL狀態(tài)表列出了當(dāng)前路徑上的狀態(tài)。 ? NSL新狀態(tài)表，包含了等待評估的結(jié)點(diǎn)，其后裔結(jié)點(diǎn)還未被擴(kuò)展。如果在搜索中再遇到它們，就會檢測到它們是DE中的成分而立即將其排除。檢測可以通過對每一個(gè)新生成的狀態(tài)判斷它是否在上述 3張表中來實(shí)現(xiàn)，如果它屬于某一張表，就說明它已被搜索過不必再考慮。 CS總是等于最近加入 SL中的狀態(tài)，是當(dāng)前正在探尋的解題路徑的“前鋒”。新的CS加入 SL中，搜索就這樣繼續(xù)進(jìn)行。 圖搜索的實(shí)現(xiàn)（續(xù)） ? Function backtrack (回溯算法） ? begin ? SL:=[Start]。 DE := [ ]。 /*初始化 */ ? while NSL? [ ] /*還有未檢查的狀態(tài) */ ? do begin ? if CS = 目標(biāo)（或符合目標(biāo)的要求） ? then return (SL)。 ? 將 CS加入 SL； ? end ? else begin ? 將 CS子狀態(tài)（不包括 DE、 SL、 NSL中有的）加入 NSL； 圖搜索的實(shí)現(xiàn)（續(xù)） ? CS： =NSL中第一個(gè)元素； ? 將 CS加入 SL； ? end ? end。 ? 廣度優(yōu)先搜索采取的是先橫后縱的搜索策略，而深度優(yōu)先搜索采取的是先縱后橫的搜索策略。 OPEN表中放的是未擴(kuò)展的結(jié)點(diǎn)， CLOSED表中放的是已擴(kuò)展的結(jié)點(diǎn)。其思想是定一個(gè)界 d， 這個(gè)界 d可以是深度 ， 也可以是一個(gè)代價(jià)。 寬度優(yōu)先搜索 ? 寬度優(yōu)先搜索的過程如下： ? １、把初始節(jié)點(diǎn)放入 open表 ? ２、如果 open表為空，則問題無解，退出． ? ３、把 open表的第一個(gè)節(jié)點(diǎn) (記為 n)取出放入closed表． ? ４、考察節(jié)點(diǎn) n是否為目標(biāo)節(jié)點(diǎn)，若是則求得了問題的解，退出。 ? ５、若節(jié)點(diǎn) n不可擴(kuò)展，則轉(zhuǎn)第２步． ? ６、擴(kuò)展節(jié)點(diǎn) n將其子節(jié)點(diǎn)放入 open表的首部 深度優(yōu)先搜索 ? 深度優(yōu)先搜索和寬度優(yōu)先搜索的區(qū)別僅在于：寬度優(yōu)先搜索是把節(jié)點(diǎn) n的子節(jié)點(diǎn)放入到 open表的尾部，而深度優(yōu)先搜索則是將節(jié)點(diǎn) n的子節(jié)點(diǎn)放入 open表的首部．深度優(yōu)先搜索重排九宮的例子見 p268頁的圖６－１６． 有界深度優(yōu)先搜索 ? 為了解決深度優(yōu)先搜索不完備的問題，避免搜索過程陷入無窮分支的死循環(huán)，提出了有界深度優(yōu)先搜索方法．其過程如下： ? １、把初始節(jié)點(diǎn)放入 open表，置 S0深度d(S0)=0 ? ２、如果 open表為空，則問題無解，退出． ? ３、把 open表的第一個(gè)節(jié)點(diǎn) (記為 n)取出放入closed表． 有界深度優(yōu)先搜索 ? ４、考察節(jié)點(diǎn) n是否為目標(biāo)節(jié)點(diǎn)，若是則求得了問題的解，退出。 ? 若節(jié)點(diǎn) n不可擴(kuò)展，轉(zhuǎn)２ 代價(jià)樹的寬度優(yōu)先搜索 ? 擴(kuò)展節(jié)點(diǎn) n將其子節(jié)點(diǎn)放入 open表中，并為其配置指向父節(jié)點(diǎn)的指針，計(jì)算各子節(jié)點(diǎn)的代價(jià)，并按代價(jià)對 open表中的全部節(jié)點(diǎn)按從小到大的順序排序，轉(zhuǎn)２． ? 搜索過程見 p270頁的圖６－１９ ? 書上例６ .7給出了求５城市間交通圖，現(xiàn)要求從城市Ａ到城市Ｅ的最小費(fèi)用交通路線．求解該問題時(shí)首先要把圖轉(zhuǎn)換成代價(jià)樹． 代價(jià)樹的寬度優(yōu)先搜索 ? A 4 B ? 4 4 ? C 2 D 5 ? 3 E ? 交通圖 代價(jià)樹的寬度優(yōu)先搜索 ? 轉(zhuǎn)化成代價(jià)樹 ? A ? 3 4 ? C1 B1 ? 2