配眼镜经验总结

三种搜索算法解8数码问题

1. 三种搜索算法解8数码问题
   1. 一、实验内容
   2. 二、实验过程
      1. 设计思路
      2. 设计过程
   3. 三、实验结果

一、实验内容

1. 编写成三种算法程序
2. 用三种算法编写8数码问题，指出扩展的 节点数、所需时间

二、实验过程

设计思路

程序主要分为三个模块，一是输入模块，二是计算模块，三是画图输出模块。
- 输入模块，主要使用python包turtle的输入，得到形如” 23156478”的字符串输入，然后转换成3*3列表，并且得到一个数字输入（选择算法）。
- 计算模块，首先将解决问题的方法面向过程化，也就是空格的移动抽象为上，下，左，右四个动作，然后利用四个动作和open_table与closed_table数据结构处理问题，但是A*算法还多一个估价函数
- 输出模块，利用turtle包画九个正方形和对应的数字，得到结果列表后按照此列表画出移动的顺序。

设计过程

1. 输入模块

   input1 = screen.textinput("初始状态输入", "请按逐行逐列的顺序输入8数码初始输入，空为 ，例如：' 23156478'")
   input2 = screen.numinput("搜算算法输入","1为广度搜索，2为深度搜索，3为A*启发式搜索",default=3,minval=1,maxval=3)
   if len(input1) != 9 or input1 == None or input2 == None:
       messagebox.showinfo("输入有误")
       sys.exit(0)
   init_status = transfer(input1)
   

2. 计算模块

   left(a)
   right(a)
   up(a)
   down(a)                     //3*3列表空格向下移动
   get_value(a)                    //估价函数
   solve_by_breadth(a)         //广度搜索
   solve_by_deepth(a)          //深度搜索
   solve_by_A(a)               //启发搜索
   

3. 输出模块

   zfx(a=200)                                  //画正方形
   zfx2(a=100,x=0,y=0,c='white',s='')   //画九宫格
   jggChange(first,second)                 //画空格移动的前后两个状态
   t.speed(0)                                  //控制海龟速度
   jgg(init_status)                            //先画初始状态
   t.up()
   t.goto(x=0,y=200)
   t.down()
   s = "时间:"+str(time)+"s,扩展节点数:"+str(result[0])//显示计算时间和扩展节点数
   t.write(str(s),align='center',font=('宋体',20,'bold'))
   for i in range(len(order)-1):
       jggChange(order[i],order[i+1])
   t.mainloop()
   

三、实验结果

1. 宽度和深度在不同的情况下有着不同的表现，比如样例”23156478“宽度表现得很好，但是在样例“2 3156478”只有搜索表现得很好，其他两种表现得都不好

---

欢迎在评论区中进行批评指正，转载请注明来源，如涉及侵权，请联系作者删除。