这篇文章主要介绍了利用javascript在网页实现八数码启发式a*算法动画效果,需要的朋友可以参考下
最近人工智能课老师布置了一个八数码实验,网上看到很多八数码的启发式A*算法,但是大多数都是利用C或者C++在控制台实现的,于是我用js在网页中做了一个类似的。
首先八数码就是一个九宫格,其中有一个空格,其他八个对应数字1-8,

移动空格,使得最后状态为有序,如下图

启发式算法是指在求解时,利用启发函数将不符合规则的解节点去掉,从而缩小问题的解空间。
A*算法是利用评价函数的启发式算法,在本例中,利用当前节点状态与最终节点状态所不同的格子数来评估节点的优劣,将优越节点储存并在之后展开,将劣质节点抛弃。
利用web实现这一点首先在html中添加九个如图所示input文本框,背景图片为数码格

页面代码为
html>
<meta>
<title>八数码</title>
<style>
#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>
<p>
<input>
<input>
<input><br>
<input>
<input>
<input><br>
<input>
<input>
<input><br>
</p>
<button>求解</button>
然后利用javascript获取输入的值,并保存在二维数组中
var startArray=[[8,1,3],[0,2,4],[7,6,5]];//初始化八数码数组
//获取输入的初始状态
var cpic=1;
for(var i=0;i<n var evaluategraph showgraph><p>其中Graph类是用来来保存一个状态节点相关数据:</p>
<pre class="brush:js;">//节点类
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><p>利用评估函数evaluateGraph()评估当前节点与目标节点的差距值</p>
<pre class="brush:js;">//评估函数
function evaluateGraph(theGraph, endGraph){
var differ = 0;//差距数
for (var i = 0; i<n><p>利用moveGraph()函数来移动并返回一个新节点:</p>
<pre class="brush:js;">//移动数码组
function moveGraph(theGraph, direct){
var HasGetBlank = 0;//是否找到空格位置
var AbleMove = 1;//是否可移动
var i, j, t_i, t_j;
//查找空格坐标i,j
for (i = 0; i<n>= N)
AbleMove = 0;
break;
case 3://左
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><p>最后是<a href="http://www.php.cn/code/8331.html" target="_blank">搜索</a>函数,通过从初始节点开始一层层向下搜索,直到抵达目标节点,返回子节点,从子节点一层层向上回溯父节点,便可找到解路径:</p>
<pre class="brush:js;">//搜索路径
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 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);
}
Java免费学习笔记:立即使用
解锁 Java 大师之旅:从入门到精通的终极指南











