溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹了怎么使用JavaScript在網(wǎng)頁實現(xiàn)八數(shù)碼啟發(fā)式A*算法動畫效果，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。
首先八數(shù)碼就是一個九宮格，其中有一個空格，其他八個對應數(shù)字1-8，
移動空格，使得最后狀態(tài)為有序，如下圖
啟發(fā)式算法是指在求解時，利用啟發(fā)函數(shù)將不符合規(guī)則的解節(jié)點去掉，從而縮小問題的解空間。
A*算法是利用評價函數(shù)的啟發(fā)式算法，在本例中，利用當前節(jié)點狀態(tài)與最終節(jié)點狀態(tài)所不同的格子數(shù)來評估節(jié)點的優(yōu)劣，將優(yōu)越節(jié)點儲存并在之后展開，將劣質節(jié)點拋棄。
利用web實現(xiàn)這一點首先在html中添加九個如圖所示input文本框，背景圖片為數(shù)碼格
頁面代碼為
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>八數(shù)碼</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>
<div 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>
</div>
<button onclick="run()">求解</button>
</body>
</html>然后利用javascript獲取輸入的值，并保存在二維數(shù)組中
var startArray=[[8,1,3],[0,2,4],[7,6,5]];//初始化八數(shù)碼數(shù)組
//獲取輸入的初始狀態(tài)
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);//目標節(jié)點
evaluateGraph(startGraph,endGraph);
showGraph(startGraph);其中Graph類是用來來保存一個狀態(tài)節(jié)點相關數(shù)據(jù)：
//節(jié)點類
var Graph = function(formData){
this.form=formData;
this.evalue=0;
this.udirect=0;
this.parent=null;
};實現(xiàn)一個showGraph()函數(shù)來顯示八數(shù)碼狀態(tài)：
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)";
}
}
}利用評估函數(shù)evaluateGraph()評估當前節(jié)點與目標節(jié)點的差距值
//評估函數(shù)
function evaluateGraph(theGraph, endGraph){
var differ = 0;//差距數(shù)
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;
}利用moveGraph()函數(shù)來移動并返回一個新節(jié)點：
//移動數(shù)碼組
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方向不能移動，返回原節(jié)點
if (AbleMove == 0)
{
return theGraph;
}
//向Direct方向移動，生成新節(jié)點
var ta=[[0,0,0],[0,0,0],[0,0,0]];
var New_graph = new Graph(ta);
for (var x = 0; x<N; x++)//復制數(shù)碼組
{
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];//交換空格和移動方向上的數(shù)字
New_graph.form[t_i][t_j] = 0;
return New_graph;
}最后是搜索函數(shù)，通過從初始節(jié)點開始一層層向下搜索，直到抵達目標節(jié)點，返回子節(jié)點，從子節(jié)點一層層向上回溯父節(jié)點，便可找到解路徑：
//搜索路徑
function Search(beginGraph, endGraph){
var g1, g2, g;
var Step = 0;//深度
var Direct = 0;//方向
var i;
var front=-1,rear=-1;
g1=beginGraph;//初始八數(shù)碼節(jié)點
while (g1)//隊列不空,從close隊列中拿出一個節(jié)點
{
for (i = 1; i <= 4; i++){//分別從四個方向推導出新子節(jié)點
Direct = i;
if (Direct == g1.udirect)
continue;//跳過屏蔽方向
g2=moveGraph(g1,Direct);
if (evaluateGraph(g2,g1)!=0){//數(shù)碼組是否可以移動
evaluateGraph(g1,endGraph);
evaluateGraph(g2,endGraph);//評價新的節(jié)點
if (g2.evalue <= g1.evalue + 1)//利用評估值判斷是否為優(yōu)越節(jié)點
{ //若為優(yōu)，將g2的父節(jié)點指向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;//把優(yōu)越節(jié)點放到close隊列
if (g2.evalue == 0)//為0則搜索完成
{
g = g2;
break;
}
}
else{g2 = null;}//拋棄劣質節(jié)點
}
}
//搜索完成，繼續(xù)退出
if (typeof g !== 'undefined')
{
if (g.evalue == 0)
{
break;
}
}
Step++;//統(tǒng)計深度
if (Step>Max_Step){
alert("超過搜索深度！");
break;}
g1=Qu[++front];//從close隊列中拿出一個節(jié)點繼續(xù)下一輪展開
}
return g;
}最后將解路徑節(jié)點按順序壓入堆棧，每秒彈出一個節(jié)點，顯示，形成動畫：
var top=-1;
var G;
G = Search(startGraph, endGraph);
//解序列存入堆棧
var P=G;
while (P != null)
{
top++;
St[top] = P;
P = P.parent;
}
//動畫執(zhí)行
var si=setInterval(function () {
if (top>-1)
{
showGraph(St[top]);
top--;
}else {
clearInterval(si);
}
},1000);
}感謝你能夠認真閱讀完這篇文章，希望小編分享的“怎么使用JavaScript在網(wǎng)頁實現(xiàn)八數(shù)碼啟發(fā)式A*算法動畫效果”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業(yè)資訊頻道，更多相關知識等著你來學習!
免責聲明：本站發(fā)布的內容（圖片、視頻和文字）以原創(chuàng)、轉載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權內容。
