最近人工智能課老師布置了一個八數碼實驗，網上看到很多八數碼的啟發式A*算法，但是大多數都是利用C或者C++在控制臺實現的，于是我用js在網頁中做了一個類似的。
首先八數碼就是一個九宮格，其中有一個空格，其他八個對應數字1-8，
移動空格，使得最后狀態為有序，如下圖
啟發式算法是指在求解時，利用啟發函數將不符合規則的解節點去掉，從而縮小問題的解空間。
A*算法是利用評價函數的啟發式算法，在本例中，利用當前節點狀態與最終節點狀態所不同的格子數來評估節點的優劣，將優越節點儲存并在之后展開，將劣質節點拋棄。
利用web實現這一點首先在html中添加九個如圖所示input文本框，背景圖片為數碼格
頁面代碼為
<!DOCTYPE html><html lang="en"><head> <meta charset="UTF-8"> <title>八數碼</title> <style type="text/css"> #result input{ display: inline-block; font-family:"微軟雅黑"; font-size: 60px; font-weight: 900; text-align: center; width:100px; height:100px; background:url(images/0.png); background-size:cover; }</style></head><body> <div id="result"> <input type="text" id="r1"> <input type="text" id="r2"> <input type="text" id="r3"><br> <input type="text" id="r4"> <input type="text" id="r5"> <input type="text" id="r6"><br> <input type="text" id="r7"> <input type="text" id="r8"> <input type="text" id="r9"><br> </div> <button onclick="run()">求解</button></body></html>然后利用javascript獲取輸入的值，并保存在二維數組中
var startArray=[[8,1,3],[0,2,4],[7,6,5]];//初始化八數碼數組 //獲取輸入的初始狀態 var cpic=1; for(var i=0;i<N;i++){ for(var j=0;j<N;j++){ var rid='r'+cpic++; var inputValue=getId(rid).value; if(inputValue==""){inputValue=0;} startArray[i][j]=parseInt(inputValue); getId(rid).value=""; } }var startGraph=new Graph(startArray);var endArray=[[ 1,2,3],[ 8,0,4 ],[ 7,6,5 ]];var endGraph=new Graph(endArray);//目標節點evaluateGraph(startGraph,endGraph);showGraph(startGraph);其中Graph類是用來來保存一個狀態節點相關數據：
//節點類 var Graph = function(formData){ this.form=formData; this.evalue=0; this.udirect=0; this.parent=null; };實現一個showGraph()函數來顯示八數碼狀態：
function showGraph(graph) { var c=1; for(var i=0;i<N;i++){ for(var j=0;j<N;j++){ var s='r'+c++; getId(s).style.backgroundImage="url(images/"+graph.form[i][j]+".png)"; } } }利用評估函數evaluateGraph()評估當前節點與目標節點的差距值
//評估函數 function evaluateGraph(theGraph, endGraph){ var differ = 0;//差距數 for (var i = 0; i<N; i++) { for (var j = 0; j<N; j++) { if (theGraph.form[i][j] != endGraph.form[i][j]){differ++;} } } theGraph.evalue = differ; return differ; }利用moveGraph()函數來移動并返回一個新節點：
//移動數碼組 function moveGraph(theGraph, direct){ var HasGetBlank = 0;//是否找到空格位置 var AbleMove = 1;//是否可移動 var i, j, t_i, t_j; //查找空格坐標i,j for (i = 0; i<N; i++) { for (j = 0; j<N; j++) { if (theGraph.form[i][j] == 0) { HasGetBlank = 1; break; } } if (HasGetBlank == 1) break; } t_i = i; t_j = j; //移動空格 switch (direct) { case 1://上 t_i--; if (t_i<0) AbleMove = 0;//移動超過邊界 break; case 2://下 t_i++; if (t_i >= N) AbleMove = 0; break; case 3://左 t_j--; if (t_j<0) AbleMove = 0; break; case 4://右 t_j++; if (t_j >= N) AbleMove = 0; break; } //Direct方向不能移動，返回原節點 if (AbleMove == 0) { return theGraph; } //向Direct方向移動，生成新節點 var ta=[[0,0,0],[0,0,0],[0,0,0]]; var New_graph = new Graph(ta); for (var x = 0; x<N; x++)//復制數碼組 { for (var y = 0; y<N; y++) { New_graph.form[x][y] = theGraph.form[x][y]; } } //交換 New_graph.form[i][j] = New_graph.form[t_i][t_j];//交換空格和移動方向上的數字 New_graph.form[t_i][t_j] = 0; return New_graph; }最后是搜索函數，通過從初始節點開始一層層向下搜索，直到抵達目標節點，返回子節點，從子節點一層層向上回溯父節點，便可找到解路徑：
//搜索路徑 function Search(beginGraph, endGraph){ var g1, g2, g; var Step = 0;//深度 var Direct = 0;//方向 var i; var front=-1,rear=-1; g1=beginGraph;//初始八數碼節點 while (g1)//隊列不空,從close隊列中拿出一個節點 { for (i = 1; i <= 4; i++){//分別從四個方向推導出新子節點 Direct = i; if (Direct == g1.udirect) continue;//跳過屏蔽方向 g2=moveGraph(g1,Direct); if (evaluateGraph(g2,g1)!=0){//數碼組是否可以移動 evaluateGraph(g1,endGraph); evaluateGraph(g2,endGraph);//評價新的節點 if (g2.evalue <= g1.evalue + 1)//利用評估值判斷是否為優越節點 { //若為優，將g2的父節點指向g1 g2.parent = g1; //設置屏蔽方向，防止往回推 switch (Direct){ case 1://上 g2.udirect = 2; break; case 2://下 g2.udirect = 1; break; case 3://左 g2.udirect = 4; break; case 4://右 g2.udirect = 3; break; } Qu[++rear]=g2;//把優越節點放到close隊列 if (g2.evalue == 0)//為0則搜索完成 { g = g2; break; } } else{g2 = null;}//拋棄劣質節點 } } //搜索完成，繼續退出 if (typeof g !== 'undefined') { if (g.evalue == 0) { break; } } Step++;//統計深度 if (Step>Max_Step){ alert("超過搜索深度！"); break;} g1=Qu[++front];//從close隊列中拿出一個節點繼續下一輪展開 } return g; }最后將解路徑節點按順序壓入堆棧，每秒彈出一個節點，顯示，形成動畫：
var top=-1; var G; G = Search(startGraph, endGraph); //解序列存入堆棧 var P=G; while (P != null) { top++; St[top] = P; P = P.parent; } //動畫執行 var si=setInterval(function () { if (top>-1) { showGraph(St[top]); top--; }else { clearInterval(si); } },1000); }以上所述是小編給大家介紹的利用JavaScript在網頁實現八數碼啟發式A*算法動畫效果，希望對大家有所幫助，如果大家有任何疑問歡迎給我留言，小編會及時回復大家的，在此也非常感謝大家對武林網網站的支持！
新聞熱點
疑難解答
