人工智能初步

教學案例2023/12/102狀態(tài)空間表示法案例12023/12/103目標

學會用狀態(tài)空間法表示重排九宮問題

了解狀態(tài)空間法的相關概念、基本思想2023/12/104程序算法問題使用計算求解問題的思路分析建模程序設計2023/12/105要求：用盡可能少棋步能由初始狀態(tài)到達目標狀態(tài)。例1[重排九宮問題]83647■5初始狀態(tài)123■84765目標狀態(tài)2831647528314765283164752831647528364175283147652318476528314765283167548326417528364175832147652837146523184765231847652831476528143765283167542816375483264175236841758321476528371465123847652341876528314765281437652831675428163754283641752836741523184765283164752318675428315674目標狀態(tài)初始狀態(tài)2023/12/107狀態(tài)

表示問題求解過程中每一步問題狀況的數(shù)據(jù)結構。例如，在棋弈中的格局即為問題的狀態(tài)。操作

把問題從一種狀態(tài)變換為另外一種狀態(tài)的手段。例如，棋弈中一步“走子”可將一個格局變?yōu)榱硪环N格局。狀態(tài)空間表示法2023/12/108狀態(tài)空間

用來描述一個問題的全部狀態(tài)以及這些狀態(tài)之間的相互關系。包含三個部分：

S—問題的初始狀態(tài)集合

F—操作集合

G—目標狀態(tài)的集合狀態(tài)空間樹（圖）

可用一個圖（樹）來直觀地表示出狀態(tài)空間。2023/12/109狀態(tài)空間表示法的基本思想

用“狀態(tài)”和“操作”來表示問題及其變化，形成狀態(tài)空間，求解問題的過程就是在狀態(tài)空間樹中搜索表示解的狀態(tài)的過程。搜索時，從某個初始狀態(tài)出發(fā)，每次使用一個操作使得問題能夠從一種狀態(tài)變?yōu)榱硗庖环N狀態(tài)，直到到達目標狀態(tài)為止。

假設有7個錢幣，任一選手只能將已分好的一堆錢幣分成兩堆個數(shù)不等的錢幣，兩位選手輪流進行，直到每一堆都只有一個或兩個錢幣，不能再分為止，哪個遇到不能分的情況，則就為輸。假設對方先走，我方是否有必勝策略？2023/12/1010[例2]分錢幣問題（7）（6,1）（5,2）（4,3）（5,1,1）（4,2,1）（3,2,2）（3,3,1）（4,1,1,1）（3,2,1,1）（2,2,2,1）（3,1,1,1,1）（2,2,1,1,1）（2,1,1,1,1,1）對方先走我方勝對方勝對方勝分錢幣問題的搏弈圖2023/12/1012◆結論◆評價2023/12/10131.還有哪些類似的問題可以使用狀態(tài)空間來描述？比如，井字棋、五子棋、拾火柴等游戲。畫出井字棋問題的狀態(tài)空間樹。過河問題如何使用狀態(tài)空間法表示？畫出過河問題的狀態(tài)空間圖。思考與練習井字棋井字棋游戲五子棋游戲……2023/12/1016

假定盤中放有n根火柴，由弈者A和B兩人參加比賽。比賽的規(guī)則是：兩名弈者輪流從盤中取走火柴，每次從盤中取走1，2或3根火柴均為合法著，否則為非法著。拿走盤中最后一根火柴的弈者為輸。假定A方先走，A有必勝策略嗎？若有就找出A的必勝策略。拾火柴游戲2023/12/1017搜索技術案例22023/12/1018目標

學會用幾種搜索技術求解重排九宮問題

體驗幾種搜索技術的基本思想2023/12/1019盲目搜索狀態(tài)空間樹（圖）上的搜索策略啟發(fā)式搜索寬度優(yōu)先搜索深度優(yōu)先搜索2023/12/1020求解思路：1.先將問題的求解過程用狀態(tài)空間樹表示出來2.在狀態(tài)空間樹上搜索問題的解答要求：用盡可能少棋步能由初始狀態(tài)到達目標狀態(tài)。例1[重排九宮問題]83647■5初始狀態(tài)123■84765目標狀態(tài)2831647528314765283164752831647528364175283147652318476528314765283167548326417528364175832147652837146523184765231847652831476528143765283167542816375483264175236841758321476528371465123847652341876528314765281437652831675428163754283641752836741523184765283164752318675428315674目標狀態(tài)初始狀態(tài)深度優(yōu)先搜索2831647528314765283164752831647528364175283147652318476528314765283167548326417528364175832147652837146523184765231847652831476528143765283167542816375483264175236841758321476528371465123847652341876528314765281437652831675428163754283641752836741523184765283164752318675428315674目標狀態(tài)初始狀態(tài)寬度優(yōu)先搜索2023/12/1023啟發(fā)式函數(shù):f(X)=g(X)+h(X)Xg(X)h(X)啟發(fā)式搜索2831647■5283164■752831■476528316475■283■147652■318476528314■765■83214765283714■65■2318476523■184765123■847650+41+51+31+52+32+32+43+33+43+23+44+1啟發(fā)函數(shù)：

f(X)=g(X)+h(X)

目標2831647■5283164■752831■476528316475■283■147652■318476528314■765■83214765283714■6545353343

4到目標到無結果的漫游8■32147653

啟發(fā)函數(shù)：

f(X)=h(X)

2023/12/1026

假設有7個錢幣，任一選手只能將已分好的一堆錢幣分成兩堆個數(shù)不等的錢幣，兩位選手輪流進行，直到每一堆都只有一個或兩個錢