人工智能A星算法及人工智能部分习题答案.docx

1、人工智能A星算法及人工智能部分习题答案A*算法实验报告实验目的1熟悉和掌握启发式搜索的定义、估价函数和算法过程2. 学会利用A*算法求解N数码难题3. 理解求解流程和搜索顺序实验原理A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索，总是选择f值最小的节点作为扩展节点。因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的代价以及从节点n到达目标节点的代价。实验条件1.Window NT/xp/7及以上的操作系统2.内存在512M以上3.CPU在奔腾II以上实验内容1.分别以8数码和15数码为例实际

2、求解A*算法2.画出A*算法求解框图3.分析估价函数对搜索算法的影响4.分析A*算法的特点实验分析1. A*算法基本步骤1）生成一个只包含开始节点n0的搜索图G，把n0放在一个叫OPEN的列表上。2）生成一个列表CLOSED，它的初始值为空。3）如果OPEN表为空，则失败退出。4）选择OPEN上的第一个节点，把它从OPEN中移入CLPSED，称该节点为n。5）如果n是目标节点，顺着G中，从n到n0的指针找到一条路径，获得解决方案，成功退出（该指针定义了一个搜索树，在第7步建立）。6）扩展节点n，生成其后继结点集M，在G中，n的祖先不能在M中。在G中安置M的成员，使他们成为n的后继。7）从M的每

3、一个不在G中的成员建立一个指向n的指针（例如，既不在OPEN中，也不在CLOSED中）。把M1的这些成员加到OPEN中。对M的每一个已在OPEN中或CLOSED中的成员m，如果到目前为止找到的到达m的最好路径通过n，就把它的指针指向n。对已在CLOSED中的M的每一个成员，重定向它在G中的每一个后继，以使它们顺着到目前为止发现的最好路径指向它们的祖先。8）按递增f*值，重排OPEN（相同最小f*值可根据搜索树中的最深节点来解决）。9）返回第3步。在第7步中，如果搜索过程发现一条路径到达一个节点的代价比现存的路径代价低，就要重定向指向该节点的指针。已经在CLOSED中的节点子孙的重定向保存了后面

4、的搜索结果，但是可能需要指数级的计算代价。实验步骤算法流程图程序代码#include #include #include using namespace std;const int ROW = 3;/行数const int COL = 3;/列数const int MAXDISTANCE = 10000;/最多可以有的表的数目const int MAXNUM = 10000;typedef struct _Node int digitROWCOL; int dist; /一个表和目的表的距离 int dep; / t深度 int index; /节点的位置 Node;Node src, des

5、t;/ 父节表 目的表vector node_v; /存储节点bool isEmptyOfOPEN() /open表是否为空 for (int i = 0; i node_v.size(); i+) if (node_vi.dist != MAXNUM) return false; return true;bool isEqual(int index, int digitCOL) /判断这个最优的节点是否和目的节点一样 for (int i = 0; i ROW; i+) for (int j = 0; j COL; j+) if (node_vindex.digitij != digitij

6、) return false; return true;ostream& operator(ostream& os, Node& node) for (int i = 0; i ROW; i+) for (int j = 0; j COL; j+) os node.digitij ; os endl; return os;void PrintSteps(int index, vector& rstep_v)/输出每一个遍历的节点 深度遍历 rstep_v.push_back(node_vindex); index = node_vindex.index; while (index != 0)

7、rstep_v.push_back(node_vindex); index = node_vindex.index; for (int i = rstep_v.size() - 1; i = 0; i-)/输出每一步的探索过程 cout Step rstep_v.size() - i endl rstep_vi endl;void Swap(int& a, int& b) int t; t = a; a = b; b = t;void Assign(Node& node, int index) for (int i = 0; i ROW; i+) for (int j = 0; j COL;

8、j+) node.digitij = node_vindex.digitij;int GetMinNode() /找到最小的节点的位置 即最优节点 int dist = MAXNUM; int loc; / the location of minimize node for (int i = 0; i node_v.size(); i+) if (node_vi.dist = MAXNUM) continue; else if (node_vi.dist + node_vi.dep) dist) loc = i; dist = node_vi.dist + node_vi.dep; retur

