利用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)

熱門話題

Java教學

1666

CakePHP 教程

1425

Laravel 教程

1327

PHP教程

1273

C# 教程

1253

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版

熱門話題