知幟的表雜方法21狀態(tài)空間法22問題歸絢法E3謂詞邏著法24語網(wǎng)絡(luò)法25框架示法26劇本(aerial)袁示27過程(a)殺小結(jié)20192/22§2狀態(tài)空間法問題求解(problemsolving)是個大課題,它涉及歸約、推斷、決策、規(guī)劃、常識推理、定理證明和相關(guān)過程的核心概念。在分析了人工智能研究中運(yùn)用的問題求解方法之后,就會發(fā)現(xiàn)許多問題求解方法是采用試探搜索方法的。也就是說,這些方法是通過在某個可能的解空間內(nèi)尋找一個解來求解問題的。這種基于解答空間的問題表示和求解方法就是狀態(tài)空間法,它是以狀態(tài)和算符(operator)為基礎(chǔ)來表示和求解問題的。20192/22悶題部斛故術(shù)雨個主要的方面問題的表示:如果描述方法不對,對問題求解會帶來很大的困難求解的方法:采用試探搜索方法。20192/22狀態(tài)空間法三要點(diǎn)狀態(tài)(state):表示問題解法中每一步問題狀況的數(shù)據(jù)結(jié)構(gòu);算符(operator):把問題從一種狀態(tài)變換為另種狀態(tài)的手段狀態(tài)空間方法:基于解答空間的問題表示和求解方法,它是以狀態(tài)和算符為基礎(chǔ)來表示和求解問題的。20192/221向題狀態(tài)描述要完成某個問題的狀態(tài)描述,必須確定三件事:1該狀態(tài)描述方式,特別是初始狀態(tài)描述;2操作符集合及其對狀態(tài)描述的作用3.目標(biāo)狀態(tài)描述的特性。20192/22定義狀態(tài)(state):為描述某類不同事物間的差別而引入的一組最少變量q0,q1,…,qn的有序集合,其矢量形式如下:Q=[q0,41,…,q式中每個元素q(i=0,1,…,n)為集合的分量,稱為狀態(tài)變量20192/22給定每個變量的一組值就得到一個具體的狀態(tài),如Qk=lqok,qIk,ink它只是問題所有可能狀態(tài)的羅列,還必須描述這些狀態(tài)之間的可能變化。所謂操作,或稱為算子是引起狀態(tài)中的某分量發(fā)生改變,從而使問題由一個具體狀態(tài)A變化為另一具體狀態(tài)B的作用。20192/22算符:使問題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作符或算符。操作符可為走步、過程、規(guī)則、數(shù)學(xué)算子、運(yùn)算符號或邏輯符號等。問題的狀態(tài)空間(statespace):是一個表示該問題全部可能狀態(tài)及其關(guān)系的圖,它包含三種說明的集合,即所有可能的問題初始狀態(tài)集合S(初始狀態(tài)S∈S)、操作符集合F以及目標(biāo)狀態(tài)集合G(GcS)。可把狀態(tài)空間記為三元狀態(tài)(S,F,G)。F狀態(tài)空間可用有向圖來表示20192/22狀態(tài)空間的一個解使一個有限的操作算子序列,它使初始狀態(tài)轉(zhuǎn)化為目標(biāo)狀態(tài):S-f1->S1f2fK>G20192/22狀態(tài)空間表示得釋讓我們先用數(shù)碼難題(puzzleproblem)來說明狀態(tài)空間表示的概念。由15個編有1至15并放在4×4方格棋盤上的可走動的棋子組成。棋盤上總有一格是空的,以便可能讓空格周圍的棋子走進(jìn)空格,這也可以理解為移動空格。圖中繪出了兩種棋局,即初始棋局和目標(biāo)棋局,它們對應(yīng)于該下棋問題的初始狀態(tài)和目標(biāo)狀態(tài)。如何把初始棋