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

最近人工智能课老师布置了一个八数码实验，网上看到很多八数码的启发式A*算法，但是大多数都是利用C或者C++在控制台实现的，于是我用js在网页中做了一个类似的。

首先八数码就是一个九宫格，其中有一个空格，其他八个对应数字1-8，

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

启发式算法是指在求解时，利用启发函数将不符合规则的解节点去掉，从而缩小问题的解空间。

A*算法是利用评价函数的启发式算法，在本例中，利用当前节点状态与最终节点状态所不同的格子数来评估节点的优劣，将优越节点储存并在之后展开，将劣质节点抛弃。

利用web实现这一点首先在html中添加九个如图所示input文本框，背景图片为数码格

页面代码为

然后利用javascript获取输入的值，并保存在二维数组中

其中Graph类是用来来保存一个状态节点相关数据：

实现一个showGraph()函数来显示八数码状态：

利用评估函数evaluateGraph()评估当前节点与目标节点的差距值

利用moveGraph()函数来移动并返回一个新节点：

最后是搜索函数，通过从初始节点开始一层层向下搜索，直到抵达目标节点，返回子节点，从子节点一层层向上回溯父节点，便可找到解路径：

最后将解路径节点按顺序压入堆栈，每秒弹出一个节点，显示，形成动画：