人工智能-搜索策略實驗報告

搜索策略實驗報告目錄一、實驗內容 一、實驗內容熟悉和掌握啟發(fā)式搜索的定義、估價函數(shù)和算法過程，比較不同算法的性能。以八數(shù)碼問題或路徑規(guī)劃等問題為例設計啟發(fā)式搜索算法，改變啟發(fā)函數(shù)，觀察結果的變化，分析原因。二、實驗目的熟悉和掌握各種啟發(fā)式搜索策略的思想，掌握A*算法的定義、估價函數(shù)和算法過程，理解求解流程和搜索順序。三、實驗內容分別以各種搜索算法為例演示搜索過程，比較不同算法的性能；分析各種算法中的OPEN表CLOSE表的生成過程；分析估價函數(shù)對搜索算法的影響；以八數(shù)碼問題或路徑規(guī)劃等問題為例設計啟發(fā)式搜索算法，改變啟發(fā)函數(shù)，觀察結果的變化，分析原因。四、實驗環(huán)境以下兩種實驗環(huán)境可供選擇：搜索策略可視化實驗環(huán)境，如圖1所示。圖SEQ圖\*ARABIC1搜索策略可視化實驗環(huán)境C＋＋語言編程環(huán)境，語言環(huán)境可以自選。五、實驗步驟開始演示。進入搜索策略演示程序，可從多種不同搜索算法選擇裝載相關源文件；選擇不同的搜索算法，點擊“autosearch”觀察搜索過程；設置不同屬性，觀察搜索過程的變化；觀察運行過程和搜索順序，理解啟發(fā)式搜索的原理；算法流程的任一時刻的相關狀態(tài),以算法流程高亮、open表、close表、節(jié)點靜態(tài)圖、當前擴展節(jié)點移動圖等5種形式在按鈕上方同步顯示,便于深入學習理解搜索算法。根據(jù)程序運行過程畫出搜索算法框圖；若要自己設計改進算法并運行，可參考幫助文件。六、搜索策略實驗報告表姓名王啟樂年級信安1802班指導老師鐘萍日期2020.11.18實驗目的熟悉和掌握各種啟發(fā)式搜索策略的思想，掌握A*算法的定義、估價函數(shù)和算法過程，理解求解流程和搜索順序。搜索圖算法比較廣度優(yōu)先搜索最佳優(yōu)先搜索A*算法Open表{初始節(jié)點S}{節(jié)點1，節(jié)點2}{節(jié)點2，節(jié)點3，節(jié)點4}{節(jié)點3，節(jié)點4，節(jié)點5，節(jié)點6}{節(jié)點4，節(jié)點5，節(jié)點6，節(jié)點7}{節(jié)點5，節(jié)點6，節(jié)點7，節(jié)點8}{節(jié)點6，節(jié)點7，節(jié)點8，節(jié)點9目標節(jié)點G}{節(jié)點7，節(jié)點8，節(jié)點9，目標節(jié)點G，節(jié)點10}{節(jié)點8，節(jié)點9，目標節(jié)點G，節(jié)點10}{節(jié)點9，目標節(jié)點G，節(jié)點10}{目標節(jié)點G，節(jié)點10}{節(jié)點10}{初始節(jié)點S}{節(jié)點2，節(jié)點1}{節(jié)點6，節(jié)點5，節(jié)點1}{節(jié)點10，節(jié)點5，節(jié)點1}{節(jié)點5，節(jié)點1}{目標節(jié)點G，節(jié)點9，節(jié)點1}{節(jié)點9，節(jié)點1}{初始節(jié)點S}{節(jié)點2，節(jié)點1}{節(jié)點1，節(jié)點5，節(jié)點6}{節(jié)點5，節(jié)點6，節(jié)點4，節(jié)點3}{節(jié)點6，節(jié)點4，目標節(jié)點G，節(jié)點9，節(jié)點3}{節(jié)點4，目標節(jié)點G，節(jié)點9，節(jié)點3，節(jié)點10}{目標節(jié)點G，節(jié)點9，節(jié)點3，節(jié)點10，節(jié)點8}{節(jié)點9，節(jié)點3，節(jié)點10，節(jié)點8}Close表{}{初始節(jié)點S}{初始節(jié)點S，節(jié)點1}{初始節(jié)點S，節(jié)點1，節(jié)點2}{初始節(jié)點S，節(jié)點1，節(jié)點2，節(jié)點3}{初始節(jié)點S，節(jié)點1，節(jié)點2，節(jié)點3，節(jié)點4}{初始節(jié)點S，節(jié)點1，節(jié)點2，節(jié)點3，節(jié)點4，節(jié)點5}{初始節(jié)點S，節(jié)點1，節(jié)點2，節(jié)點3，節(jié)點4，節(jié)點5，節(jié)點6}{初始節(jié)點S，節(jié)點1，節(jié)點2，節(jié)點3，節(jié)點4，節(jié)點5，節(jié)點6，節(jié)點7}{初始節(jié)點S，節(jié)點1，節(jié)點2，節(jié)點3，節(jié)點4，節(jié)點5，節(jié)點6，節(jié)點7，節(jié)點8}{初始節(jié)點S，節(jié)點1，節(jié)點2，節(jié)點3，節(jié)點4，節(jié)點5，節(jié)點6，節(jié)點7，節(jié)點8，節(jié)點9}{初始節(jié)點S，節(jié)點1，節(jié)點2，節(jié)點3，節(jié)點4，節(jié)點5，節(jié)點6，節(jié)點7，節(jié)點8，節(jié)點9，目標節(jié)點G}{}{初始節(jié)點S}{初始節(jié)點S，節(jié)點2}{初始節(jié)點S，節(jié)點2，節(jié)點6}{初始節(jié)點S，節(jié)點2，節(jié)點6，節(jié)點10}{初始節(jié)點S，節(jié)點2，節(jié)點6，節(jié)點10，節(jié)點5}{初始節(jié)點S，節(jié)點2，節(jié)點6，節(jié)點10，節(jié)點5，目標節(jié)點G}{}{初始節(jié)點S}{初始節(jié)點S，節(jié)點2}{初始節(jié)點S，節(jié)點2，節(jié)點1}{初始節(jié)點S，節(jié)點2，節(jié)點1，節(jié)點5}{初始節(jié)點S，節(jié)點2，節(jié)點1，節(jié)點5，節(jié)點6}{初始節(jié)點S，節(jié)點2，節(jié)點1，節(jié)點5，節(jié)點6，節(jié)點4}{初始節(jié)點S，節(jié)點2，節(jié)點1，節(jié)點5，節(jié)點6，節(jié)點4，目標節(jié)點G}估價函數(shù)f(n)為節(jié)點n的深度f(n)=h(n)h(n)為估計的從n到目標的最優(yōu)距離f(n)=g(n)+h(n)g(n)為搜索樹中S到n這段路徑的代價，h(n)為估計的從n到目標的最優(yōu)距離搜索節(jié)點次序記錄{初始節(jié)點S，節(jié)點1，節(jié)點2，節(jié)點3，節(jié)點4，節(jié)點5，節(jié)點6，節(jié)點7，節(jié)點8，節(jié)點9，目標節(jié)點G}{初始節(jié)點S，節(jié)點2，節(jié)點6，節(jié)點10，節(jié)點5，目標節(jié)點G}{初始節(jié)點S，節(jié)點2，節(jié)點1，節(jié)點5，節(jié)點6，節(jié)點4，目標節(jié)點G}觀測結果學生結論廣度優(yōu)先搜索算法搜索成功，但擴展的節(jié)點數(shù)較多搜索速度較慢，其以接近起始節(jié)點的程度依次擴展節(jié)點，具有完備性，能找到最優(yōu)解，但時間復雜度和空間復雜度較高，常常速度比較慢。最佳優(yōu)先搜索算法搜索成功，擴展的節(jié)點數(shù)少，搜索速度較快，它是一種不追求最優(yōu)解，只希望求得較為滿意的解。因為他省去了為了找到最優(yōu)解要窮盡所有可能而必須耗費的大量時間。A*算法搜索成功，擴展的節(jié)點數(shù)較少，搜索速度較快，它是一種靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法，也是解決許多搜索問題的有效算法。算法中的距離估算值與實際值越接近，最終搜索速度越快。七、實驗結論啟發(fā)式搜索算法A*流程圖和算法框圖；A*算法是一種啟發(fā)式搜索，評估方程是：f(n)=d(n)+h(n)，當OPEN表不為空時，每次循環(huán)從OPEN表中取出評估值最小的狀態(tài)節(jié)點進行擴展，判斷該節(jié)點是否為目標節(jié)點，如果是則輸出移動的路徑；如果不是則將子節(jié)點放入OPEN表。并且為了避免狀態(tài)的重復搜索，用hash函數(shù)來判斷狀態(tài)是否存在，如果已存在則不會擴展該節(jié)點。A*算法流程圖如下：圖SEQ圖\*ARABIC2A*算法流程圖試分析估價函數(shù)的值對搜索算法速度的影響；估價函數(shù)能夠提供一個評定候選擴展結點的方法，以確定哪個節(jié)點最有可能在通向目標的最佳路徑上。估價函數(shù)構造得越準確，就越快能找到最應該被擴展的節(jié)點，搜索算法的速度就會越快。以路徑規(guī)劃問題為例設計啟發(fā)式搜索算法，改變啟發(fā)函數(shù)，觀察結果的變化，分析原因。修改前的啟發(fā)函數(shù)：圖SEQ圖\*ARABIC3修改前的啟發(fā)函數(shù)運行結果：圖SEQ圖\*ARABIC4修改前的啟發(fā)函數(shù)的運行結果修改后的啟發(fā)函數(shù)：圖SEQ圖\*ARABIC5修改后的啟發(fā)函數(shù)運行結果：圖SEQ圖\*ARABIC6修改后的啟發(fā)函數(shù)的運行結果可以觀察到，修改后的啟發(fā)函數(shù)導致搜索算法速度明顯變慢。根據(jù)A*算法分析啟發(fā)式搜索的特點。啟發(fā)式搜索算法，就是在狀態(tài)空間中的搜索對每一個搜索的位置進行評估，得到最好的位置，再從這個位置進行搜索直到目標。A*算法把從初始節(jié)點到n節(jié)點的實際代價g(n)和從n到目標節(jié)點最佳路徑的估計代價h(n)結合起來對節(jié)點n進行評價，從而確定下一個被擴展的節(jié)點。附：A*搜索算法代碼import

