利用JavaScript在網(wǎng)頁實現(xiàn)八數(shù)碼啟發(fā)式A*算法動畫效果

更新時間：2017年04月16日 08:42:57 作者：theVicTory

這篇文章主要介紹了利用JavaScript在網(wǎng)頁實現(xiàn)八數(shù)碼啟發(fā)式A*算法動畫效果,需要的朋友可以參考下

最近人工智能課老師布置了一個八數(shù)碼實驗，網(wǎng)上看到很多八數(shù)碼的啟發(fā)式A*算法，但是大多數(shù)都是利用C或者C++在控制臺實現(xiàn)的，于是我用js在網(wǎng)頁中做了一個類似的。

首先八數(shù)碼就是一個九宮格，其中有一個空格，其他八個對應(yīng)數(shù)字1-8，

移動空格，使得最后狀態(tài)為有序，如下圖

啟發(fā)式算法是指在求解時，利用啟發(fā)函數(shù)將不符合規(guī)則的解節(jié)點去掉，從而縮小問題的解空間。

A*算法是利用評價函數(shù)的啟發(fā)式算法，在本例中，利用當(dāng)前節(jié)點狀態(tài)與最終節(jié)點狀態(tài)所不同的格子數(shù)來評估節(jié)點的優(yōu)劣，將優(yōu)越節(jié)點儲存并在之后展開，將劣質(zhì)節(jié)點拋棄。

利用web實現(xiàn)這一點首先在html中添加九個如圖所示input文本框，背景圖片為數(shù)碼格

頁面代碼為

<!DOCTYPE html>
<html lang="en">
<head>
 <meta charset="UTF-8">
 <title>八數(shù)碼</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獲取輸入的值，并保存在二維數(shù)組中

var startArray=[[8,1,3],[0,2,4],[7,6,5]];//初始化八數(shù)碼數(shù)組
   //獲取輸入的初始狀態(tài)
   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);//目標(biāo)節(jié)點
evaluateGraph(startGraph,endGraph);
showGraph(startGraph);

其中Graph類是用來來保存一個狀態(tài)節(jié)點相關(guān)數(shù)據(jù)：

//節(jié)點類
  var Graph = function(formData){
   this.form=formData;
   this.evalue=0;
   this.udirect=0;
   this.parent=null;
  };

實現(xiàn)一個showGraph()函數(shù)來顯示八數(shù)碼狀態(tài)：

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)";
    }
   }
  }

利用評估函數(shù)evaluateGraph()評估當(dāng)前節(jié)點與目標(biāo)節(jié)點的差距值

//評估函數(shù)
  function evaluateGraph(theGraph, endGraph){
   var differ = 0;//差距數(shù)
   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()函數(shù)來移動并返回一個新節(jié)點：

//移動數(shù)碼組
  function moveGraph(theGraph, direct){
   var HasGetBlank = 0;//是否找到空格位置
   var AbleMove = 1;//是否可移動
   var i, j, t_i, t_j;
   //查找空格坐標(biāo)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方向不能移動，返回原節(jié)點
   if (AbleMove == 0)
   {
    return theGraph;
   }
   //向Direct方向移動，生成新節(jié)點
   var ta=[[0,0,0],[0,0,0],[0,0,0]];
   var New_graph = new Graph(ta);
   for (var x = 0; x<N; x++)//復(fù)制數(shù)碼組
   {
    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];//交換空格和移動方向上的數(shù)字
   New_graph.form[t_i][t_j] = 0;
   return New_graph;
  }

最后是搜索函數(shù)，通過從初始節(jié)點開始一層層向下搜索，直到抵達(dá)目標(biāo)節(jié)點，返回子節(jié)點，從子節(jié)點一層層向上回溯父節(jié)點，便可找到解路徑：

//搜索路徑
  function Search(beginGraph, endGraph){
   var g1, g2, g;
   var Step = 0;//深度
   var Direct = 0;//方向
   var i;
   var front=-1,rear=-1;
   g1=beginGraph;//初始八數(shù)碼節(jié)點
   while (g1)//隊列不空,從close隊列中拿出一個節(jié)點
   {
    for (i = 1; i <= 4; i++){//分別從四個方向推導(dǎo)出新子節(jié)點
     Direct = i;
     if (Direct == g1.udirect)
      continue;//跳過屏蔽方向
     g2=moveGraph(g1,Direct);
     if (evaluateGraph(g2,g1)!=0){//數(shù)碼組是否可以移動
      evaluateGraph(g1,endGraph);
      evaluateGraph(g2,endGraph);//評價新的節(jié)點
      if (g2.evalue <= g1.evalue + 1)//利用評估值判斷是否為優(yōu)越節(jié)點
      { //若為優(yōu)，將g2的父節(jié)點指向g1
       g2.parent = g1;
       //設(shè)置屏蔽方向，防止往回推
       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;//把優(yōu)越節(jié)點放到close隊列
       if (g2.evalue == 0)//為0則搜索完成
       {
        g = g2;
        break;
       }
      }
      else{g2 = null;}//拋棄劣質(zhì)節(jié)點
     }
    }
    //搜索完成，繼續(xù)退出
    if (typeof g !== 'undefined')
    {
     if (g.evalue == 0)
     {
      break;
     }
    }
    Step++;//統(tǒng)計深度
    if (Step>Max_Step){
     alert("超過搜索深度！");
     break;}
    g1=Qu[++front];//從close隊列中拿出一個節(jié)點繼續(xù)下一輪展開
   }
   return g;
  }

最后將解路徑節(jié)點按順序壓入堆棧，每秒彈出一個節(jié)點，顯示，形成動畫：

var top=-1;
   var G;
   G = Search(startGraph, endGraph);
   //解序列存入堆棧
   var P=G;
   while (P != null)
   {
    top++;
    St[top] = P;
    P = P.parent;
   }
   //動畫執(zhí)行
   var si=setInterval(function () {
    if (top>-1)
    {
     showGraph(St[top]);
     top--;
    }else {
     clearInterval(si);
    }
   },1000);
  }

以上所述是小編給大家介紹的利用JavaScript在網(wǎng)頁實現(xiàn)八數(shù)碼啟發(fā)式A*算法動畫效果，希望對大家有所幫助，如果大家有任何疑問歡迎給我留言，小編會及時回復(fù)大家的，在此也非常感謝大家對腳本之家網(wǎng)站的支持！

您可能感興趣的文章: