（迷宮問題）
姓名：學號：20102769
班級：計1005
一．實驗內容：利用a*演算法，程式設計求解「迷宮問題」。
二．實驗要求：
1．程式語言不限，源程式要列印輸出，不得上交手寫源程式；2．給出程式執行結果；
3．其他方面可以自行發揮，包括演算法分析，題目理解，流程圖和程式設計心得等；
4．上交作業在封面上寫明姓名，學號和班級並左側裝訂。三．演算法分析1．定義幾個函式：
①g*(n)=k(s,n)：從初始節點s到節點n的最小耗散值路徑的實際耗散值。
②h*(n)=mink(n,ti)：從節點n到目標節點集﹛ti﹜中所有節點最小耗散值路徑的實際耗散值中的最小值。
③f*(n)= g*(n) + h*(n)：從初始節點s約束通過節點n的最小耗散值路徑的耗散值。
④評價函式：f(n)= g(n) + h(n)其中：f, g, h分別是f*, g*,h*的估計值。
（通常約定：f(n)按照公升序排列。）討論：
(1)由上述定義，得：g(n)≥g*(n)
(2)當h≡0且g(n)=d(n)時，f(n)= d(n)既寬度優先策略d(n)：節點深度
(3)h(n)稱為啟發函式。2．a*演算法：
1）open＝(s)，f(s)=g(s)+h(s)
2）loop：ifopen＝()thenexit(fail)3）n←first(open)
4）ifgoal(n)thenexit(success)5）remove(n,open)，add(n,closed)6）﹛mi﹜←expand(n)
●計算f(n,mi)=g(n,mi)+h(mi) (自s過n，mi到目標節點的耗散值)●add(mj,open)，標記mj到n的指標(mj不在open和closed中)
●iff(n,mk)＜f(mk)thenf(mk)←f(n,mk)，標記mk到n的指標(mk在open中)
●iff(n,ml)＜f(ml)thenf(ml)←f(n,ml)，標記ml到n的指標(ml在closed中)add(ml,open)，把ml放回到open中7）open中的節點按照f值公升序排列8）goloop3．具體說明：
1）迷宮用10*10的陣列表示，且迷宮大小可隨意設定，暫用10；2）對於open，closed中的節點的資料型別為：
typedef struct resultresult,*linknote;
3）insert( )插入函式對插入節點自動排序。
四．流程圖
開始初始化open，closed
計算f（s）
open為空n
first(open)—>ny失敗
yn為目標n
成功remove(n，open)，insert(n，closed)expand（n）—>
ninsert(n，closed)，標記mi到n的指標
mi在open中且f（n，mi）< f（mi）
yremove(n，open)，insert(n，open)，標記mi到n的指標
計算f（mi）
mi在closed中且（fn，mi）< f（mi）
yremove(n，closed)，insert(n，open)，標記mi到n的指標
n五．源程式
順序錶類順序表的每個成員都是乙個鍊錶用於儲存所走路徑typedef struct resultresult,*linknote;
class lianbiao;
#include ""#include<>
lianbiao::lianbiao()
int lianbiao::insert(result e)int coun=count-1;while(coun>=0&&(cla[coun].f><
cla[coun+1].y=cla[coun].y;cla[coun+1].
link=cla[coun].link;cla[coun+1].f=cla[coun].
f;cla[coun+1].level=cla[coun--].level;}cla[coun+1].
x= 1;}
int lianbiao::dele(result e)
主程式及規則函式
#include<>#include<>#include""
#define migongsize 11
int migong[migongsize][migongsize];//迷宮lianbiao closed; //closedlianbiaoopen; //open
int **oidrepeat(result neww,result rootw)
int left(result now,result * next)elsereturn 0;}
int above(result now,result * next)elsereturn 0;}
int right(result now,result * next)elsereturn 0;}
int below(result now,result * next)elsereturn 0;}
int goal(result end,result now)
int computef(result now,result end,int g)
mainvoid main()//switchif(falgzhuan)//for}//else
}//whileif(flag==1) {cout<<"走迷宮成功（2為路徑）"<0;k--){for(int j=1;j六．執行結果
七．程式設計心得
感覺a*演算法演示起來容易，但程式設計實現的時候，節點資料結構的選定和節點間的連線關係還是不太容易掌握的，所以大部分時間都在處理這兩個方面，其餘的則比較好實現。總體覺得a*演算法還是很有效且容易理解的。
人工智慧原理
北京華嘉物聯網國際學院 課程教學大綱 課程名稱 人工智慧 適用專業 2013級物聯網開發專業 課程類別 專業課 人工智慧 課程教學大綱 一 課程性質 人工智慧 是學院物聯網開發專業的專業課，也是物聯網開發專業教學計畫中的一門重要專業課。二 課程目標 人工智慧 教學目標在於通過對人工智慧課程的學習與研...
人工智慧習題
三大塊 一 搜尋 1 什麼是搜尋？有哪兩大類搜尋方法？兩者的區別是什麼？2 什麼是狀態空間？用狀態空間表示問題時，什麼是問題的解？什麼是最優解，最優解唯一嗎？3 在狀態空間的搜尋過程中，open表和closed表的作用與區別是什麼？4 廣度優先搜尋與深度優先搜尋有何區別？什麼時候使用廣度？什麼時候使...
人工智慧考試複習
人工智慧 第一章緒論 1 智慧型 intelligence 人的智慧型是他們理解和學習事物的能力，或者說，智慧型是思考和理解能力而不是本能做事能力。2 人工智慧 學科 人工智慧研究者們認為 人工智慧 學科 是電腦科學中涉及研究 設計和應用智慧型機器的乙個分支。它的近期主要目標在於研究用機器來模仿和執...