利用JavaScript在网页实现八数码启发式A*算法动画效果的图文代码介绍
这篇文章主要介绍了利用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='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);
}Atas ialah kandungan terperinci 利用JavaScript在网页实现八数码启发式A*算法动画效果的图文代码介绍. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!
Alat AI Hot
Undresser.AI Undress
Apl berkuasa AI untuk mencipta foto bogel yang realistik
AI Clothes Remover
Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.
Undress AI Tool
Gambar buka pakaian secara percuma
Clothoff.io
Penyingkiran pakaian AI
Video Face Swap
Tukar muka dalam mana-mana video dengan mudah menggunakan alat tukar muka AI percuma kami!
Artikel Panas
Alat panas
Notepad++7.3.1
Editor kod yang mudah digunakan dan percuma
SublimeText3 versi Cina
Versi Cina, sangat mudah digunakan
Hantar Studio 13.0.1
Persekitaran pembangunan bersepadu PHP yang berkuasa
Dreamweaver CS6
Alat pembangunan web visual
SublimeText3 versi Mac
Perisian penyuntingan kod peringkat Tuhan (SublimeText3)
Topik panas
1393
52
1205
24
Bagaimana untuk melaksanakan sistem pengecaman pertuturan dalam talian menggunakan WebSocket dan JavaScript
Dec 17, 2023 pm 02:54 PM
Cara menggunakan WebSocket dan JavaScript untuk melaksanakan sistem pengecaman pertuturan dalam talian Pengenalan: Dengan perkembangan teknologi yang berterusan, teknologi pengecaman pertuturan telah menjadi bahagian penting dalam bidang kecerdasan buatan. Sistem pengecaman pertuturan dalam talian berdasarkan WebSocket dan JavaScript mempunyai ciri kependaman rendah, masa nyata dan platform merentas, dan telah menjadi penyelesaian yang digunakan secara meluas. Artikel ini akan memperkenalkan cara menggunakan WebSocket dan JavaScript untuk melaksanakan sistem pengecaman pertuturan dalam talian.
WebSocket dan JavaScript: teknologi utama untuk melaksanakan sistem pemantauan masa nyata
Dec 17, 2023 pm 05:30 PM
WebSocket dan JavaScript: Teknologi utama untuk merealisasikan sistem pemantauan masa nyata Pengenalan: Dengan perkembangan pesat teknologi Internet, sistem pemantauan masa nyata telah digunakan secara meluas dalam pelbagai bidang. Salah satu teknologi utama untuk mencapai pemantauan masa nyata ialah gabungan WebSocket dan JavaScript. Artikel ini akan memperkenalkan aplikasi WebSocket dan JavaScript dalam sistem pemantauan masa nyata, memberikan contoh kod dan menerangkan prinsip pelaksanaannya secara terperinci. 1. Teknologi WebSocket
Cara menggunakan JavaScript dan WebSocket untuk melaksanakan sistem pesanan dalam talian masa nyata
Dec 17, 2023 pm 12:09 PM
Pengenalan kepada cara menggunakan JavaScript dan WebSocket untuk melaksanakan sistem pesanan dalam talian masa nyata: Dengan populariti Internet dan kemajuan teknologi, semakin banyak restoran telah mula menyediakan perkhidmatan pesanan dalam talian. Untuk melaksanakan sistem pesanan dalam talian masa nyata, kami boleh menggunakan teknologi JavaScript dan WebSocket. WebSocket ialah protokol komunikasi dupleks penuh berdasarkan protokol TCP, yang boleh merealisasikan komunikasi dua hala masa nyata antara pelanggan dan pelayan. Dalam sistem pesanan dalam talian masa nyata, apabila pengguna memilih hidangan dan membuat pesanan
Bagaimana untuk melaksanakan sistem tempahan dalam talian menggunakan WebSocket dan JavaScript
Dec 17, 2023 am 09:39 AM
Cara menggunakan WebSocket dan JavaScript untuk melaksanakan sistem tempahan dalam talian Dalam era digital hari ini, semakin banyak perniagaan dan perkhidmatan perlu menyediakan fungsi tempahan dalam talian. Adalah penting untuk melaksanakan sistem tempahan dalam talian yang cekap dan masa nyata. Artikel ini akan memperkenalkan cara menggunakan WebSocket dan JavaScript untuk melaksanakan sistem tempahan dalam talian dan memberikan contoh kod khusus. 1. Apakah itu WebSocket? WebSocket ialah kaedah dupleks penuh pada sambungan TCP tunggal.
JavaScript dan WebSocket: Membina sistem ramalan cuaca masa nyata yang cekap
Dec 17, 2023 pm 05:13 PM
JavaScript dan WebSocket: Membina sistem ramalan cuaca masa nyata yang cekap Pengenalan: Hari ini, ketepatan ramalan cuaca sangat penting kepada kehidupan harian dan membuat keputusan. Apabila teknologi berkembang, kami boleh menyediakan ramalan cuaca yang lebih tepat dan boleh dipercayai dengan mendapatkan data cuaca dalam masa nyata. Dalam artikel ini, kita akan mempelajari cara menggunakan teknologi JavaScript dan WebSocket untuk membina sistem ramalan cuaca masa nyata yang cekap. Artikel ini akan menunjukkan proses pelaksanaan melalui contoh kod tertentu. Kami
Tutorial JavaScript Mudah: Cara Mendapatkan Kod Status HTTP
Jan 05, 2024 pm 06:08 PM
Tutorial JavaScript: Bagaimana untuk mendapatkan kod status HTTP, contoh kod khusus diperlukan: Dalam pembangunan web, interaksi data dengan pelayan sering terlibat. Apabila berkomunikasi dengan pelayan, kami selalunya perlu mendapatkan kod status HTTP yang dikembalikan untuk menentukan sama ada operasi itu berjaya dan melaksanakan pemprosesan yang sepadan berdasarkan kod status yang berbeza. Artikel ini akan mengajar anda cara menggunakan JavaScript untuk mendapatkan kod status HTTP dan menyediakan beberapa contoh kod praktikal. Menggunakan XMLHttpRequest
Bagaimana untuk menggunakan insertBefore dalam javascript
Nov 24, 2023 am 11:56 AM
Penggunaan: Dalam JavaScript, kaedah insertBefore() digunakan untuk memasukkan nod baharu dalam pepohon DOM. Kaedah ini memerlukan dua parameter: nod baharu untuk dimasukkan dan nod rujukan (iaitu nod di mana nod baharu akan dimasukkan).
JavaScript dan WebSocket: Membina sistem pemprosesan imej masa nyata yang cekap
Dec 17, 2023 am 08:41 AM
JavaScript ialah bahasa pengaturcaraan yang digunakan secara meluas dalam pembangunan web, manakala WebSocket ialah protokol rangkaian yang digunakan untuk komunikasi masa nyata. Menggabungkan fungsi berkuasa kedua-duanya, kami boleh mencipta sistem pemprosesan imej masa nyata yang cekap. Artikel ini akan memperkenalkan cara untuk melaksanakan sistem ini menggunakan JavaScript dan WebSocket, dan memberikan contoh kod khusus. Pertama, kita perlu menjelaskan keperluan dan matlamat sistem pemprosesan imej masa nyata. Katakan kita mempunyai peranti kamera yang boleh mengumpul data imej masa nyata
