Maison > Article > interface Web > Une introduction au code graphique et textuel pour la mise en œuvre de l'effet d'animation de l'algorithme heuristique A* à huit chiffres sur les pages Web à l'aide de JavaScript

Une introduction au code graphique et textuel pour la mise en œuvre de l'effet d'animation de l'algorithme heuristique A* à huit chiffres sur les pages Web à l'aide de JavaScript

黄舟original: 2017-04-18 09:49:583295parcourir

Cet article présente principalement l'utilisation de JavaScript pour implémenter l'algorithme heuristique A* à huit chiffres effet d'animation sur les pages Web. Les amis qui en ont besoin peuvent se référer à

<.>Artificiel récent L'enseignant de la classe intelligente a organisé une expérience à huit chiffres. J'ai vu de nombreux algorithmes heuristiques A* à huit chiffres sur Internet, mais la plupart d'entre eux ont été implémentés sur la console en utilisant C ou C++, j'ai donc utilisé

js pour l'implémenter sur la page Web. J'en ai créé un similaire en .

Tout d'abord, le nombre à huit chiffres est une grille de neuf carrés, avec un espace à l'intérieur et les huit autres nombres correspondants de 1 à 8

Déplacez l'espace pour que le dernier

L'état soit ordonné, comme indiqué ci-dessous

L'algorithme heuristique fait référence à l'utilisation de l'heuristique

fonction pour supprimer les nœuds de solution qui ne respectent pas les règles lors de la résolution supprimée pour réduire l'espace de solution du problème.

L'algorithme A* est un algorithme heuristique qui utilise une fonction d'évaluation. Dans cet exemple, le nombre de grilles qui diffèrent entre l'état actuel du nœud et l'état final du nœud est utilisé pour évaluer la qualité du nœud, et le nœud supérieur est stocké et utilisé plus tard. Développez et supprimez les nœuds inférieurs.

Utilisez le Web pour y parvenir. Tout d'abord, ajoutez neuf zones de texte de saisie dans le code HTML, comme indiqué dans la figure. L'

image d'arrière-plan est une grille numérique

Le code de la page est

, puis utilisez javascript pour obtenir la valeur d'entrée et enregistrez-la dans le

<!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>

tableau bidimensionnel

où la classe Graph est utilisée Pour enregistrer les données liées à un nœud d'état :

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

Implémentez une fonction showGraph() pour afficher l'état à huit chiffres :

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

Utilisez la fonction d'évaluation évaluerGraph() pour évaluer le nœud actuel et le nœud cible. La valeur d'écart de

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

utilise la fonction moveGraph() pour déplacer et renvoyer un nouveau nœud :

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

et enfin la fonction

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

recherche

, en partant du nœud initial Rechercher vers le bas couche par couche jusqu'à atteindre le nœud cible, revenir au nœud enfant, et remonter couche par couche du nœud enfant au nœud parent pour trouver le chemin de la solution :

Enfin, appuyez sur les nœuds du chemin de la solution dans l'ordre. Dans la pile, un nœud apparaît toutes les secondes, s'affiche et forme une 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;
  }

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Déclaration：

Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Article précédent：Partage de code pour JavaScript afin d'implémenter la fonction de recherche frontale en temps réel (photo)Article suivant：Partage de code pour JavaScript afin d'implémenter la fonction de recherche frontale en temps réel (photo)

Articles Liés

Voir plus