利用JavaScript在网页实现八数码启发式A*算法动画效果
最近人工智能课老师布置了一个八数码实验，网上看到很多八数码的启发式A*算法，但是大多数都是利用C或者C++在控制台实现的，于是我用js在网页中做了一个类似的。
首先八数码就是一个九宫格，其中有一个空格，其他八个对应数字1-8，
移动空格，使得最后状态为有序，如下图
启发式算法是指在求解时，利用启发函数将不符合规则的解节点去掉，从而缩小问题的解空间。
A*算法是利用评价函数的启发式算法，在本例中，利用当前节点状态与最终节点状态所不同的格子数来评估节点的优劣，将优越节点储存并在之后展开，将劣质节点抛弃。
利用web实现这一点首先在html中添加九个如图所示input文本框，背景图片为数码格
页面代码为
<!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>
<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获取输入的值，并保存在二维数组中
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);
其中Graph类是用来来保存一个状态节点相关数据：
//节点类
var Graph = function(formData){
this.form=formData;
this.evalue=0;
this.udirect=0;
this.parent=null;
};
实现一个showGraph()函数来显示八数码状态：
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)";
}
}
}
利用评估函数evaluateGraph()评估当前节点与目标节点的差距值
//评估函数
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;
}
利用moveGraph()函数来移动并返回一个新节点：
//移动数码组
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;
}
最后是搜索函数，通过从初始节点开始一层层向下搜索，直到抵达目标节点，返回子节点，从子节点一层层向上回溯父节点，便可找到解路径：
//搜索路径
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;
}
最后将解路径节点按顺序压入堆栈，每秒弹出一个节点，显示，形成动画：
var top=-1;
var G;
G = Search(startGraph, endGraph);
//解序列存入堆栈
var P=G;
while (P != null)
{
top++;
St[top] = P;
P = P.parent;
}
//动画执行
var si=setInterval(function () {
if (top>-1)
{
showGraph(St[top]);
top--;
}else {
clearInterval(si);
}
},1000);
}
以上所述是小编给大家介绍的利用JavaScript在网页实现八数码启发式A*算法动画效果，希望对大家有所帮助，如果大家有任何疑问欢迎给我留言，小编会及时回复大家的，在此也非常感谢大家对我们网站的支持！
相关推荐
-
javascript解三阶幻方（九宫格）
谜题:三阶幻方, 试将1~9这9个不同整数填入一个3×3的表格,使得每行.每列以及每条对角线上的数字之和相同. 策略:穷举搜索.列出所有的整数填充方案,然后进行过滤. 亮点为递归函数getPermutation的设计,文章最后给出了几个非递归算法 // 递归算法,很巧妙,但太费资源 function getPermutation(arr) { if (arr.length == 1) { return [arr]; } var permutation = []; for (var i = 0;
-
javascript+canvas制作九宫格小程序
js核心代码 复制代码 代码如下: /* *canvasid:html canvas标签id *imageid:html img 标签id *gridcountX:x轴图片分割个数 *gridcountY:y轴图片分割个数 *gridspace:宫格空隙 *offsetX:x*y宫格相对canvas(0,0)X坐标偏移量 **offsetX:x*y宫格相对canvas(0,0)Y坐标偏移量 *isanimat:是否启用动画显示 */ function ImageGrid(can
-
js实现九宫格图片半透明渐显特效的方法
本文实例讲述了js实现九宫格图片半透明渐显特效的方法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: <html> <title>九宫格图片半透明渐显效果</title> <body> <STYLE type=text/css>.invisible { FILTER: alpha(opacity=0) } </STYLE> <SCRIPT language=JavaScript1.2> <!-- f
-
利用JavaScript在网页实现八数码启发式A*算法动画效果
最近人工智能课老师布置了一个八数码实验,网上看到很多八数码的启发式A*算法,但是大多数都是利用C或者C++在控制台实现的,于是我用js在网页中做了一个类似的. 首先八数码就是一个九宫格,其中有一个空格,其他八个对应数字1-8, 移动空格,使得最后状态为有序,如下图 启发式算法是指在求解时,利用启发函数将不符合规则的解节点去掉,从而缩小问题的解空间. A*算法是利用评价函数的启发式算法,在本例中,利用当前节点状态与最终节点状态所不同的格子数来评估节点的优劣,将优越节点储存并在之后展开,将劣质节点抛
-
JavaScript实现网页下拉列表的省市联动
大家好,今天我和大家分享网页中下拉列表的省市联动.在我们平常填写一些信息时就会有省市联动,就是在第一个下拉列表中选择我们所在的省,后面一个下拉列表显示该省的所有城市. 既然是省市联动,我们就不能把数据直接写到网页上,我们应该通过第一个下拉列表的省动态生成该省的所有城市.我们可以先定义一个JSON对象表示省,在对象中定义一个数组存储一个省中的所有城市(这里的城市也是JSON对象),最后用数组存储所有的省.我们可以利用JavaScript在网页上面添加选项option.联动这块我们可以为第一个下拉列
-
利用C++求解八数码问题实例代码
目录 问题描述: 内容提要: 实验步骤: 实验步骤 分析说明(包括核心代码及解释) 总结心得 问题描述: 八数码,在3×3的方格棋盘上,摆放着1到8这八个数码,有1个方格是空的,其初始状态如图1所示,要求对空格执行空格左移.空格右移.空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态.(注:图片给的例子无解.) 内容提要: 分别用广度优先搜索策略.深度优先搜索策略和启发式搜索算法(至少两种)求解八数码问题:分析估价函数对启发式搜索算法的影响:探究讨论各个搜索算法的特点. 实验步骤: 1.随
-
利用JavaScript实现简单的网页时钟
目录 一.效果展示 二.使用的技术 三.日期对象 1.指定时间 2.获取目前时间 三.源代码 前言: 今天带大家使用JavaScript定制一款网页时钟 一.效果展示 二.使用的技术 主要使用了js的日期对象,实现的时候先创建一个日期对象,并进行网页布局,对时间获取之后将时间填入对应的标签内.然后使用多线程实现时钟的变动. 三.日期对象 1.指定时间 代码如下: <script> //创建日期对象 d=new Date(); //设置年月日
-
JavaScript驾驭网页－获取网页元素
推荐阅读:JavaScript驾驭网页-DOM JavaScript驾驭网页-CSS与DOM 利用DOM分割HTML 利用JavaScript控制网页内容其实很像烹饪.只是不用收拾列羹剩肴,但也没有办法享受美味的成果. 不过,你将能完整网页内容的HTML构成要素:更重要的是,你将拥有替换网页成分的能力. JavaScript让你可以随心所欲地操控网页的HTML代码,从而打开各种有趣的机会之门,一切都是因为标准对象:DOM的存在 getElementById HTML标签都有一个"id"
-
JavaScript驾驭网页-CSS与DOM
推荐阅读:JavaScript驾驭网页-DOM DOM是种符合万维网标准的HTML操纵方式,它能比innerHTML特性达成更多操控功能 这里有HTML代码与CSS代码 <!doctype html> <html> <head> <meta charset="utf-8"> <title>无标题文档</title> <style type="text/css"> span.class
-
JavaScript针对网页节点的增删改查用法实例
本文实例讲述了JavaScript针对网页节点的增删改查用法.分享给大家供大家参考.具体分析如下: 一.基本概念 这部分也就是所谓的"HTML DOM",所谓HTML DOM也就是Web页面加载规则,是一个规则,也就是网页组成的基本公式. 也就是所有网页都必须按照:<html><body></body></html>--的规则编写,也按照这样的规则加载. 所谓的"网页节点",也叫"DOM节点"的通俗
-
基于JQuery和原生JavaScript实现网页定位导航特效
慕课网的一个小课程,练习了一遍,不足之处,欢迎指正(照片在本地,大家可以着重看代码哈): <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>爱淘气购物网-JQuery网页定位导航特效</title> <style> /*All tag*/ html, body, div, ul, li, img
-
javascript在网页中实现读取剪贴板粘贴截图功能
见某网站的输入框支持截屏粘贴的功能,觉得有点意思,于是将代码扒出来分享下. 可惜,目前仅有高版本的 Chrome 浏览器支持这样直接粘贴,其他浏览器目前为止还无法粘贴( IE11没测试过 ),当然这种增强型的用户体验功能有总比没有好. 输入框的结构代码: 复制代码 代码如下: <input type="text" id="testInput" /> 为输入框绑定粘贴事件: 复制代码 代码如下: var input = document.getElemen
-
JavaScript驾驭网页－DOM
一.DOM全称 文档对象模型(Document Object Model) 二.DOM是什么 DOM就是一个编程接口,就是一套API. DOM是针对HTML文档.XML等文档的一套API.就类似于JDBC是针对数据库的一套API一样. 三.DOM的用途 DOM 是用来访问或操作HTML文档.XHTML文档.XML文档中的节点元素. 现在基本上所有的浏览器都都执行了W3C发布的DOM规范,所以在浏览器上就可以用DOM的这些API. DOM提供对脚本友善的网页结构与内容的视图 DOM把网页视为节点构