Heim > Artikel > Web-Frontend > Eine Einführung in den Grafik- und Textcode, der JavaScript verwendet, um den achtstelligen heuristischen A*-Algorithmus-Animationseffekt auf Webseiten zu implementieren

Eine Einführung in den Grafik- und Textcode, der JavaScript verwendet, um den achtstelligen heuristischen A*-Algorithmus-Animationseffekt auf Webseiten zu implementieren

黄舟Original: 2017-04-18 09:49:583294Durchsuche

In diesem Artikel wird hauptsächlich die Verwendung von JavaScript zur Implementierung des achtstelligen heuristischen A*-Algorithmus Animationseffekt auf Webseiten vorgestellt

Kürzlich künstlich Der Lehrer in der Smart-Klasse hat ein achtstelliges Experiment arrangiert. Ich habe im Internet viele achtstellige heuristische A*-Algorithmen gesehen, aber die meisten davon wurden mit C oder C++ auf der Konsole implementiert, also habe ich js, um es auf der Webseite zu implementieren. Habe ein ähnliches in .

Zuerst ist die achtstellige Zahl ein Neunquadratraster mit einem Leerzeichen darin und den anderen acht entsprechenden Zahlen 1-8

Verschieben Sie den Raum so, dass der letzte

Der Status wie unten gezeigt geordnet ist

Der heuristische Algorithmus bezieht sich auf die Verwendung der Heuristik

Funktion zum Entfernen der Lösungsknoten, die beim Lösen nicht den Regeln entsprechen, um den Lösungsraum des Problems zu reduzieren.

Der A*-Algorithmus ist ein heuristischer Algorithmus, der eine Bewertungsfunktion verwendet. In diesem Beispiel wird die Anzahl der Gitter, die sich zwischen dem aktuellen Knotenstatus und dem endgültigen Knotenstatus unterscheiden, verwendet, um die Qualität des Knotens zu bewerten. und der übergeordnete Knoten wird gespeichert und später verwendet. Erweitern und verwerfen Sie untergeordnete Knoten.

Verwenden Sie dazu das Web. Fügen Sie zunächst neun Eingabetextfelder in den HTML-Code ein, wie in der Abbildung gezeigt. Das Hintergrundbild

Der Seitencode lautet

. Verwenden Sie dann Javascript, um den Eingabewert abzurufen und ihn im

zweidimensionalen Array

<!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>
 <p 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>
 </p>
 <button onclick="run()">求解</button>
</body>
</html>

zu speichern wo die Graph-Klasse verwendet wird. So speichern Sie Daten im Zusammenhang mit einem Statusknoten:

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=&#39;r&#39;+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);

Implementieren Sie eine showGraph()-Funktion, um den achtstelligen Status anzuzeigen:

//节点类
  var Graph = function(formData){
   this.form=formData;
   this.evalue=0;
   this.udirect=0;
   this.parent=null;
  };

Verwenden Sie die Auswertungsfunktion „evaluateGraph()“, um den aktuellen Knoten und den Zielknoten auszuwerten. Der Lückenwert von

function showGraph(graph) {
   var c=1;
   for(var i=0;i<N;i++){
    for(var j=0;j<N;j++){
     var s=&#39;r&#39;+c++;
     getId(s).style.backgroundImage="url(images/"+graph.form[i][j]+".png)";
    }
   }
  }

verwendet die Funktion „moveGraph()“, um einen neuen Knoten zu verschieben und zurückzugeben:

//评估函数
  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;
  }

und schließlich die

Suchfunktion

//移动数码组
  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;
  }

, indem Sie vom Anfangsknoten aus Schicht für Schicht nach unten suchen, bis Sie den Zielknoten erreichen, zum untergeordneten Knoten zurückkehren und dann Schicht für Schicht vom untergeordneten Knoten zum Zielknoten zurückkehren Übergeordneter Knoten, um den Lösungspfad zu finden:

Drücken Sie abschließend die Lösungspfadknoten der Reihe nach. Im Stapel erscheint jede Sekunde ein Knoten, wird angezeigt und bildet eine Animation:

//搜索路径
  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 !== &#39;undefined&#39;)
    {
     if (g.evalue == 0)
     {
      break;
     }
    }
    Step++;//统计深度
    if (Step>Max_Step){
     alert("超过搜索深度！");
     break;}
    g1=Qu[++front];//从close队列中拿出一个节点继续下一轮展开
   }
   return g;
  }

Das obige ist der detaillierte Inhalt vonEine Einführung in den Grafik- und Textcode, der JavaScript verwendet, um den achtstelligen heuristischen A*-Algorithmus-Animationseffekt auf Webseiten zu implementieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme：

Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Vorheriger Artikel：Code-Sharing für JavaScript zur Implementierung der Front-End-Echtzeit-Suchfunktion (Bild)Nächster Artikel：Code-Sharing für JavaScript zur Implementierung der Front-End-Echtzeit-Suchfunktion (Bild)

In Verbindung stehende Artikel

Mehr sehen