js版九宫格拼图与启发式搜索(A*算法) (2)

   (6)如何判断点击的方块是否能移动,首先我们将最后一个方块隐藏如果点击的方块距离最后(8号)方块距离为1则表示可以移动,及两个状态可以转化,

     这个方法也可以看做两个状态的数组能否相互转化,可作为后面启发式搜索判断节点扩展的方法;

     

js版九宫格拼图与启发式搜索(A*算法)

    以上代码为每个方块添加点击事件

     至此游戏的基本实现方式介绍完毕,详细看代码

 二、启发式搜索

  启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径,提高了效率。在启发式搜索中,对位置的估价是十分重要的。采用了不同的估价可以有不同的效果 

它把到达节点的耗散g(n)和从该节点到目标节点的消耗h(n)结合起来对节点进行评价:f(n)=g(n)+h(n) 

  简单的说就是扩展当前状态节点的所有可能下一步节点,通过一个方式来估算那个节点最快能到到目标,不断重复知道实现达到目标状态;

  我们这里的估计方法为 当前状态的全部距离+走的步数;

  

  搜索过程可能描述如下:

(1)把初始节点S0放入Open表中,f(S0)=g(S0)+h(S0);

(2)如果Open表为空,则问题无解,失败退出;

(3)把Open表的第一个节点取出放入Closed表,并记该节点为n;

(4)考察节点n是否为目标节点。若是,则找到了问题的解,成功退出;

(5)若节点n不可扩展,则转到第(2)步;

(6)扩展节点n,生成子节点ni(i=1,2,……),计算每一个子节点的估价值f(ni) (i=1,2,……),并为每一个子节点设置指向父节点的指针,然后将这些子节点放入Open表中;

(7)根据各节点的估价函数值,对Open表中的全部节点按从小到大的顺序重新进行排序;

(8)转第(2)步。

  代码太长 截图不够,详细还是看代码吧:O(∩_∩)O

  

js版九宫格拼图与启发式搜索(A*算法)

  

  我是把一步的搜索结果直接展示在视图中的,所以closed表中没有保留节点状态,单通过console.log输出,大家可以点击F12在调试模式下查看全部节点;

  若希望查看每一步视图状态,则可以在searchA方法的while循环中打断点查看效果;

 

 

   网上找个图说明一下搜索的方法:容易明白

  

js版九宫格拼图与启发式搜索(A*算法)

          

js版九宫格拼图与启发式搜索(A*算法)

 

js版九宫格拼图与启发式搜索(A*算法)

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wspzgj.html