利用JavaScript在網(wǎng)頁(yè)實(shí)現(xiàn)八數(shù)碼啟發(fā)式A*算法動(dòng)畫效果
最近人工智能課老師布置了一個(gè)八數(shù)碼實(shí)驗(yàn)，網(wǎng)上看到很多八數(shù)碼的啟發(fā)式A*算法，但是大多數(shù)都是利用C或者C++在控制臺(tái)實(shí)現(xiàn)的，于是我用js在網(wǎng)頁(yè)中做了一個(gè)類似的。
首先八數(shù)碼就是一個(gè)九宮格，其中有一個(gè)空格，其他八個(gè)對(duì)應(yīng)數(shù)字1-8，
移動(dòng)空格，使得最后狀態(tài)為有序，如下圖
啟發(fā)式算法是指在求解時(shí)，利用啟發(fā)函數(shù)將不符合規(guī)則的解節(jié)點(diǎn)去掉，從而縮小問(wèn)題的解空間。
A*算法是利用評(píng)價(jià)函數(shù)的啟發(fā)式算法，在本例中，利用當(dāng)前節(jié)點(diǎn)狀態(tài)與最終節(jié)點(diǎn)狀態(tài)所不同的格子數(shù)來(lái)評(píng)估節(jié)點(diǎn)的優(yōu)劣，將優(yōu)越節(jié)點(diǎn)儲(chǔ)存并在之后展開，將劣質(zhì)節(jié)點(diǎn)拋棄。
利用web實(shí)現(xiàn)這一點(diǎn)首先在html中添加九個(gè)如圖所示input文本框，背景圖片為數(shù)碼格
頁(yè)面代碼為
<!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);//目標(biāo)節(jié)點(diǎn)
evaluateGraph(startGraph,endGraph);
showGraph(startGraph);
其中Graph類是用來(lái)來(lái)保存一個(gè)狀態(tài)節(jié)點(diǎn)相關(guān)數(shù)據(jù)：
//節(jié)點(diǎn)類
var Graph = function(formData){
this.form=formData;
this.evalue=0;
this.udirect=0;
this.parent=null;
};
實(shí)現(xiàn)一個(gè)showGraph()函數(shù)來(lái)顯示八數(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)";
}
}
}
利用評(píng)估函數(shù)evaluateGraph()評(píng)估當(dāng)前節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的差距值
//評(píng)估函數(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ù)來(lái)移動(dòng)并返回一個(gè)新節(jié)點(diǎn)：
//移動(dòng)數(shù)碼組
function moveGraph(theGraph, direct){
var HasGetBlank = 0;//是否找到空格位置
var AbleMove = 1;//是否可移動(dòng)
var i, j, t_i, t_j;
//查找空格坐標(biāo)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;
//移動(dòng)空格
switch (direct)
{
case 1://上
t_i--;
if (t_i<0)
AbleMove = 0;//移動(dòng)超過(guò)邊界
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方向不能移動(dòng)，返回原節(jié)點(diǎn)
if (AbleMove == 0)
{
return theGraph;
}
//向Direct方向移動(dòng)，生成新節(jié)點(diǎn)
var ta=[[0,0,0],[0,0,0],[0,0,0]];
var New_graph = new Graph(ta);
for (var x = 0; x<N; x++)//復(fù)制數(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];//交換空格和移動(dòng)方向上的數(shù)字
New_graph.form[t_i][t_j] = 0;
return New_graph;
}
最后是搜索函數(shù)，通過(guò)從初始節(jié)點(diǎn)開始一層層向下搜索，直到抵達(dá)目標(biāo)節(jié)點(diǎn)，返回子節(jié)點(diǎn)，從子節(jié)點(diǎn)一層層向上回溯父節(jié)點(diǎn)，便可找到解路徑：
//搜索路徑
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é)點(diǎn)
while (g1)//隊(duì)列不空,從close隊(duì)列中拿出一個(gè)節(jié)點(diǎn)
{
for (i = 1; i <= 4; i++){//分別從四個(gè)方向推導(dǎo)出新子節(jié)點(diǎn)
Direct = i;
if (Direct == g1.udirect)
continue;//跳過(guò)屏蔽方向
g2=moveGraph(g1,Direct);
if (evaluateGraph(g2,g1)!=0){//數(shù)碼組是否可以移動(dòng)
evaluateGraph(g1,endGraph);
evaluateGraph(g2,endGraph);//評(píng)價(jià)新的節(jié)點(diǎn)
if (g2.evalue <= g1.evalue + 1)//利用評(píng)估值判斷是否為優(yōu)越節(jié)點(diǎn)
{ //若為優(yōu)，將g2的父節(jié)點(diǎn)指向g1
g2.parent = g1;
//設(shè)置屏蔽方向，防止往回推
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é)點(diǎn)放到close隊(duì)列
if (g2.evalue == 0)//為0則搜索完成
{
g = g2;
break;
}
}
else{g2 = null;}//拋棄劣質(zhì)節(jié)點(diǎn)
}
}
//搜索完成，繼續(xù)退出
if (typeof g !== 'undefined')
{
if (g.evalue == 0)
{
break;
}
}
Step++;//統(tǒng)計(jì)深度
if (Step>Max_Step){
alert("超過(guò)搜索深度！");
break;}
g1=Qu[++front];//從close隊(duì)列中拿出一個(gè)節(jié)點(diǎn)繼續(xù)下一輪展開
}
return g;
}
最后將解路徑節(jié)點(diǎn)按順序壓入堆棧，每秒彈出一個(gè)節(jié)點(diǎn)，顯示，形成動(dòng)畫：
var top=-1;
var G;
G = Search(startGraph, endGraph);
//解序列存入堆棧
var P=G;
while (P != null)
{
top++;
St[top] = P;
P = P.parent;
}
//動(dòng)畫執(zhí)行
var si=setInterval(function () {
if (top>-1)
{
showGraph(St[top]);
top--;
}else {
clearInterval(si);
}
},1000);
}
以上所述是小編給大家介紹的利用JavaScript在網(wǎng)頁(yè)實(shí)現(xiàn)八數(shù)碼啟發(fā)式A*算法動(dòng)畫效果，希望對(duì)大家有所幫助，如果大家有任何疑問(wèn)歡迎給我留言，小編會(huì)及時(shí)回復(fù)大家的，在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持！
相關(guān)文章
IE中g(shù)etElementsByName()對(duì)有些元素?zé)o效的解決方案
這篇文章主要介紹了IE中g(shù)etElementsByName()對(duì)有些元素?zé)o效的解決方案,很簡(jiǎn)單，很實(shí)用，需要的朋友可以參考下2014-09-09
JavaScript中的noscript元素屬性位置及作用介紹
Javascript插入到XHTML中要使用script元素，使用這個(gè)元素可以把Javascript嵌入到XHTML頁(yè)面中，讓腳本與標(biāo)記混合在一起，感興趣的朋友可以了解下2013-04-04
微信小程序?qū)W習(xí)總結(jié)（四）事件與冒泡實(shí)例分析
這篇文章主要介紹了微信小程序?qū)W習(xí)總結(jié)（四）事件與冒泡,結(jié)合實(shí)例形式分析了微信小程序事件、冒泡、數(shù)據(jù)獲取相關(guān)機(jī)制、原理與操作注意事項(xiàng),需要的朋友可以參考下2020-06-06
在JavaScript中數(shù)組是一種常用的數(shù)據(jù)結(jié)構(gòu),用于存儲(chǔ)多個(gè)值,這篇文章主要給大家總結(jié)介紹了關(guān)于JS中截取數(shù)組的幾種方法,文中通過(guò)代碼介紹的非常詳細(xì),需要的朋友可以參考下2024-05-05
本篇文章主要是對(duì)JS獲取地址欄參數(shù)的幾種方法進(jìn)行了介紹，需要的朋友可以過(guò)來(lái)參考下，希望對(duì)大家有所幫助2014-02-02
這篇文章主要介紹了微信小程序?qū)崿F(xiàn)固定表頭、列表格組件的相關(guān)資料,這個(gè)功能在我們進(jìn)行小程序開發(fā)的時(shí)候非常實(shí)用,文章通過(guò)示例代碼介紹的非常詳細(xì),需要的朋友可以參考下2021-07-07
JavaScript設(shè)計(jì)模式之裝飾者模式介紹
這篇文章主要介紹了JavaScript設(shè)計(jì)模式之裝飾者模式介紹,通一個(gè)類來(lái)動(dòng)態(tài)的對(duì)另一個(gè)類的功能對(duì)象進(jìn)行前或后的修飾，給它輔加一些額外的功能; 這是對(duì)一個(gè)類對(duì)象功能的裝飾，裝飾的類跟被裝飾的類，要求擁有相同的訪問(wèn)接口方法（功能）,需要的朋友可以參考下2014-12-12
本篇文章主要講述幾種前端JS檢測(cè)開發(fā)者工具是否打開的方法,需要的朋友可以參考下2020-10-10
微信小程序?qū)D片進(jìn)行canvas壓縮的方法示例詳解
這篇文章主要給大家介紹了關(guān)于微信小程序?qū)D片進(jìn)行canvas壓縮的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11
超越Jquery_01_isPlainObject分析與重構(gòu)
isPlainObject是Jquery1.4后提供的新方法,用于判斷對(duì)象是否是純粹的對(duì)象（通過(guò) {} 或者 new Object 創(chuàng)建的）。2010-10-10