人工智能问题求解策略

《人工智能问题求解策略》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、淮北师范大学学院专业研究方向学生姓名学号任课教师姓名任课教师职称人工智能问题求解策略计算机科学与技术计算机科学与技术（师范）问题求解策略孔锐20111202018马艳芳副教授2013年6月25日人工智能问题求解策略摘要：本文以人工智能课程中问题求解策略的搜索算法为研究对象，阐述了图搜索算法的方法设计，借助这些方法依次讨论图搜索策略的本质特点和相关数据结构，并讨论了等代价搜索和A*搜索的执行过程及其效率。关键词：人工智能问题求解搜索算法1.引言人工智能原理是计算机专业本科及研究生教学的主要专业课之一。课程理论性强、知识点多、内容抽象、应用广泛，学习过程需要较强的数学和逻辑表达。知识表达及问题求

2、解是人工智能领域的重要内容。问题求解包含搜索策略、推理和智能技术三种主要方法，其中搜索策略是问题求解的基础方法，多个搜索算法的描述非常抽象，容易使学生感觉枯燥且难以区分。本文对图搜索内容进行有效的学习设计，其理论依据借助历史及生活事实进行类比，将算法思想进行形象表述；对各搜索算法冗长的内容设计表格进行对比和概扌舌；使用数学公式表示，强化算法的可理解性；通过典型的八数码问题实例，展示图搜索算法的扩展过程，增强学生对算法的理解2.搜索策略相关概念问题求解过程就是从问题起始状态到终止状态的搜索过程。从问题的初始状态出发，构造一条使问题得到解决的推理路径，称为搜索。搜索包括盲目搜索和启发式搜索两种策

3、略。盲目搜索包插宽度优先和深度优先搜索，按照预定策略搜索，很少考虑问题的相关信息，搜索结果生成较多状态，生成较大的状态空间显示图。启发式搜索包活等代价搜索和A*算法,考虑问题的领域知识，动态优先选择操作算子，生成较小的状态空间显示图。采用框图和文字描述图搜索策略的传统教学方式，内容枯燥，学生难以快速领悟和常握各方法的核心内容和本质区别0将搜索策略的理论知识采用类比法、对比和案例法分层次推进，表格概括和数学抽象对搜索理论进行形式描述，用人工智能的典型实例与搜索理论融合，增强学习过程的可视性。3・对比及概括概括能力的培养对工科学生非常的重要，尤其是用数学表达式进行抽象和概括。以问题初始状态节点S

4、O为起点逐步扩展，最后扩展到目的状态节点Sg的搜索过程，以八数码问题为例，对比搜索采用的代价函数g(x)和启发函数h(x)如表1和表2所示。表1搜索算法类比表算法代价函数g(x)启发函数h(x)宽度优先搜索深度没有深度优先搜索深度的负值没有等代价搜索从起点到当前结点的代价深度没有A*算法从起点到当前结点的代价深从当前结点到终点的代价深度度表2八数码问题的启发函数及搜索效率算法启发函数h(x)g(x)节点总数扩展节点数宽度优先搜索h(x)=0D(x)深度2716深度优先搜索h(x)=0-D(x)在深度为5界限内没有结果等代价搜索h(x)=0D(x2716A*算法x与Sg不同的码距离D(x)94

5、表中同时对比了各搜索算法扩展的节点数和生成的节点数，各搜索算法的特点和效率一目了然。初始状态SO283目标状态Sg图1八数码问题八数码问题的初始状态和目标状态如图1所示。将牌位于中心，初始状态与目标状态有3个码不同。牌，不能移动到边境外，不能移回祖父节点。g(x)表达为从初始节点SO到扩展节点x的深度。h(x)在等代价搜索中为0,在A*算法中表达为节点x与目标节点Sg的不同码的距离。等代价搜索的估价函数f(x)为深度加不同的码个数。A*算法的f(x)为深度加不同的码距。由表3可知，由于扩展节点和总节点数的下降，启发式搜索比盲目搜索算法的效率高,A*算法比等代价搜索算法效率高。表3搜索算法的O

6、PEN表描述算法OPEN表待扩展节点新节点插入机制代价函数g(x)启发函数h(x)OPEN表数据结构宽度优先先进先出open表后Depth(x),深度0队列深度优先后进先出open表前-Depth(X)0堆栈等代价搜索min©x)J{OPEN}按g(x)值升序重排SO到X的代价0链表A*算法mirMftx)=g

7、核心，抽象描述如表3所示，数据结构分别采用队列、堆栈和链表。OPEN表中待扩展节点、代价函数g(x)和启发函数h(x)用数学公式抽象描述。4.结论图搜索策略作为学习研究对象，生动描述图搜索策略的用途及差别。概括搜索算法的数据结构和函数，使搜索算法的本质和核心内容一目了然，将等代价搜索和A*算法进行对比。上述方法使图搜索策略的学习过程生动深刻，对于人工智能原理课程的其它内容同样具有很好的推广性。参考文献(1〕蔡