ホームページ > 記事 > ウェブフロントエンド > JavaScript を使用して Web ページに 8 桁のヒューリスティック A* アルゴリズムのアニメーション効果を実装するためのグラフィック コードとテキスト コードの紹介
JavaScript を使用して Web ページに 8 桁のヒューリスティック A* アルゴリズムのアニメーション効果を実装するためのグラフィック コードとテキスト コードの紹介
- 黄舟オリジナル
- 2017-04-18 09:49:583253ブラウズ
この記事では主に 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>
で、Graph クラスを使用してステータス ノードに関連するデータを保存します。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)";
}
}
}はmoveGraph()関数を使用して、新しいノードを移動して返します:
//评估函数
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 サイトの他の関連記事を参照してください。