资源描述：
《第3讲 搜索算法-8数码游戏的自动求解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第3讲搜索算法－8数码游戏的自动求解知识点一、8数码问题讨论1.1问题求解技术1.2状态空间表示举例1：猴子和香蕉问题1.3状态空间表示举例2：农夫过河问题1.48数码问题的求解二、8数码游戏程序界面三、8数码游戏攻略(人工求解)四、8数码问题的盲目搜索求解4.1一般搜索策略4.2盲目搜索4.2.1广度优先搜索(BFS,BreadthFirstSearch)…五、8数目问题的启发式搜索求解5.1启发式搜索5.1.1有序搜索5.1.2A*算法…5.2剪枝技术一、8数码问题讨论滑块问题：规则形状滑块问题：滑块的形状和大小都是一样的，如一般的拼图游戏和8数码游戏、15数码游戏等。不规则形状滑
2、块问题：滑块的形状或大小不一致，如华容道游戏。本课件讨论的都是规则形状滑块问题。滑块问题：m行n列的滑块问题(Sliding-titlePuzzles)的棋盘有共m×n个方格，这些方格大小相等，其中有一个方格是空着的，其余方格里标有1~m×n-1共m×n-1个数字（或分割的图片）。游戏的目标是：通过移动空格，使得从初始状态出发到达一个指定的目标状态。如下图所示，左图表示初始状态，右图表示目标状态。初始状态目标状态滑块问题的特例：8数码问题初始状态和目标状态都可以指定。思考：能否开发一个键盘滑块软件？1.1问题求解技术问题求解(比如8数码问题的自动求解)技术主要涉及两个方面：问题的表示：
3、通常采用状态空间法。求解的方法：求解问题的通用策略－搜索。状态空间法试探搜索法：在问题的解空间进行搜索来求解问题。通常人们在求解8数码问题时采用的就是这种方法，这一步走不通，退一步，换另一种走法。人工求解迷宫问题更能说明这种思路。基于解答空间的问题表示和求解方法就是状态空间法。状态空间法是以状态和算符为基础来表示和求解问题的。状态空间法的基本概念状态(State，或者称为格局)算符(Operator)状态空间(StateSpace)状态空间法定义状态：为了描述某类不同事物间的差别而引入的一组最少变量q0,q1,…,qn的有序集合。矢量形式：Q=[q0,q1,…,qn]T式中每个元素qi
4、为集合的分量，称为状态变量。给定每个分量的一组值就得到一个具体的状态，如Qk=[q0k,q1k,…,qnk]T。算符：使问题从一种状态变化为另一种状态的手段。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。问题的状态空间：是一个表示该问题全部可能状态及其转换关系的图，它包含三种说明的集合，即三元状态(S,F,G)。S—初始状态集合；F—操作符集合；G—目标状态集合。典型的例子下棋、迷宫及各种游戏。在这些例子中，状态通常也称为格局。中间状态初始状态目标状态对一个问题的状态描述，必须确定3件事：该状态描述方式，特别是初始状态和目标状态的描述；操作符集合及其对状态描述的作用；合理
5、可行的机制避免状态的重复访问。1.2状态空间表示举例1：猴子和香蕉问题问题描述：猴子的初始位置在地面上的a处，要通过放置在b处的箱子，摘下悬挂在c处天花板上的香蕉。abc解题过程用一个四元表列(W,x,Y,z)来表示问题状态。W：猴子的水平位置，取值为a,b,c；x：猴子的垂直位置，0表示在地面上，1表示在箱子上；Y：箱子的水平位置，取值为a,b,c；z：猴子是否摘到香蕉，0表示没有摘到，1表示摘到。操作(算符)：goto(U)：表示猴子走到水平位置U或者用产生式规则表示为：(W,0,Y,z)goto(U)(U,0,Y,z)pushbox(V)：猴子把箱子推到水平位置V，即有，(W,0
6、,W,z)climbbox(W,1,W,z)grasp：猴子摘到香蕉，猴子必须在c处且站在箱子上，才有可能摘到香蕉，即有,(c,1,c,0)grasp(c,1,c,1)climbbox：猴子爬上箱顶，即有，(W,0,Y,z)pushbox(V)(V,0,V,z)该初始状态(a,0,b,0)变换为目标状态(c,1,c,1)的操作符序列为：{goto(b),pushbox(c),climbbox,grasp}abcabcHa!Ha!猴子和香蕉问题的演示abcabcabcabcabcHa!Ha!目标状态初始状态猴子和香蕉问题的状态空间图abc猴子和香蕉问题的动态演示(FLASH)1.3状态空
7、间表示举例2：农夫过河问题问题：有一农夫带一条狼、一只羊和一筐菜从河的左岸乘船到右岸，但受下列条件限制：船太小，农夫每次只能带一样东西过河；如果没有农夫看管，则狼要吃羊，羊要吃菜。问：怎么过河？提示：问题状态表示为(M,W,S,V)。M:农夫的位置，1表示在左岸、0表示在右岸；W:狼的位置，1表示在左岸、0表示在右岸；S:羊的位置，1表示在左岸、0表示在右岸；V:菜的位置，1表示在左岸、0表示在右岸。思考：什么是初始状态和目标状态？规则有哪些？
