人工智能关于八数码问题论文(可编辑)

人工智能关于八数码问题论文(可编辑) 人工智能关于八数码问题论文 人工智能关于八数码问题论文 摘要: 八数码问题是人工智能中一个很典型的智力问题。本文以状态空间搜索的观点讨论了八数码问题，给出了八数码问题的Java算法与实现的思想，分析了A算法的可采纳性等及系统的特点。关键词九宫重排，状态空间，启发式搜索，A算法1引言九宫重排问题是人工智能当中有名的难题之一。问题是在3×3方格盘上，放有八个数码，剩下一个位置为空，每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置，要求通过一系列的数码移动，将初始状态转化为目标状态。状态转换的规则:空格四周的数移向空格，我们可以看作是空格移动，它最多可以有,个方向的移动，即上、下、左、右。九宫重排问题的求解方法，就是从给定的初始状态出发，不断地空格上下左右的数码移至空格，将一个状态转化成其它状态，直到产生目标状态。 一、 问题描述 1.1 待解决问题的解释 八数码游戏(八数码问题)描述为:在3×3组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有1-8八个数码中的某一个 数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。这种游戏求解的问题是:给定一种初始的将牌布局或结构(称初始状态)和一个目标的布局(称目标状态)，问如何移动将牌，实现从初始状态到目标状态的转变。 1.2 问题的搜索形式描述(4要素) 初始状态: 8个数字将牌和空格在九宫格棋盘上常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。 广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。在这里就要用到启发式搜索 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提到了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。 启发中的估价是用估价函数 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示的，如:f n g n + h n 其中f n 是节点n的估价函数，g n 是在状态空间中从初始节点到n节点的实际代价，h n 是从n到目标节点最佳路径的估计代价。 不管哪种搜索，都统一用这样的形式表示:搜索的对象是一个图，它面向一个问题，不一定有明确的存储形式，但它里面的一个结点都有可能是一个解(可行解)，搜索的目的有两个方面，或者求可行解，或者从可行解集中求最优解我们说DFS和BFS都是蛮力搜索，因为它们在搜索到一个结点时，在展开它的后续结点时，是对它们没有任何‘认识’的，它认为它的孩子们都是一样的‘优秀’，但事实并非如此，后续结点是有好有坏的。好，就是说它离目标结点‘近’，如果优先处理它，就会更快的找到目标结点，从而整体上提高搜索性能。 为了改善上面的算法，我们需要对展开后续结点时对子结点有所了解，这里需要一个估值函数，估值函数就是评价函数，它用来评价子结点的好坏，因为准确评价是不可能的，所以称为估值。如果估值函数只考虑结点的某种性能上的价值，而不考虑深度，比较有名的就是有序搜索(Ordered-Search)，它着重看好能否找出解，而不看解离起始结点的距离(深度)。如果估值函数考虑了深度，或者是带权距离(从起始结点到目标结点的距离加权和)，那就是A*如果不考虑深度，就是说不要求最少步数，移动一步就相当于向后多展开一层结点，深度多算一层，如果要求最少步数，那就需要用A*。简单的来说A*就是将估值函数分成两个部分，一个部分是路径价值，另一个部分是一般性启发价值，合在一起算估整个结点的价值， b 初始状态是1 04 2 7 3 8 5 6，用h作为启发函数结果都如下: 中间略 b 初始状态是1 0 3 8 2 4 7 6 5，用h作为启发函数结果都如 下: 四、参考文献 [1] Artificial Intelligence――A Modern Approach. Stuart Russell, Peter Norvig. 人民邮电出版社,2004 [2] Artificial Intelligence, Rob Callan. 电子工业出版 社,2004 附录―源代码及其注释 #include "stdafx.h" #include "iostream.h" #include #include #include #include static int target[9] 1,2,3,8,0,4,7,6,5 ; //class definition class eight_num private: int num[9]; int not_in_position_num; int deapth; int eva_function; public: eight_num* parent; eight_num* leaf_next; eight_num* leaf_pre; eight_num int init_num[9] ; eight_num int num1,int num2,int num3,int num4,int num5,int num6,int num7,int num8,int num9 num[0] num1; num[1] num2; num[2] num3; num[3] num4; num[4] num5; num[5] num6; num[6] num7; num[7] num8; num[8] num9; eight_num void for int i 0;i 9;i++ num[i] i; void cul_para void ; void get_numbers_to int other_num[9] ; int get_nipn void return not_in_position_num; int get_deapth void return deapth; int get_evafun void return eva_function; void set_num int other_num[9] ; void show void ; eight_num& operator eight_num& ; eight_num& operator int other_num[9] ; int operator eight_num& ; int operator int other_num[9] ; ; //计算启发函数g n 的值 void eight_num::cul_para void int i; int temp_nipn 0; for i 0;i 9;i++ if num[i]! target[i] temp_nipn++; not_in_position_num temp_nipn; if this- parent NULL deapth 0; else deapth this- parent- deapth+1; eva_function not_in_position_num+deapth; //构造函数1 eight_num::eight_num int init_num[9] for int i 0;i 9;i++ num[i] init_num[i]; //显示当前节点的状态 void eight_num::show cout num[0]; cout " "; cout num[1]; cout " "; cout num[2]; cout "\n"; cout num[3]; cout " "; cout num[4]; cout " "; cout num[5]; cout "\n"; cout num[6]; cout " "; cout num[7]; cout " "; cout num[8]; cout "\n"; //复制当前节点状态到一个另数组中 void eight_num::get_numbers_to int other_num[9] for int i 0;i 9;i++ other_num[i] num[i]; //设置当前节点状态 欲设置的状态记录的other数组中 void eight_num::set_num int other_num[9] for int i 0;i 9;i++ num[i] other_num[i]; eight_num& eight_num::operator eight_num& another_8num for int i 0;i 9;i++