人工智能實(shí)驗(yàn)盲目搜索

一、 無(wú)信息搜索（盲目搜索）

1.算法原理
1.1 搜索問(wèn)題的形式化定義
解決搜索問(wèn)題時(shí)，首先需要對(duì)搜索問(wèn)題進(jìn)行形式化表述。搜索問(wèn)題從以下幾個(gè)方面表述：

狀態(tài)空間：對(duì)問(wèn)題的形式化，表示需要進(jìn)行搜索的空間
動(dòng)作：對(duì)真正動(dòng)作的形式化，表示從一個(gè)狀態(tài)到達(dá)另一個(gè)狀態(tài)
初始狀態(tài)：表示當(dāng)前的狀態(tài)
目標(biāo)：表示需要達(dá)到的目標(biāo)的狀態(tài)
啟發(fā)方法：用于指揮搜索的前進(jìn)方向的方法
問(wèn)題的解：一個(gè)從初始狀態(tài)到達(dá)目標(biāo)狀態(tài)的動(dòng)作序列
搜索問(wèn)題可以用狀態(tài)空間樹表示，每個(gè)節(jié)點(diǎn)對(duì)應(yīng)著狀態(tài)空間中的一種狀態(tài)。節(jié)點(diǎn)的父節(jié)點(diǎn)表示產(chǎn)生該狀態(tài)的上一個(gè)狀態(tài)，父節(jié)點(diǎn)生成子節(jié)點(diǎn)時(shí)需要記錄生成節(jié)點(diǎn)所采取的行動(dòng)與代價(jià)。

搜索算法的性能需要考慮一個(gè)方面：

完備性：當(dāng)問(wèn)題有解時(shí)是否一定能找到解
最優(yōu)性：搜索策略是否一定能找到最優(yōu)解
時(shí)間復(fù)雜度：找到解所需要的時(shí)間，又稱為搜索代價(jià)
空間復(fù)雜度：執(zhí)行搜索過(guò)程中需要多少內(nèi)存空間
1.2 無(wú)信息搜索的具體算法
1.2.1 寬度優(yōu)先搜索
寬度優(yōu)先搜索用一個(gè)先進(jìn)先出的隊(duì)列實(shí)現(xiàn)，節(jié)點(diǎn)的拓展順序與目標(biāo)節(jié)點(diǎn)的位置無(wú)關(guān)。從狀態(tài)空間樹上看，寬度優(yōu)先搜索的拓展順序是按樹的層次順序來(lái)進(jìn)行的。這樣一來(lái)，短的路徑會(huì)在任何比它長(zhǎng)的路徑之前被遍歷，因此寬度優(yōu)先搜索具有完備性和最優(yōu)性。

定義b bb為問(wèn)題中一個(gè)狀態(tài)最大的后繼狀態(tài)個(gè)數(shù)，d dd為最短解的動(dòng)作個(gè)數(shù)，則有：

時(shí)間復(fù)雜度：1 + b + b 2 + . . . + b d + b ( b d ? 1 ) = O ( b d + 1 ) 1+b+b^2+...+b^d+b(b^d-1)=O(b^{d+1})1+b+b2+...+bd+b(bd?1)=O(bd+1)
空間復(fù)雜度：b ( b d ? 1 ) = O ( b d + 1 ) b(b^d-1)=O(b^{d+1})b(bd?1)=O(bd+1)
1.2.2 深度優(yōu)先搜索
把當(dāng)前要擴(kuò)展的狀態(tài)的后繼狀態(tài)放在邊界的最前面，邊界上總是擴(kuò)展最深的那個(gè)節(jié)點(diǎn)。在狀態(tài)空間無(wú)限或在狀態(tài)空間有限，但是存在無(wú)限的路徑（例如存在回路） 的情況下不具有完備性。在狀態(tài)空間有限，且對(duì)重復(fù)路徑進(jìn)行剪枝的情況下才有。不具有最優(yōu)性。

定義m是遍歷過(guò)程中最長(zhǎng)路徑的長(zhǎng)度，則有：

時(shí)間復(fù)雜度：O ( b m ) O(b^m)O(bm)

空間復(fù)雜度：O ( b m ) O(bm)O(bm)

1.2.3 一致代價(jià)搜索
邊界中，按路徑的成本升序排列，總是擴(kuò)展成本最低的那條路徑。當(dāng)每種動(dòng)作的成本是一樣的時(shí)候，和寬度優(yōu)先是一樣的。假設(shè)每個(gè)動(dòng)作的成本都大于某個(gè)大于0的常量，所有成本較低的路徑都會(huì)在成本高的路徑之前被擴(kuò)展。給定成本，該成本的路徑數(shù)量是有限的；成本小于最優(yōu)路徑的路徑數(shù)量是有限的，最終，我們可以找到最短的路徑，因此具備完備性和最優(yōu)性。

