这里有新鲜出炉的 Javascript 教程,程序狗速度看过来!
Javascript 是一种由 Netscape 的 LiveScript 发展而来的原型化继承的基于对象的动态类型的区分大小写的客户端脚本语言,主要目的是为了解决服务器端语言,比如 Perl,遗留的速度问题,为客户提供更流畅的浏览效果。
这篇文章主要介绍了利用 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 * 算法动画效果,希望对大家有所帮助,如果大家有任何疑问欢迎给我留言,小编会及时回复大家的,在此也非常感谢大家对 phperz 网站的支持!
(adsbygoogle = window.adsbygoogle || []).push({});
来源: http://www.phperz.com/article/17/0705/334030.html