【文章內(nèi)容簡介】 2 3 4 5 8 7 6 15 1 2 8 5 3 7 4 6 17 1 3 5 8 2 7 4 6 18 8 1 3 2 5 7 4 6 19 1 2 3 7 8 5 4 6 20 2 3 1 8 5 7 4 6 21 1 2 8 4 3 7 6 5 22 1 2 3 8 5 7 4 6 5 1 2 3 8 4 7 6 5 23 八數(shù)碼廣度優(yōu)先搜索 1 2 8 5 3 7 4 6 9 16 1 2 3 8 5 6 7 4 2023/4/2 人工智能 43 廣度優(yōu)先搜索 廣度優(yōu)先搜索的特點(diǎn)： ?廣度優(yōu)先中 OPEN表 是一個(gè) 隊(duì)列 ， CLOSED表 是一個(gè) 順序表 ，表中各節(jié)點(diǎn)按順序編號(hào)，正被考察的節(jié)點(diǎn)在表中編號(hào)最大。 ?廣度優(yōu)先搜索又稱為 寬度優(yōu)先 或 橫向搜索 。 ?廣度優(yōu)先策略是 完備 的，即如果問題的解存在，則它一定可以找到解，并且找到的解還是最優(yōu)解。 ?廣度優(yōu)先搜索策略與問題無關(guān)，具有通用性。 ?缺點(diǎn)搜索 效率低 。 2023/4/2 人工智能 44 深度優(yōu)先搜索 (1) ?深度優(yōu)先搜索的基本思想： 深度優(yōu)先搜索是一種一直向下的搜索過程，它優(yōu)先在自己的子節(jié)點(diǎn)集合中選擇下一個(gè)被考察的節(jié)點(diǎn)，不斷向縱深方向前進(jìn)，直到到達(dá)葉子節(jié)點(diǎn)或受到深度限制時(shí)，才返回到上一級(jí)節(jié)點(diǎn)沿另一方向繼續(xù)前進(jìn)。 ?深度優(yōu)先搜索算法： 與廣度優(yōu)先搜索策略的唯一不同點(diǎn)就是 OPEN表 被設(shè)計(jì)成 后進(jìn)先出的棧 ，新生成的子節(jié)點(diǎn)放在 OPEN表的前面，后生成的節(jié)點(diǎn)優(yōu)先被考察。深度優(yōu)先搜索算法只需 將寬度優(yōu)先搜索算法步 6修改為 ： 步 6 否則，擴(kuò)展 N，將其所有子節(jié)點(diǎn)配上指向 N的指針放入 OPEN表的 首部 ，轉(zhuǎn)步 2。 例 1 2 3 8 5 7 4 6 1 1 2 3 8 4 5 7 6 3 1 2 3 8 4 5 7 6 1 2 3 8 4 5 7 6 1 2 3 8 5 7 4 6 1 2 3 8 4 5 7 6 1 2 3 8 4 7 6 5 4 1 2 8 4 3 7 6 5 1 2 3 8 5 7 4 6 2 1 2 3 8 4 7 6 5 5 2023/4/2 人工智能 46 深度優(yōu)先搜索 深度優(yōu)先搜索的特點(diǎn) ： ?OPEN表為一個(gè) 堆棧 。 ?深度優(yōu)先又稱 縱向搜索 。 ?一般 不能保證找到最優(yōu)解 。如下圖所示： S0S g 1圖 213 深度優(yōu)先搜索不具有完備性示意圖 2023/4/2 人工智能 47 （ Acd ） 為克服深度優(yōu)先搜索的不足，可以對其深度進(jìn)行限制 ?深度界限的選擇很重要 dm 若太小，則達(dá)不到解的深度，得不到解；若太大，既浪費(fèi)了計(jì)算機(jī)的存儲(chǔ)空間與時(shí)間，又降低了搜索效率。由于解的路徑長度事先難以預(yù)料，所以要恰當(dāng)?shù)亟o出 dm的值是比較困難的。 ?即使能求出解，它也不一定是最優(yōu)解。 (1) 當(dāng)在 dm界限之內(nèi)找不到解時(shí)，可以將深度界限 dm不斷擴(kuò)大，每次增加一個(gè)深度增量 ?d，直到找到解，或者搜索完整棵樹。這樣算法的完備性得到了保證，稱為可變界深度優(yōu)先搜索算法 (或迭代加深搜索 )。 當(dāng) ⊿ d =1時(shí)，算法開始蛻變?yōu)?廣度優(yōu)先搜索 算法。 (2) ? 迭代加深搜索過程： 步 1 把初始節(jié)點(diǎn) S0放入 OPEN表中，置 S0的深度 d（ S0 ）＝ 0， dm為任意初值。 步 2 若 OPEN表為空， 則考查 CLOSED表是否有待擴(kuò)展節(jié)點(diǎn)： ①若無，則問題無解，退出。 ② 若有，則取出 CLOSED表中待擴(kuò)展節(jié)點(diǎn)放入到 OPEN表中，令 dm=dm+⊿ d。 (3) 步 3 取 OPEN表中第一個(gè)節(jié)點(diǎn) N放在 CLOSED表中；并冠以編號(hào) n； 步 4 若節(jié)點(diǎn) N為目標(biāo)節(jié)點(diǎn)，成功退出。 步 5 若 N的深度 d（ N） ＞ dm（深度限制值）， 則標(biāo) N為待擴(kuò)展節(jié)點(diǎn)， 則轉(zhuǎn)步 2； 步 6 N無子節(jié)點(diǎn)，則轉(zhuǎn)步 2； 步 7 擴(kuò)展 N，將其所有子節(jié)點(diǎn) Ni配上指向 N的指針放入OPEN首部 ， 置 d（ Ni ）＝ d（ N）＋ 1，轉(zhuǎn)步 2。 (1) 問題： 當(dāng) ⊿ d 1 時(shí)， 是否能保證找到最優(yōu)解？ S0Sg 2dm 1 = dm + △ ddm△ d = 3Sg 1d ( Sg 1)dm 2= d ( Sg 1) 12023/4/2 人工智能 53 (2) 步 1 把初始節(jié)點(diǎn) S0放入 OPEN表中，置 d(S0)=0， dm=dm0， G=NULL。 步 2 若 OPEN表為空，則考察 CLOSED表是否有待擴(kuò)展節(jié)點(diǎn)： （ 1）若無待擴(kuò)展節(jié)點(diǎn)，則判斷 G表是否為空： 若為空，搜索失敗，退出； 否則，取出 G表最后面的節(jié)點(diǎn) Sg， Sg即為所求最優(yōu)解，搜索成功，退出； （ 2）若有待擴(kuò)展節(jié)點(diǎn)，則取出 CLOSED表中待擴(kuò)展節(jié)點(diǎn)放入到OPEN表中，令 dm=dm+⊿ d，轉(zhuǎn)步 2； (3) 步 3 取 OPEN表中首部的節(jié)點(diǎn) N放在 CLOSED表中；并冠以順序編號(hào) n； 步 4 若 d（ N） ＞ dm，則標(biāo) N為待擴(kuò)展節(jié)點(diǎn)，轉(zhuǎn)步 2； 步 5 若 N是目標(biāo)節(jié)點(diǎn) Sg ，則令 dm＝ d（ Sg ） 1 ，把 Sg放到 G 表的尾部，轉(zhuǎn)步 2。 步 6 若 N不可擴(kuò)展，則轉(zhuǎn)步 2； 步 7 否則，擴(kuò)展 N，將其所有子節(jié)點(diǎn) Ni配上指向 N的返回指針放入OPEN表首部， 置 d（ Ni ）＝ d（ N）＋ 1 ，轉(zhuǎn)步 2。 2023/4/2 人工智能 54 狀態(tài)空間圖的啟發(fā)式搜索 (1) ?啟發(fā)性知識(shí) 就是與被求解問題自身特性相關(guān)的知識(shí)，包括被求解問題的解的特性、解的分布規(guī)律和在實(shí)際當(dāng)中求解此類問題的經(jīng)驗(yàn)、技巧等，對應(yīng)于問題求解框架中的 控制性知識(shí) 。 ?啟發(fā)函數(shù) 要實(shí)現(xiàn)啟發(fā)式搜索，需要把啟發(fā)性知識(shí)形式化，即用一定的函數(shù)表示出來，通過函數(shù)計(jì)算來評(píng)價(jià)每種選擇的價(jià)值大小，用以 指導(dǎo)搜索過程 ，這樣的函數(shù)稱為啟發(fā)函數(shù)。 2023/4/2 人工智能 55 2023/4/2 人工智能 56 狀態(tài)空間圖的啟發(fā)式搜索 (2) 在實(shí)際設(shè)計(jì)過程中， 啟發(fā)函數(shù)是用來估計(jì)搜索樹節(jié)點(diǎn)x與目標(biāo)節(jié)點(diǎn)接近程度的一種函數(shù)，通常記為 h（ x） 。 啟發(fā)函數(shù)可以是： （ 1）一個(gè)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的某種距離或差異的量度； （ 2）一個(gè)節(jié)點(diǎn)處在最佳路徑上的概率； （ 3）根據(jù)主觀經(jīng)驗(yàn)的主觀打分等。 2023/4/2 人工智能 57 狀態(tài)空間圖的啟發(fā)式搜索 (3) 啟發(fā)式搜索算法 啟發(fā)式搜索的 A算法和 A*算法 A*算法在游戲中的應(yīng)用 2023/4/2 人工智能 58 啟發(fā)式搜索算法 （ 1） ?啟發(fā)式搜索 用啟發(fā)函數(shù)來導(dǎo)航，其搜索算法就要在狀態(tài)圖一般搜索算法基礎(chǔ)上再 增加啟發(fā)函數(shù)值 的 計(jì)算 與 傳播 過程，并且由 啟發(fā)函數(shù)值 來 確定 節(jié)點(diǎn)的 擴(kuò)展順序 。 ?按選擇范圍不同，啟發(fā)式搜索分為 ： ?全局擇優(yōu)搜索 ?局部擇優(yōu)搜索 2023/4/2 人工智能 59 啟發(fā)式搜索算法 （ 2） 基本思想： 在 OPEN表中 保留所有已生成而未考察 的節(jié)點(diǎn)， 并用啟發(fā)函數(shù) h(x)對它們 全部 進(jìn)行估價(jià) ， 從中選出最優(yōu)節(jié)點(diǎn)進(jìn)行擴(kuò)展 ， 而不管這個(gè)節(jié)點(diǎn)出現(xiàn)在搜索樹的什么地方 。 啟發(fā)式搜索算法 （ 3） 全局擇優(yōu)搜索算法： 步 1 把初始節(jié)點(diǎn) S0放入 OPEN表中，計(jì)算 h(S0)； 步 2 若 OPEN表為空，則搜索失敗，退出； 步 3 否則，移出 OPEN表中第一個(gè)節(jié)點(diǎn) N放入 CLOSED表中，并冠以序號(hào) n ； 步 4 若目標(biāo)節(jié)點(diǎn) Sg ＝ N，則搜索成功，利用 CLOSED表中的返回指針找出 S0到 N的路徑即為所求解，退出； 步 5 若 N不可擴(kuò)展，則轉(zhuǎn)步 2 ； 步 6 否則，擴(kuò)展 N，計(jì)算 N的每個(gè)子節(jié)點(diǎn) x的函數(shù)值，并將N所有子節(jié)點(diǎn) x配以指向 N的返回指針后放入 OPEN表中，依據(jù)啟發(fā)函數(shù)對節(jié)點(diǎn)的計(jì)算，再對 OPEN表中 所有節(jié)點(diǎn) 按其啟發(fā)函數(shù)值的大小以升序排列，轉(zhuǎn)步 2。 2023/4/2 人工智能 60 啟發(fā)式搜索算法 （ 4） 基本思想： 局部擇優(yōu)搜索是在啟發(fā)性知識(shí)導(dǎo)航下的深度優(yōu)先搜索，在 OPEN表中保留所有已生成而未考察的節(jié)點(diǎn)，對其中 新生成的每個(gè)子節(jié)點(diǎn) x計(jì)算啟發(fā)函數(shù) ，從 全部子節(jié)點(diǎn) 中選出 最優(yōu)節(jié)點(diǎn) 進(jìn)行擴(kuò)展，其選擇下一個(gè)要考察節(jié)點(diǎn)的范圍是剛剛生成的全部子節(jié)點(diǎn)， 局部擇優(yōu)搜索算法： 與全局擇優(yōu)搜索算法的區(qū)別僅在 步 6： 步 6 否則，擴(kuò)展 N，計(jì)算 N的每個(gè)子節(jié)點(diǎn) x的函數(shù)值，并將 N的所有子節(jié)點(diǎn) x配以指向節(jié)點(diǎn) N的指針后，將 全部子節(jié)點(diǎn) 按啟發(fā)函數(shù)值升序排列后放入 OPEN表的首部，轉(zhuǎn)步 2。 2023/4/2 人工智能 61 啟發(fā)式搜索的 A算法和 A*算法（ 1） 啟發(fā)函數(shù)是對當(dāng)前節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)未來可能要付出的代價(jià)的估計(jì)。 在全局擇優(yōu)和局部擇優(yōu)搜索算法中，都沒有考慮從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)已經(jīng)付出的實(shí)際代價(jià)。 在很多實(shí)際問題中，已經(jīng)付出的實(shí)際代價(jià)是必須考慮的，如 TSP問題等。將兩者同時(shí)考慮，用于指導(dǎo)搜索的算法稱為 A算法和 A*算法 。 2023/4/2 人工智能 63 啟發(fā)式搜索的 A算法和 A*算法（ 2） 1. A算法 估價(jià)函數(shù) f（ x） :為了防止在單獨(dú)利用啟發(fā)函數(shù)的時(shí)候誤入歧途，將啟發(fā)函數(shù) h（ x）與代價(jià)函數(shù) g（ x）相結(jié)合，即初始節(jié)點(diǎn) S0到達(dá)節(jié)點(diǎn) x處已付出的 代價(jià)與 節(jié)點(diǎn) x 到達(dá)目標(biāo)節(jié)點(diǎn) Sg的 接近程度估計(jì)值總和 。 f（ x） ＝ g（ x）＋ h（ x） ? g（ x）代價(jià)函數(shù) ： 初始節(jié)點(diǎn) S0到達(dá)節(jié)點(diǎn) x處已付出的 代價(jià)， 有利于搜索縱向發(fā)展，提高搜索效率，但影響完備性。 ? h（ x）啟發(fā)函數(shù) ：節(jié)點(diǎn) x 到達(dá)目標(biāo)節(jié)點(diǎn) Sg的 接近程度估計(jì)值 有利于搜索橫向發(fā)展，提高搜索的完備性，但影響搜索效率。 啟發(fā)式搜索的 A算法和 A*算法（ 3） 代價(jià) g（ x） 的計(jì)算 g（ x） 表示從初始節(jié)點(diǎn) S0到節(jié)點(diǎn) x的代價(jià)： g（ S0 ）＝ 0 g（ xj ）＝ g（ xi ）＋ c（ xi， xj） 其中， c（ xi， xj） 表示父節(jié)點(diǎn) xi到子節(jié)點(diǎn) xj的代價(jià) A D C E B 4 6 4 3 3 2 3 2 3 4 6 2 3 4 4 6 3 2 C1 B1 D1 D2 E1 C2 E2 D3 C3 B2 E4 E3 6 B3 2023/4/2 人工智能 64 啟發(fā)式搜索的 A算法和 A*算法（ 4） 對估價(jià)函數(shù) f（ x） ＝ g（ x）＋ h（ x） 令其中的 h（ x） =0時(shí)，這時(shí)得到的是 代價(jià)樹 的 非啟發(fā)式搜索算法。 按對節(jié)點(diǎn)的考察范圍不同，可分為兩種搜索策略： ? 分支界限法 將全局擇優(yōu)搜索算法中的 h（ x） 替換為 g（ x） ，即可得到分支界限搜索算法。 ? 瞎子爬山法 將局部擇優(yōu)搜索算法中的 h（ x） 替換為 g（ x） ，即可得到瞎子爬山搜索算法。 2023/4/2 人工智能 65 2023/4/2 人工智能 66 啟發(fā)式搜索的 A算法和 A*算法（ 5） 步 1 把附有 f（ S0 ） 的初始節(jié)點(diǎn) S0放入 OPEN表中； 步 2 若 OPEN表為空，則搜索失敗，退出； 步 3 否則，移出 OPEN表中第一個(gè)節(jié)點(diǎn)