Astar算法解决八数码问题Python实现(GUI)

简介

八数码问题:在3*3的方格棋盘上,摆放着1到8这八个数码,有1个方格是空的,其初始状态如图1所示,要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。

状态图搜索:

  • 搜索树:搜索过程中经过的节点和边按原图的连接关系构成一个树型的有向图,称为搜索树。
  • 搜索方式
    • 树式搜索:记录搜索过程中所经过的所有节点和边
  • 路径的获得
    • 树式搜索:反向求解

树式搜索算法:

  • 步1 把初始节点放入OPEN表;
  • 步2 检查OPEN表,若为空,则问题无解,退出;
  • 步3 移出OPEN表中第一个节点N并放入CLOSED表中,并编号为n;
  • 步4 考察节点N是否为目标节点,若是,则搜索成功,退出;
  • 步5 若N不可扩展,则转步2;
  • 步6 扩展节点N,生成所有子节点,对这组子节点作如下处理:
  • (1)、如果有节点N的先辈节点,则删除;
  • (2)、如果有已存在于OPEN表的节点,也删除;但删除之前要比较其返回初始节点的新路径与原路径,如果新路径“短”,则修改这些节点在OPEN表中的原指向父节点的指针,使其指向新的父节点。
  • (3)、如果有已存在于CLOSED表中的节点,则作与(2)同样的处理,并且再将其移出CLOSED表,放入OPEN表重新扩展;
  • (4)、对其余子节点,配上指向父节点n的指针后放入OPEN表,对OPEN表按某种搜索策略排序后转步2。

启发式搜索的实验原理:

启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径,提高了效率。评估函数f(x)定义为:从初始节点S0出发,约束地经过节点X到达目标节点Sg的所有路径中最小路径代价的估计值。

其一般形式为:

f(x)=g(x)+h(x)

其中g(x)表示从初始节点S0到节点X的实际代价;h(x)表示从X到目标节点Sg的最优路径的估计代价。但是实际的形式要根据问题特性确定。

Closed表和open表

——closed表对树式搜索来说存储的是正在成长的搜索树,对线式搜索来说存储的是不断伸长的折现,本省就是所求的路径。

——open表存储当前待考察的节点。

使用一种启发式搜索方法(A算法)编程求解八数码问题(初始状态任选,并对实验结果进行分析得出合理的结论。

流程图

代码

效果如顶部的图所示

注意GUI部分方向键自己控制,空格键利用算法自动走。

 

读者评分
[评分人数: 1 平均分: 5]

评论

OmegaXYZ