對(duì)于一致代價(jià)搜索，當(dāng)最優(yōu)解的成本為C* ，上述最低代價(jià)為?s ss，則有：

時(shí)間復(fù)雜度：O ( b [ C ? / s ] + 1 ) O(b^{[C^*/s]+1})O(b[C?/s]+1)
空間復(fù)雜度：O ( b [ C ? / s ] + 1 ) O(b^{[C^*/s]+1})O(b[C?/s]+1)
1.2.4 深度受限搜索
深度受限搜索是深度優(yōu)先搜索，但是預(yù)先限制了搜索的深度L，因此無(wú)限長(zhǎng)度的路徑不會(huì)導(dǎo)致深度優(yōu)先搜索無(wú)法停止的問(wèn)題。 但只有當(dāng)解路徑的長(zhǎng)度 ≤ L 時(shí)，才能找到解，故不具有完備性和最優(yōu)性。

時(shí)間復(fù)雜度：O ( b L ) O(b^L)O(bL)
空間復(fù)雜度：O ( b L ) O(bL)O(bL)
1.2.5 迭代加深搜索
一開始設(shè)置深度限制為L(zhǎng) = 0，迭代地增加深度限制，對(duì)于每個(gè)深度限制都進(jìn)行深度受限搜索 。如果找到解，或者深度受限搜索沒(méi)有節(jié)點(diǎn)可以擴(kuò)展的時(shí)候可以停止當(dāng)前迭代，并提高深度限制L 。如果沒(méi)有節(jié)點(diǎn)可以被剪掉（深度限制不能再提高）仍然 沒(méi)有找到解，那么說(shuō)明已經(jīng)搜索所有路徑，因此這個(gè)搜索不存在解。具有完備性，且在每個(gè)動(dòng)作的成本一致時(shí)具有最優(yōu)性。

1.2.6 雙向搜索
同時(shí)進(jìn)行從初始狀態(tài)向前的搜索和從目標(biāo)節(jié)點(diǎn)向后搜索，在兩個(gè)搜索在中間相遇時(shí)停止搜索。假設(shè)兩個(gè)搜索都使用寬度優(yōu)先搜索，則具有完備性，在每條邊/每個(gè)動(dòng)作的成本一致的情況下具有最優(yōu)性。

2. 流程圖和偽代碼

為了便于比較算法差異，我實(shí)現(xiàn)了寬度優(yōu)先搜索和雙向搜索兩種算法。

2.1 寬度優(yōu)先搜索

判斷隊(duì)列是否有終點(diǎn)和輸出路徑較為簡(jiǎn)單，下面只討論算法終點(diǎn)部分。

每次取出隊(duì)列首個(gè)節(jié)點(diǎn)，記其坐標(biāo)為(x,y)，向上下左右四個(gè)方向拓展新的四個(gè)節(jié)點(diǎn)。拓展節(jié)點(diǎn)的方式如下：

input: queue/* 輸入當(dāng)前節(jié)點(diǎn)隊(duì)列 */

output: queue/* 輸出更新后的隊(duì)列 */

def expand(queue) (x,y) = queue.front(); /* 取出隊(duì)首的節(jié)點(diǎn) */ /* 向上下左右四個(gè)方向拓展新的節(jié)點(diǎn) */ expand_node(x+1,y); expand_node(x-1,y); expand_node(x,y+1); expand_node(x,y-1); /* 將當(dāng)前節(jié)點(diǎn)出隊(duì) */ queue.pop();

判斷具體的節(jié)點(diǎn)是否要加入隊(duì)列時(shí)，判斷節(jié)點(diǎn)位置是否是通路’0’或終點(diǎn)’E’即可?？紤]到迷宮四周一圈都是墻壁’1’，所以不需要考慮出界的問(wèn)題。

input: queue, x, y/* 輸入當(dāng)前節(jié)點(diǎn)隊(duì)列，要加入的新節(jié)點(diǎn)的坐標(biāo) */

output: queue/* 輸出更新后的隊(duì)列 */

def expand_node(queue, x, y)

if (x,y) 處為通路或終點(diǎn)?

?then queue.push((x,y))??將(x,y)處變?yōu)閴Ρ?/p>

完整的源碼和詳細(xì)的文檔，上傳到了 【W(wǎng)RITE-BUG數(shù)字空間】，需要的請(qǐng)自取：
https://www.writebug.com/code/0c802727-c792-11ed-ac02-6479f0e5e323/#