copy

#棋盤的類，實現(xiàn)移動和擴展狀態(tài)

class

grid:

def

__init__(self,stat):

self.pre=None

#stat是一個二維列表

self.stat=stat

self.find0()

self.update()

#更新啟發(fā)函數(shù)的相關信息

def

update(self):

self.fH()

self.fG()

self.fF()

#G是深度，也就是走的步數(shù)

def

fG(self):

if(self.pre!=None):

self.G=self.pre.G+1

else:

self.G=0

#H是和目標狀態(tài)距離之和

def

fH(self):

target=[[1,2,3],[8,0,4],[7,6,5]]

self.H=0

for

i

in

range(3):

for

j

in

range(3):

targetX=target[i][j]

nowP=self.findx(targetX)

#曼哈頓距離之和

self.H+=abs(nowP[0]-i)+abs(nowP[1]-j)

#F是啟發(fā)函數(shù)，F(xiàn)=G+H

def

fF(self):

self.F=self.G

#+

self.H

#以三行三列的形式輸出當前狀態(tài)

def

see(self):

for

i

in

range(3):

print(self.stat[i])

print("F=",self.F,"G=",self.G,"H=",self.H)

print("-"*10)

#查看找到的解是如何從頭移動的

def

seeAns(self):

ans=[]

ans.append(self)

