人工智能：基于图搜索策略求解八数码问题的最优路径

《人工智能：基于图搜索策略求解八数码问题的最优路径》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、人工智能大作业学院电子工程学院专业智能科学与技术学号姓名第一部分：八数码难题基于图搜索策略求解八数码问题的最优路径一、问题简介八数码问题状态图仅给出了初始节点和目标节点，其余节点需用状态转换规则来产生。类似于这样表示的状态图称为隐式状态图，或者说状态图的隐式表示。八数码游戏（八数码问题）描述为：在3×3组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有1-8八个数码中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。这种游戏求解的问题是：给定一种初始的将牌布局或结构（称初始状态）和一

2、个目标的布局（称目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。12384 765283164 75初始节点目标节点二、基于图搜索问题的搜索方法图搜索是人工智能的核心技术之一，人工智能的许多分支领域都涉及到图搜索。我们可以把图搜索看成是一种在图中寻找路径的方法。初始节点和目标节点分别代表初始数据库和满足终止条件的数据库，求得把一个数据库变换成另一个数据库的规则序列问题就等价于求的图中的一条路径问题。图搜索一般过程：（1）建立一个只含有其实节点S的搜索图G，建立一个OPEN表，它只含有初始节点S。（2）建立一个表CLOSED，它的初

3、始状态为空。（3）LOOP：若OPEN为空，则失败退出。（4）选择OPEN表中第一个节点，将其放入CLOSED表，称此节点为节点n。（5）如果n属于目标集（目标节点），则有解并成功退出，则沿着G中n到s的指针得出一条路径，并以此返回（指针在步骤7建立）。（6）扩展节点n，建立集合M，使M仅含有n的后继者，而不含有n的祖先，并把M中的节点作为n的后继者加入到G中。（7）对M中原来不在G中的节点（即不在OPEN表中也不在CLOSED表中）建立一个从这些节点到n的指针，并把它们加入到表OPEN中。对已经在OPEN或CLOSED表上的每一个成员M，确

4、定是否更改通到n的指针方向。对于已在CLOSED表上的每个M成员，确定是否应该改变图G中通向它的每个后裔节点的指针方向。（8）按某种方式，对OPEN表中的节点重新排序。（9）GOLOOP。图搜索的一般方法：三、求解八数码难题的两种算法3.1广度优先搜索广度优先搜索就是始终先在同一级节点中考查，只有当同一级节点考查完之后，才考查下一级节点。或者说，是以初始节点为根节点，向下逐级扩展搜索树。所以，广度优先策略的搜索树是自顶向下一层一层逐渐生成的。步骤步1把初始节点S0放入OPEN表中；步2若OPEN表为空，则搜索失败，退出。步3取OPEN表中前面

5、第一个节点N放入CLOSED表中，并冠以顺序编号n；步4若目标节点Sg=N，则搜索成功，结束。步5若N不可扩展，则转步2；步6扩展N，将其所有子节点配上指向N的返回指针依次放入OPEN表的尾部，转步2。广度优先搜索亦称为宽度优先或横向搜索。这种策略是完备的，即如果问题的解存在，用它则一定能找到解，且找到的解还是最优解（即最短的路径）。这是优点，缺点是搜索效率低。宽度优先搜索流程图： 图1图2给出广度优先搜索应用于八数码难题时所生成的搜索树。搜索树上的所有结点都标记它们所对应的状态，每个结点旁边的数字表示结点扩展的顺序。粗线条路径表明求得的一个

6、解。从图中可以看出，扩展２６个结点和生成４６个结点之后，才求得这个解。此外，直接观察此图表明，不存在有更短走步序列的解。图23.2启发式图搜索的A*算法估价函数：将启发函数与代价函数相结合，为了防止在单独利用启发函数的时候误入歧途。f(x)＝g(x)＋h(x)h(x)：启发函数，有利于搜索纵向发展，提高搜索效率，但影响完备性。g(x)：代价函数，有利于搜索横向发展，提高搜索的完备性，但影响搜索效率。f(x)：是初始节点S0到达节点x处已付出的代价与节点x到达目标节点Sg的接近程度估计值总和。是g（x）与h（x）的折中。A算法：步1把附有f（S

7、0）的初始节点S0放入OPEN表中；步2若OPEN表为空，则搜索失败，退出。步3移出OPEN表中第一个节点N放入CLOSED表中，并冠以顺序编号n；步4若目标节点Sg＝N，则搜索成功，结束。步5若N不可扩展，则转步2；步6扩展N，生成一组附有f(x)的子节点，对这组节点作如下处理：（1）考察是否有已在OPEN表或CLOSED表中存在的节点；若有则再考察其中有无N的先辈节点，若有则删除之；对于其余节点，也删除之，但由于它们被第二次生成，需考虑是否修改已经存在于OPEN表或CLOSED表中的这些节点及其后裔的返回指针和f（x）的值，修改原则是抄f

8、(x)值小的路走”。（2）对其余子节点配上指向N的返回指针后放入OPEN表中，并对OPEN表按f(x)以升序排列，转步2。A*算法：对A算法再限制其估价函数中的启发