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>Copier après la connexion
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='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);Copier après la connexion
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;
};Copier après la connexion
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='r'+c++;
getId(s).style.backgroundImage="url(images/"+graph.form[i][j]+".png)";
}
}
}Copier après la connexion
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;
}Copier après la connexion
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;
}Copier après la connexion
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 !== 'undefined')
{
if (g.evalue == 0)
{
break;
}
}
Step++;//统计深度
if (Step>Max_Step){
alert("超过搜索深度！");
break;}
g1=Qu[++front];//从close队列中拿出一个节点继续下一轮展开
}
return g;
}Copier après la connexion
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!
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