p=self.pre

while(p):

ans.append(p)

p=p.pre

ans.reverse()

for

i

in

ans:

i.see()

#找到數(shù)字x的位置

def

findx(self,x):

for

i

in

range(3):

if(x

in

self.stat[i]):

j=self.stat[i].index(x)

return

[i,j]

#找到0，也就是空白格的位置

def

find0(self):

self.zero=self.findx(0)

#擴展當前狀態(tài)，也就是上下左右移動。返回的是一個狀態(tài)列表，也就是包含stat的列表

def

expand(self):

i=self.zero[0]

j=self.zero[1]

gridList=[]

if(j==2

or

j==1):

gridList.append(self.left())

if(i==2

or

i==1):

gridList.append(self.up())

if(i==0

or

i==1):

gridList.append(self.down())

if(j==0

or

j==1):

gridList.append(self.right())

return

gridList

#deepcopy多維列表的復制，防止指針賦值將原列表改變

#move只能移動行或列，即row和col必有一個為0

#向某個方向移動

def

move(self,row,col):

newStat=copy.deepcopy(self.stat)

tmp=self.stat[self.zero[0]+row][self.zero[1]+col]

newStat[self.zero[0]][self.zero[1]]=tmp

newStat[self.zero[0]+row][self.zero[1]+col]=0

return

newStat

def

up(self):

return

self.move(-1,0)

def

down(self):

return

self.move(1,0)

def

left(self):

return

self.move(0,-1)

def

right(self):

return

self.move(0,1)

#判斷狀態(tài)g是否在狀態(tài)集合中，g是對象，gList是對象列表

#返回的結果是一個列表，第一個值是真假，如果是真則第二個值是g在gList中的位置索引

def

isin(g,gList):

gstat=g.stat

statList=[]

for

i

in

gList:

statList.append(i.stat)

if(gstat

in

statList):

res=[True,statList.index(gstat)]

else:

res=[False,0]

return

res

#Astar算法的函數(shù)

def

Astar(startStat):

#open和closed存的是grid對象

open=[]

closed=[]

#初始化狀態(tài)

g=grid(startStat)

open.append(g)

#time變量用于記錄遍歷次數(shù)

time=0

#當open表非空時進行遍歷

while(open):

#根據(jù)啟發(fā)函數(shù)值對open進行排序，默認升序

open.sort(key=lambda

G:G.F)

#找出啟發(fā)函數(shù)值最小的進行擴展

minFStat=open[0]

#檢查是否找到解，如果找到則從頭輸出移動步驟

if(minFStat.H==0):

print("found

and

times:",time,"moves:",minFStat.G)

minFStat.seeAns()

break

#走到這里證明還沒有找到解，對啟發(fā)函數(shù)值最小的進行擴展

open.pop(0)

closed.append(minFStat)

expandStats=minFStat.expand()

#遍歷擴展出來的狀態(tài)

for

stat

in

expandStats:

#將擴展出來的狀態(tài)（二維列表）實例化為grid對象

tmpG=grid(stat)

#指針指向父節(jié)點

tmpG.pre=minFStat

#初始化時沒有pre，所以G初始化時都是0