利用人工智能技术解决八数码游戏问题 1.八数码游戏问题简介 九宫排字问题(又称八数码问题)是人工智能当中有名的难题之一。问题是在 3×3方格盘上,放有八个数码,剩下第九个为空,每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置,要求通过一系列的数码移动,将初始位置转化为目标位置。 2.八数码游戏问题的状态空间法表示 ①建立一个只含有初始节点 s0的搜索图 g,把 s0放入 open表中 ②建立 closed表,且置为空表 ③判断 open表是否为空表,若为空,则问题无解,退出 ④选择 open表中的第一个节点,把它从 open表移出,并放入 closed表中,将此节点记为节点 n ⑤考察节点 n是否为目标节点,若是,则问题有解,成功退出。问题的解就是沿着 n到s0的路径得到。若不是转⑥ ⑥扩展节点 n生成一组不是n的祖先的后继节点,并将它们记为集合 m,将 m中的这些节点作为 n的后继节点加入图 g中 ⑦对未在g中出现过的(open和 closed表中未出现过的)集合 m中的节点, 设置一个指向父节点 n的指针,并把这些节点放入 open表中;对于已在g中出现过的m中的节点,确定是否需要修改指向父节点的指针;对于已在g中出现过并已在closed表中的m中的节点,确定是否需要修改通向他们后继节点的指针。 ⑧ 按某一任意方式或某种策略重排open表中节点的顺序 ⑨ 转③ 3.八数码游戏问题的盲目搜索技术 宽度优先搜索: 1、定义 如果搜索是以接近起始节点的程度依次扩展节点的,那么这种搜索就叫做宽度优先搜索(breadth-first search)。 2、特点 这种搜索是逐层进行的;在对下一层的任一节点进行搜索之前,必须搜索完本层的所有节点。 3、宽度优先搜索算法 (1) 把起始节点放到 open表中(如果该起始节点为一目标节点,则求得一个解答)。 (2) 如果 open是个空表,则没有解,失败退出;否则继续。 (3) 把第一个节点(节点 n)从 open表移出,并把它放入 closed的扩展节点表中。 (4) 扩展节点 n。如果没有后继节点,则转向上述第(2)步。 (5) 把 n的所有后继节点放到 open表末端,并提供从这些后继节点回到 n的指针。 (6) 如果 n的任一个后继节点是个目标节点,则找到一个解答,成功退出;否则转向第(2)步。 流程图: 性质: 当问题有解时,一定能找到解。 当问题为单位消耗值,且问题有解时,一定能找到最优解。 算法与问题无关,具有通用性。 时间效率和空间效率都比较低。 深度优...