9、n loc;bool isExpandable(Node& node) for (int i = 0; i node_v.size(); i+) if (isEqual(i, node.digit) return false; return true;int Distance(Node& node, int digitCOL) int distance = 0; bool flag = false; for(int i = 0; i ROW; i+) for (int j = 0; j COL; j+) for (int k = 0; k ROW; k+) for (int l = 0; l

10、COL; l+) if (node.digitij = digitkl) distance += abs(i - k) + abs(j - l); flag = true; break; else flag = false; if (flag) break; return distance;int MinDistance(int a, int b) return (a b ? a : b);void ProcessNode(int index) int x, y; bool flag; for (int i = 0; i ROW; i+) for (int j = 0; j 0) Swap(n

11、ode_up.digitxy, node_up.digitx - 1y); if (isExpandable(node_up) dist_up = Distance(node_up, dest.digit); node_up.index = index; node_up.dist = dist_up; node_up.dep = node_vindex.dep + 1; node_v.push_back(node_up); Node node_down; Assign(node_down, index);/向下扩展的节点 int dist_down = MAXDISTANCE; if (x 0

12、) Swap(node_left.digitxy, node_left.digitxy - 1); if (isExpandable(node_left) dist_left = Distance(node_left, dest.digit); node_left.index = index; node_left.dist = dist_left; node_left.dep = node_vindex.dep + 1; node_v.push_back(node_left); Node node_right; Assign(node_right, index);/向右扩展的节点 int di

13、st_right = MAXDISTANCE; if (y 2) Swap(node_right.digitxy, node_right.digitxy + 1); if (isExpandable(node_right) dist_right = Distance(node_right, dest.digit); node_right.index = index; node_right.dist = dist_right; node_right.dep = node_vindex.dep + 1; node_v.push_back(node_right); node_vindex.dist

14、= MAXNUM;int main() / 主函数 int number; cout Input source: endl; for (int i = 0; i ROW; i+)/输入初始的表 for (int j = 0; j number; src.digitij = number; src.index = 0; src.dep = 1; cout Input destination: endl;/输入目的表 for (int m = 0; m ROW; m+) for (int n = 0; n number; dest.digitmn = number; node_v.push_bac

15、k(src);/在容器的尾部加一个数据 cout Search. endl; clock_t start = clock(); while (1) if (isEmptyOfOPEN() cout Cannt solve this statement! endl; return -1; else int loc; / the location of the minimize node最优节点的位置 loc = GetMinNode(); if(isEqual(loc, dest.digit) vector rstep_v; cout Source: endl; cout src endl; P

16、rintSteps(loc, rstep_v); cout Successful! endl; cout Using (clock() - start) / CLOCKS_PER_SEC seconds. endl; break; else ProcessNode(loc); return 0;程序运行效果图28316475(初始状态)123804765(结束状态)个人实验小结A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索，总是选择f值最小的节点作为扩展节点。通过本实验， 我熟悉启发式搜索的定义、估价函数和算法过程，并利用A*算法求解了8数码难题，理解了求解流程和

17、搜索顺序。实验过程中巩固了所学的知识，通过实验也提高了自己的编程和思维能力，收获很多。1.什么是人类智能？它有哪些特征或特点？定义：人类所具有的智力和行为能力。特点：主要体现为感知能力、记忆与思维能力、归纳与演绎能力、学习能力以及行为能力。2.人工智能是何时、何地、怎样诞生的？解：人工智能于1956年夏季在美国Dartmouth大学诞生。此时此地举办的关于用机器模拟人类智能问题的研讨会，第一次使用“人工智能”这一术语，标志着人工智能学科的诞生。3.什么是人工智能？它的研究目标是？定义：用机器模拟人类智能。研究目标：用计算机模仿人脑思维活动，解决复杂问题；从实用的观点来看，以知识为对象，研究知识

18、的获取、知识的表示方法和知识的使用。4.人工智能的发展经历了哪几个阶段？解：第一阶段：孕育期（1956年以前）；第二阶段：人工智能基础技术的研究和形成（19561970年）；第三阶段：发展和实用化阶段（19711980年）；第四阶段：知识工程和专家系统（1980年至今）。5.人工智能研究的基本内容有哪些？解：知识的获取、表示和使用。6.人工智能有哪些主要研究领域？解：问题求解、专家系统、机器学习、模式识别、自动定论证明、自动程序设计、自然语言理解、机器人学、人工神经网络和智能检索等。7.人工智能有哪几个主要学派？各自的特点是什么？主要学派：符号主义和联结主义。特点：符号主义认为人类智能的基本单

19、元是符号，认识过程就是符号表示下的符号计算，从而思维就是符号计算；联结主义认为人类智能的基本单元是神经元，认识过程是由神经元构成的网络的信息传递，这种传递是并行分布进行的。8.人工智能的近期发展趋势有哪些？解：专家系统、机器人学、人工神经网络和智能检索。9.什么是以符号处理为核心的方法？它有什么特征？解：通过符号处理来模拟人类求解问题的心理过程。特征：基于数学逻辑对知识进行表示和推理。11.什么是以网络连接为主的连接机制方法？它有什么特征？解：用硬件模拟人类神经网络，实现人类智能在机器上的模拟。特征：研究神经网络。1.请写出用一阶谓词逻辑表示法表示知识的步骤。步骤：（1）定义谓词及个体，确定每

20、个谓词及个体的确切含义；（2）根据所要表达的事物或概念，为每个谓词中的变元赋予特定的值；（3）根据所要表达的知识的语义用适当的联接符号将各个谓词联接起来，形成谓词公式。2.设有下列语句，请用相应的谓词公式把它们表示出来：（1）有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。解：定义谓词如下： Like(x,y)：x喜欢y。 Club(x)：x是梅花。 Human(x)：x是人。 Mum(x)：x是菊花。“有的人喜欢梅花”可表达为：( x)(Human(x) Like(x,Club(x)“有的人喜欢菊花”可表达为：( x)(Human(x) Like(x,Mum(x)“有的人既喜欢梅

21、花又喜欢菊花”可表达为：( x)(Human(x) Like(x,Club(x) Like(x,Mum(x)（1）他每天下午都去玩足球。解：定义谓词如下： PlayFootball(x)：x玩足球。 Day(x)：x是某一天。 则语句可表达为：( x)(D(x) PlayFootball(Ta)（2）太原市的夏天既干燥又炎热。解：定义谓词如下：Summer(x)：x的夏天。 Dry(x)：x是干燥的。 Hot(x)：x是炎热的。则语句可表达为：Dry(Summer(Taiyuan) Hot(Summer(Taiyuan)（3）所有人都有饭吃。解：定义谓词如下：Human(x)：x是人。 Eat

22、(x)：x有饭吃。则语句可表达为：( x)(Human(x) Eat(x)（4）喜欢玩篮球的人必喜欢玩排球。解：定义谓词如下：Like(x,y)：x喜欢y。 Human(x)：x是人。则语句可表达为：( x)(Human(x) Like(x,basketball) Like(x,volleyball)（5）要想出国留学，必须通过外语考试。解：定义谓词如下：Abroad(x)：x出国留学。 Pass(x)：x通过外语考试。则语句可表达为：Abroad(x) Pass(x)、猴子问题：2.7解：根据谓词知识表示的步骤求解问题如下： 解法一： (1)本问题涉及的常量定义为： 猴子：Monkey，箱子

23、：Box，香蕉：Banana，位置：a，b，c (2)定义谓词如下： SITE(x，y)：表示x在y处； HANG(x，y)：表示x悬挂在y处； ON(x，y)：表示x站在y上； HOLDS(y，w)：表示y手里拿着w。 (3)根据问题的描述将问题的初始状态和目标状态分别用谓词公式表示如下： 问题的初始状态表示： SITE(Monkey，a)HANG(Banana，b)SITE(Box，c)ON(Monkey，Box)HOLDS(Monkey，Banana) 问题的目标状态表示： SITE(Monkey，b)HANG(Banana，b)SITE(Box，b)ON(Monkey，Box)HOLD

24、S(Monkey，Banana) 解法二：本问题涉及的常量定义为： 猴子：Monkey，箱子：Box，香蕉：Banana，位置：a，b，c定义谓词如下：SITE(x，y)：表示x在y处； ONBOX(x)：表示x站在箱子顶上； HOLDS(x)：表示x摘到了香蕉。(3)根据问题的描述将问题的初始状态和目标状态分别用谓词公式表示如下： 问题的初始状态表示： SITE(Monkey，a)SITE(Box，c)ONBOX(Monkey)HOLDS(Monkey) 问题的目标状态表示： SITE(Box，b)SITE(Monkey，b)ONBOX(Monkey)HOLDS(Monkey) 从上述两种解

25、法可以看出，只要谓词定义不同，问题的初始状态和目标状态就不同。所以，对于同样的知识，不同的人的表示结果可能不同。 2.8解：本问题的关键就是制定一组操作，将初始状态转换为目标状态。为了用谓词公式表示操作，可将操作分为条件(为完成相应操作所必须具备的条件)和动作两部分。条件易于用谓词公式表示，而动作则可通过执行该动作前后的状态变化表示出来，即由于动作的执行，当前状态中删去了某些谓词公式而又增加一些谓词公式从而得到了新的状态，通过这种不同状态中谓词公式的增、减来描述动作。 定义四个操作的谓词如下，操作的条件和动作可用谓词公式的增、删表示： (1)gotox，y)：从x处走到y处。条件：SITE(M

26、onkey，x)动作：删除SITE(Monkey，x)；增加SITE(Monkey，y) (2)pushbox (x，y)：将箱子从x处推到y处。 条件：SITE(Monkey，x)SITE(Box，x)ONBOX(Monkey)动作：删除SITE(Monkey，x)，SITE(Box，x)；增加SITE(Monkey，y)，SITE(Box，y) (3)climbbox：爬到箱子顶上。 条件：ONBOX(Monkey) 动作：删除ONBOX(Monkey)；增加ONBOX(Monkey) (4)grasp：摘下香蕉。 条件：HOLDS(Monkey) ONBOX(Monkey) SITE(Monkey，b) 动作：删除HOLDS(Monkey)；增加HOLDS(Monkey) 在执行某一操作前，先检查当前状态是否满足其前提条件。若满足，则执行该操作。否则，检查另一操作的条件是否被满足。检查的方法就是当前的状态中是否蕴含了操作所要求的条件。在定义了操作谓词后，就可以给出从初始状态到目标状态的求解过程。在求解过程中，当进行条件检查时，要进行适当的变量代换。 SITE(Monkey，a) SITE(Box，c) ONBOX(Mon