下次自動登錄
現在的位置:
& 綜合 & 正文
A*演算法解決迷宮問題（DIY製作地圖類似於小遊戲，界面設計非常不錯。）
人工智慧老師要求實現一個，剛開始的時候自己做的是一個深度優先搜索，然後又學了A*，覺得深度優先效率還是不行，就打算用A*演算法實現兔子找蘿蔔的小遊戲。
地圖設計採用的是坦克大戰中的地圖設計圖案。
這是用C語言寫的，編譯器是VC6.0
需要源參考的可以在我的csdn下載資源中找到。
附上下載地址：http://download.csdn.net/detail/yujin753/7060747
問題的描述
迷宮問題可以表述為：一個二維的網格，0表示點可走，1表示點不可以走，點用（x，y）表示，尋找從某一個給定的起始單元格出發， 經由行相鄰或列相鄰的單元格(可以通過的)，最終可以到達目標單元格的、所走過的單元格序列。在任一個單元格中，都只能看到與它鄰近的4個單元格(如果位於底邊，則只有3個；位於4個角上，則只有2個是否能通過。迷宮問題用傳統的廣度優先搜索或帶回溯的深度優先搜索等演算法都能很好地解決。當然採用A*演算法更能體現對人工智慧這門的理解，比起盲目的搜索，A*演算法更具有針對性。
深度優先搜索演算法實現
所謂「深度優先」，即：狀態樹的生長或展開，首先沿狀態樹的深度方向進行。深度優先搜索演算法需要記錄下狀態樹的生長過程。深度優先搜索演算法是一種盲目的搜索演算法，搜索中可能很多次的搜索到目標點，深度搜索演算法通過不斷剪枝，尋找出一條從起始點到目標點最近且最省時的路徑，即深度優先搜索演算法也是一種全局的搜索演算法，這樣的深度優先搜索演算法運用到未知迷宮搜救中是沒有意義的。而本次實驗中，深度優先搜索演算法是以找到目標物為目的，沒有剪枝的步驟，只要搜索到目標物，迷宮的搜索過程就成功退出。
深度優先搜索的一些特點：
a) 一般不能保證找到最優解
b) 當深度限制不合理時，可能找不到解，可以將演算法改為可變深度限制
c) 最壞情況時，搜索空間等同於窮舉
d) 是一個通用的與問題無關的方法
圖一 深度優先搜索
深度優先偽碼：
1) Push(S,Open) 將初始節點放入Open表中；
2) Judge(S) 判斷S節點是不是目標節點，if（S為目標節點），那麼找到目標節點；
3) While（判斷Open表是否為空）
如果為空，那麼搜索失敗 end；
否則把第一個節點N從Open表中移至Close表中；
4) 將N的後繼節點放入Open表中；
判斷後繼節點中是否有目標節點；
If（存在目標節點）
A*演算法實現
A*演算法是人工智慧中的一種搜索演算法，是一種啟發式搜索演算法，它不需遍歷所有節點，只是利用包含問題啟發式信息的評價函數對節點進行排序（Node Ordering），使搜索方向朝著最有可能找到目標併產生最優解的方向。它的獨特之處是檢查最短路徑中每個可能的節點時引入了全局信息，對當前節點距終點的距離做出估計，並作為評價節點處於最短路線上的可能性的度量。
I．啟發函數的確定
A*演算法中引入了評估函數，評估函數如下：
f（n）=g（n）+h（n）
其中：n是搜索中遇到的任意狀態。g(n)是從起始狀態到n的代價。h(n)是對n到目標狀態代價的啟發式估計。即評估函數f ( n) 是從初始節點到達節點n 處已經付出的代價與節點n 到達目標節點的接近程度估價值的總和[10]。
這裡我們定義n點到目標點的最小實際距離為h（n）*，A*演算法要滿足的條件為：
h（n）&=h（n）*
由前面的迷宮問題的描述我們可以知道，迷宮走的時候只能往上下左右走，每走一步，代價為1，這裡我們採用的估價函數為當前節點到目標節點的曼哈頓距離，即：
h（n）=|end.x – n.x|+ |end.y – n.y|[11]
這裡end表示迷宮的目標點，n表示當前點，很明顯這裡h（n）&=h（n）*。
g（n）容易表示，即每走一步的代價是1，所以利用f（n）=g（n）+h（n）這種策略，我們可以不斷地逼近目標點，從而找到問題的解。
II A*的主要實現步驟的偽碼錶示
1） OPEN:=(s), f(s):=g(s)+h(s);
2）LOOP: IF OPEN=( ) THEN EXIT(FAIL);
3） n:=FIRST(OPEN);
4）IF GOAL(n) THEN EXIT(SUCCESS);
5）REMOVE(n, OPEN), ADD(n, CLOSED);
6）EXPAND(n) →{mi},
計算f(n, mi):=g(n, mi)+h(mi);
ADD(mj, OPEN), 標記mj到n的指針；
IF f(n, mk)&f(mk) THEN f(mk):=f(n, mk),
標記mk到n的指針；
IF f(n, ml)&f(ml,) THEN f(ml):=f(n, ml),
標記ml到n的指針,
ADD(ml, OPEN);
7, OPEN中的節點按f值從小到大排序；
8, GO LOOP；
這裡OPEN表和CLOSED表分別用來存儲要搜索的狀態結點和存儲已經訪問過的狀態。
該測試程序在VC6.0環境下編譯實現,用的是。
代碼中數據結構設計
struct mark //定義迷宮內點的坐標類型
struct mark start, //start,end入口和出口的坐標
struct Element //棧元素，
{//估價函數
//啟發函數
int x,y; //x行,y列
Element elem,e;
typedef struct LStack //鏈棧
struct LStack *
PLStack Open,C//OPEN表和CLOSE表用來儲存鏈節點
函數框架實現
InitStack(Open); //用於初始化open 表
InitStack(Close); //用於初始化close表
Push(Open,elem); //表示初始節點elem進入open表
while(!StackEmpty(Open)&&Flag==0) //棧不為空 有路徑可走
Pop(Open,elem); //將open表中的當前元素提出來
Push(Close,elem);//將從open表取出來的元素放入close表
if（判斷elem節點的子節點是否可以走）判斷上下左右{
if（elem_child不為目標節點）{
Push(Open,elem_child) 子節點進Open表，這裡的push（）函數進入棧中，為有序進入，也就是說進棧是按順序插入的。
else(該節點為目標節點){
Push(Close,elem_child)//目標節點進close表
Flag=1//將標誌置為一表示已經找到了目標節點
End//找到了目標節點結束
If（StackEmpty(Open)||Flag==0）
Printf（」迷宮沒有解\n」）
返回迷宮沒有解//表示走到這裡還沒有找到解則迷宮走不出去
核心函數代碼
int InitStack(PLStack &S) //初始化鏈棧，Open表和Close表初始化
int StackEmpty(PLStack S)//判斷棧是否為空
if(S==NULL)
int Push1(PLStack &S, Element e)//壓入新數據元素
PLStack q,t;
p=(PLStack)malloc(sizeof(LStack));
p-&elem.g=//表示深度
//估價函數即使用曼哈頓距離表示
p-&elem.h=abs(end.x-e.x)+abs(end.y-e.y);
p-&elem.f=p-&elem.h+p-&elem.g;
p-&elem.x=e.x;
p-&elem.y=e.y;
p-&next=NULL;
if(NULL==S||p-&elem.f&=S-&elem.f)
p-&next=S;
//return 1;
while(t!=NULL)
if(p-&elem.f&t-&elem.f)
p-&next=t;
q-&next=p;
int Pop(PLStack &S,Element &e) //棧頂元素出棧
if(!StackEmpty(S))
界面設計非常友好、清晰、表達明確、功能集中、操作簡單。
迷宮大小設定為18*25的，入口和出口的位置分別設為(1.0)、（16,24），
迷宮狀態用一個二維表存儲，0表示可以走，即界面中的可行域表示，1表示不能走，即界面中的黃金牆和鉑金牆。可選的地圖有三個，每次只能選擇一個，選擇完地圖之後就可以畫迷宮了，之後就可以搜索了。
我採用的WindowsAPI程序設計，整個的界面是利用windows程序設計的窗口設計實現的，地圖的樣子是通過一個地圖編輯器來實現的，總體給人的感覺是比較清楚、清晰，也比較新穎。然後把地圖當作圖片畫出來，即每一小格代表的數字，決定了地圖將會畫出什麼顏色的圖片來，當二維表中的數據為1時，我們就可以畫出牆的圖片，當其中數據為0是我們就可以畫出可行域的圖片。通過這樣的方法，我們可以比較簡單的實現地圖樣式的變換，能夠達到非常不錯的效果，旁邊的選擇地圖按鈕能夠幫助我們選擇我們想要的地圖，選擇好了之後，運行完程序，然後通過地圖重置可以實現地圖的刪除，然後可以再進行地圖的選擇，非常方便的實現了地圖的更換。
調用函數：
hmap = GetDlgItem(hwnd,IDC_MAP);
hm = GetDC(hmap);
將整個窗口的句柄控制，使用函數：
BitBlt(hm,x,y,p_Lsize,p_Hsize,h,0,0,SRCCOPY);
其中hm為窗口句柄，x，y為對應位置的坐標，p_Lsize,p_Hsize為圖片的大小，h為圖片畫的位置，這樣就可以畫出界面了。
圖二 迷宮界面
運行結果分析
從程序運行的結果我們可以知道，深度優先搜索和A*搜索兩種搜索策略都實現了。我們也已經知道，深度優先搜索是一種盲目的搜索，也就是說搜索過程中並沒有帶啟發式信息，而A*搜索帶了啟發式信息，在程序運行過程中，我們可以明顯的感知，這兩種演算法的區別。
我通過實驗驗證了深度優先搜索和A*搜索在本規模迷宮環境下的情況，可以利用遍歷Open表和Close表中的節點，得出所擴展的節點和所走的步數。這裡我們可以計算出三個地圖走出迷宮需要走的步數。
下面的數據為兩種搜索演算法從初始節點走到目標節點所走的步數：
表一 深度優先搜索和A*搜索所走步數比較
深度優先搜索
從上表我們可以明顯看出來採用啟發式的A*搜索比盲目的深度優先搜索所走的步數更少，也就是說，在迷宮問題中採用A*搜索演算法較傳統的深度優先搜索能更快的找到迷宮的目標節點，並且效率提高的非常快。從表中可以看出，效率提高了兩倍多，這樣在更大規模的迷宮問題中，能夠節約更多的時間找到問題的解。
&&&&推薦文章:
【上篇】【下篇】[迷宮遊戲] Maze 有超過百萬個謎題等你來解謎唷！（Android） _ 重灌狂人作者：
CoreYi, &&Tweet
一般的益智解謎遊戲是不是一下就破關玩完了呢？「Maze」迷宮可有超過百萬個迷宮謎題，就是要你花一輩子來解謎！（哎唷！好像很嚴重的樣子）以迷宮的尺寸大小分為四種難易度，基本上「tiny 10×10」及「small 20×20」比較適合給小朋友玩，大朋友可以從「big 40×40」或是直接挑戰「large 80×80」，才能展現你的超強解謎能力唷！遊戲畫面很簡潔，沒有多餘的綴飾，也沒有熱鬧的配樂，是一款很安靜、很單純的迷宮遊戲，就是要你專心的將小瓢蟲送到終點，題組沒有前後順序，這題解不開可直接選擇其它題組，重點是謎題真的多到看不見盡頭，足夠讓你玩到頭毛鬍鬚白唷！ ▇ 軟體小檔案 ▇軟體名稱：迷宮軟體語言：英文開發人員：Perun Labs軟體性質：免費軟體系統支援：Android 2.2 以上軟體下載：在 Android 手機中開啟 Play 商店，搜尋「perunlabs maze」即可下載安裝，或「按這裡」從網頁遠端安裝。&遊戲畫面：按「play」進入選擇難易度。上面兩個實在太過於簡單，比較適合給小朋友玩，下面兩個則真的有難度，就適合大朋友或比較有程度的小朋友玩囉！&接著選擇題組，沒有前後順序，所以可任意選擇。遊戲控制方式有兩種，可透過在螢幕上畫出手勢來操縱小瓢蟲的方向或是使用按鍵控制，選擇完畢再按右下角的按鈕進入遊戲。&這是 tiny 10×10 的難度，簡單到爆炸吧！但給小朋友玩應該是不錯的唷！只要將小瓢蟲移動至「x」處就過關囉！&如果選擇「big 40×40」或是「large 80×80」就無法在一個畫面看到整個迷宮圖，可按左上角的暫停鈕，開啟下方功能鍵，使用縮小功能調整迷宮的大小。&左圖是「large 80×80」的迷宮全景，是不是很驚人，這走到眼花都解不開了吧！？本來想幫大家先看看一個難度到底可以有多少謎題，不過我翻頁翻到 2000 的時候，就放棄了…&&非經授權，請勿全文轉載，本文網址: /15390/maze.html
→ 免費訂閱最新文章：
&(如何訂閱？) 作者:
| 發佈日期: 文章目錄：首頁 >> Android 手機、平板電腦 >> 好玩遊戲、休閒益智注意事項：本站所介紹之軟體、設定或網站服務，經實際安裝測試並通過防毒軟體掃毒。但因為不同電腦環境與軟體設定可能都各有差異，建議您僅在非工作用的電腦安裝、測試，避免因為不可預知的錯誤、當機或軟硬體衝突，影響您的工作或電腦運作。另外，在進行任何重要的操作與設定之前，記得先行備份電腦中的重要資料，避免因為未依指示的不當操作或其他疏失造成資料毀損。當您依照本文所提供之訊息執行各種操作，表示您已閱讀此注意事項並同意自行承擔可能之風險與責任。&&[行政院人事行政局] 停班停課公告網頁 (颱風假)又有漏洞了！快更新 Flash Player 程式！！最新 PotPlayer 影音播放器繁體中文版下載[下載] KMPlayer 影音播放器 最新 繁體中文版！[免費下載] Windows 10 簡體/繁體中文版 光碟映像 (ISO 檔案) 官方網站正式版本[統一發票] 中獎號碼 104 年 7、8 月[下載] 小紅傘 Avira 免費防毒軟體（繁體中文版）LINE 電腦版下載（Windows 版、Mac 版）[下載] 千千靜聽 TTPlayer 繁體中文版 (百度音樂)！[Android 模擬器] Genymotion v2.5.3 超強100%完全模擬，在電腦中也能玩 Android 遊戲、App[免費][模擬器] BlueStacks 免買手機、平板電腦，直接在電腦玩 Android 遊戲、APP關閉煩死人的「IE 安全性警告」視窗！[最新版][下載] avast! antivirus 免費防毒軟體 繁體中文版！追蹤、訂閱本站最新文章 Email
訂閱：按這裡 Facebook 訂閱：按這裡 Google+ 訂閱：按這裡 Google Play 書報攤訂閱：這裡 噗浪 Plurk 訂閱：按這裡 Twitter 訂閱：按這裡 Feedly 訂閱：按這裡 Flipboard 訂閱：按這裡(用手機,平板開) RSS 訂閱：按這裡最新文章 超酷的「Cardiio」光看臉就能測量心跳！內含真人語音七分鐘鍛煉計劃（iPhone, iPad） 「Circle Heroes」可愛又富有禪意，頗有違和感的街機遊戲（Android） [統一發票] 中獎號碼 104 年 7、8 月，恭喜大家中大獎！ [最新版][下載] avast!
Antivirus 2015 繁體中文版！v10.4. 防毒軟體（免費合法序號） 已超越解謎遊戲等級，來「花語月」體驗神祕又優美的奇幻旅程（iPhone, iPad） 超簡單的拖曳設定，不論大小事都可快速的「提醒一下」（Android） 史努比迷們！快來「加入史努比的世界」製作你的專屬角色！ 超美的「月亮動態桌布」中秋賞不到月？就在手機桌面放一個吧！（Android） [下載] CCleaner v5.10 繁體中文版！（清除電腦垃圾，讓 Windows 跑得更順暢！） Folder Size Explorer 快速顯示資料夾大小、檔案數量 ，刪檔快多了！ Zipware 壓縮/解壓縮軟體、壓縮檔加密/轉檔工具 女朋友的好朋友「隱私月月記」永遠不會背叛妳的最佳閨蜜（iPhone, Android） Rye 中文有聲書讓小朋友聽聽「中秋節」的由來吧！（Android） 「Doodle Mirror」看了絕對笑噴的超級變臉 App，還可變聲錄影唷！（iPhone, iPad） WinToFlash v1.3 自製可開機、可安裝系統的「USB 重灌隨身碟」 全部文章分類全部文章分類選擇分類Android 手機、平板電腦&&&其他工具、Android 未分類&&&好玩遊戲、休閒益智&&&影音播放、影視編輯&&&拍照攝影特效、繪圖&&&文書處理、編輯應用&&&桌面美化、介面增強&&&系統設定、功能調整&&&網路瀏覽、防毒軟體&&&美食旅遊、地圖服務&&&購物理財、生活應用&&&通訊、聊天社交服務&&&音樂播放、編輯轉檔iPad, iPhone 手機、平板電腦&&&其他工具、未分類&&&好玩遊戲、休閒益智&&&影視播放、影音編輯轉檔&&&拍照攝影特效、繪圖工具&&&文書處理、辦公室應用&&&桌布美化、系統增強工具&&&系統設定、功能調整&&&網路瀏覽、防毒軟體&&&美食旅遊、地圖服務&&&購物理財、生活應用&&&通訊、聊天、社交服務&&&音樂播放、音樂編輯轉檔Mac OS X 蘋果電腦、Apple&&&下載工具、P2P、FTP&&&好玩遊戲、休閒益智&&&影視編輯、轉檔播放軟體&&&文書編輯、PDF、字典&&&桌面美化、介面最佳化&&&檔案管理、壓縮備份還原&&&看圖軟體、繪圖、轉檔&&&磁碟管理、光碟燒錄&&&系統維護、設定工具&&&系統設定、功能調整&&&網路工具、郵件LINE即時通訊&&&蘋果電腦-未分類&&&防毒、防火牆、病毒檢測&&&音樂編輯、轉檔播放軟體Windows PhoneWindows 系統、PC 個人電腦&&&Chrome,Firefox,IE,Opera 瀏覽器&&&Email 郵件收發、收信軟體&&&LINE、MSN、即時通訊軟體&&&下載/上傳工具、P2P、FTP&&&好玩遊戲、休閒益智&&&影視編輯、轉檔、影音播放軟體&&&文書編輯、PDF、Office、字典&&&桌面美化管理、介面最佳化&&&檔案管理、壓縮軟體、備份還原&&&生活應用、其他未分類&&&看圖軟體、繪圖、相片處理&&&磁碟管理、光碟燒錄&&&系統工具&&&系統設定、功能調整&&&網路工具、遠端遙控、連線監控&&&防毒軟體、防火牆、病毒檢測&&&音樂編輯、轉檔、音樂播放軟體其他&&&Blog 部落格&&&WordPress 網站架設&&&硬體 3C&&&網頁編修、網站架設&&&虛擬主機, VPS, 伺服器租用好用網站、網路免費資源&&&KUSO、創意、網路小遊戲&&&免費字型、桌布下載&&&免費空間、貼圖傳檔&&&各種產生器、製造機&&&線上服務、實用工具&&&線上繪圖、轉檔、文書編輯&&&線上音樂、影視娛樂&&&語文學習、教育閱讀社群交友、社交網站&&&Facebook 臉書&&&Google Plus, Google+&&&Google 與其他 Google 應用&&&Plurk 噗浪&&&Twitter 微網誌&&&YouTube關魚專欄: 關於好台}