この記事では主に JavaScript を使用して 8 桁のヒューリスティック A* アルゴリズム アニメーション 効果を Web ページに実装する方法を紹介します。必要な友達はそれを参照してください
最近、人工知能のクラスの先生が手配しました。 8 桁の実験で、8 桁のヒューリスティック A* アルゴリズムをオンラインでたくさん見ましたが、そのほとんどは C または C++ を使用してコンソールで実装されているため、js を使用して同様のものを作成しました。ウェブページ。
まず、8 つの数字は 9 正方形のグリッドで、その中に 1 つのスペースがあり、他の 8 つの対応する 1 ~ 8 の数字は、最終的な
状態が順序付けされるようにスペースを移動します。以下に示す
ヒューリスティックアルゴリズム 解決する際に、ヒューリスティック関数
を使用してルールに従わない解ノードを削除し、それによって問題の解空間を減らすことを意味します。A* アルゴリズムは、評価関数を使用するヒューリスティック アルゴリズムです。この例では、現在のノードの状態と最終的なノードの状態の間で異なるグリッドの数を使用して、上位ノードが保存されます。後で拡張され、下位ノードは保存され、後でノードが破棄されます。
これを実現するには、まず、HTML の図に示すように 9 つの入力テキスト ボックスを追加します。画像 はデジタル グリッドです
次に、JavaScript を使用します。入力値を取得して保存するには、二次元配列
<!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>
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);
8 桁のステータスを表示する showGraph() 関数を実装します。 :
//节点类 var Graph = function(formData){ this.form=formData; this.evalue=0; this.udirect=0; this.parent=null; };
評価関数evaluateGraph()を使用して、現在のノードとターゲットノード間のギャップ値を評価します。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)";
}
}
}
//评估函数 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; }
最後に、
search関数は、最初のノードからターゲット ノードに到達するまで層ごとに下方向に検索し、子ノードから層ごとに親ノードまで遡って解決パスを見つけます。
//移动数码组 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; }
最後に、プッシュします。ソリューション パス ノードを順番にスタックに追加し、1 秒ごとに 1 つのノードをポップアップして表示し、アニメーションを形成します:
//搜索路径 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; }
以上がJavaScript を使用して Web ページに 8 桁のヒューリスティック A* アルゴリズムのアニメーション効果を実装するためのグラフィック コードとテキスト コードの紹介の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。