利用JavaScript在网页实现八数码启发式A*算法动画效果的图文代码介绍-js教程-PHP中文网

首页

web前端

js教程

利用JavaScript在网页实现八数码启发式A*算法动画效果的图文代码介绍

黄舟

Apr 18, 2017 am 09:49 AM

这篇文章主要介绍了利用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>
 <p 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>
 </p>
 <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=&#39;r&#39;+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=&#39;r&#39;+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 !== &#39;undefined&#39;)
    {
     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*算法动画效果的图文代码介绍的详细内容。更多信息请关注PHP中文网其他相关文章！

本站声明

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

热AI工具

Undresser.AI Undress

人工智能驱动的应用程序，用于创建逼真的裸体照片

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

免费脱衣服图片

Clothoff.io

AI脱衣机

Video Face Swap

使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸！

显示更多

热工具

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

中文版，非常好用

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

显示更多

热门话题

gmail邮箱登陆入口在哪里

7678

CakePHP 教程

1393

C# 教程

1207

steam的账户名称是什么格式

win11激活密钥永久

显示更多

Related knowledge

如何使用WebSocket和JavaScript实现在线语音识别系统 Dec 17, 2023 pm 02:54 PM

如何使用WebSocket和JavaScript实现在线语音识别系统引言：随着科技的不断发展，语音识别技术已经成为了人工智能领域的重要组成部分。而基于WebSocket和JavaScript实现的在线语音识别系统，具备了低延迟、实时性和跨平台的特点，成为了一种被广泛应用的解决方案。本文将介绍如何使用WebSocket和JavaScript来实现在线语音识别系

WebSocket与JavaScript：实现实时监控系统的关键技术 Dec 17, 2023 pm 05:30 PM

WebSocket与JavaScript：实现实时监控系统的关键技术引言：随着互联网技术的快速发展，实时监控系统在各个领域中得到了广泛的应用。而实现实时监控的关键技术之一就是WebSocket与JavaScript的结合使用。本文将介绍WebSocket与JavaScript在实时监控系统中的应用，并给出代码示例，详细解释其实现原理。一、WebSocket技

如何利用JavaScript和WebSocket实现实时在线点餐系统 Dec 17, 2023 pm 12:09 PM

如何利用JavaScript和WebSocket实现实时在线点餐系统介绍：随着互联网的普及和技术的进步，越来越多的餐厅开始提供在线点餐服务。为了实现实时在线点餐系统，我们可以利用JavaScript和WebSocket技术。WebSocket是一种基于TCP协议的全双工通信协议，可以实现客户端与服务器的实时双向通信。在实时在线点餐系统中，当用户选择菜品并下单

如何使用WebSocket和JavaScript实现在线预约系统 Dec 17, 2023 am 09:39 AM

如何使用WebSocket和JavaScript实现在线预约系统在当今数字化的时代，越来越多的业务和服务都需要提供在线预约功能。而实现一个高效、实时的在线预约系统是至关重要的。本文将介绍如何使用WebSocket和JavaScript来实现一个在线预约系统，并提供具体的代码示例。一、什么是WebSocketWebSocket是一种在单个TCP连接上进行全双工

JavaScript和WebSocket：打造高效的实时天气预报系统 Dec 17, 2023 pm 05:13 PM

JavaScript和WebSocket：打造高效的实时天气预报系统引言：如今，天气预报的准确性对于日常生活以及决策制定具有重要意义。随着技术的发展，我们可以通过实时获取天气数据来提供更准确可靠的天气预报。在本文中，我们将学习如何使用JavaScript和WebSocket技术，来构建一个高效的实时天气预报系统。本文将通过具体的代码示例来展示实现的过程。We

简易JavaScript教程：获取HTTP状态码的方法 Jan 05, 2024 pm 06:08 PM

JavaScript教程：如何获取HTTP状态码，需要具体代码示例前言：在Web开发中，经常会涉及到与服务器进行数据交互的场景。在与服务器进行通信时，我们经常需要获取返回的HTTP状态码来判断操作是否成功，根据不同的状态码来进行相应的处理。本篇文章将教你如何使用JavaScript获取HTTP状态码，并提供一些实用的代码示例。使用XMLHttpRequest

javascript中如何使用insertBefore Nov 24, 2023 am 11:56 AM

用法：在JavaScript中，insertBefore()方法用于在DOM树中插入一个新的节点。这个方法需要两个参数：要插入的新节点和参考节点（即新节点将要被插入的位置的节点）。

JavaScript和WebSocket：打造高效的实时图像处理系统 Dec 17, 2023 am 08:41 AM

JavaScript是一种广泛应用于Web开发的编程语言，而WebSocket则是一种用于实时通信的网络协议。结合二者的强大功能，我们可以打造一个高效的实时图像处理系统。本文将介绍如何利用JavaScript和WebSocket来实现这个系统，并提供具体的代码示例。首先，我们需要明确实时图像处理系统的需求和目标。假设我们有一个摄像头设备，可以采集实时的图像数

See all articles

利用JavaScript在网页实现八数码启发式A*算法动画效果的图文代码介绍

热AI工具

Undresser.AI Undress

AI Clothes Remover

Undress AI Tool

Clothoff.io

Video Face Swap

热门文章

热工具

记事本++7.3.1

SublimeText3汉化版

禅工作室 13.0.1

Dreamweaver CS6

SublimeText3 Mac版

热门话题