下载文档原格式
![人工智能[第五章状态空间搜索策略]山东大学期末考试知识点复习](https://img.taocdn.com/s1/m/90a7eb54dd36a32d73758188.png)
第五章状态空间搜索策略搜索是人工智能的一个基本问题，是推理不可分割的一部分。
搜索是求解问题的一种方法，是根据问题的实际情况，按照一定的策略或规则，从知识库中寻找可利用的知识，从而构造出一条使问题获得解决的推理路线的过程。
搜索包含两层含义：一层含义是要找到从初始事实到问题最终答案的一条推理路线；另一层含义是找到的这条路线是时间和空间复杂度最小的求解路线。
搜索可分为盲目搜索和启发式搜索两种。
1．1 盲目搜索策略1．状态空间图的搜索策略为了利用搜索的方法求解问题，首先必须将被求解的问题用某种形式表示出来。
一般情况下，不同的知识表示对应着不同的求解方法。
状态空间表示法是一种用“状态”和“算符”表示问题的方法。
状态空间可由一个三元组表示(S，F，Sg)。
利用搜索方法求解问题的基本思想是：首先将问题的初始状态(即状态空间图中的初始节点)当作当前状态，选择一适当的算符作用于当前状态，生成一组后继状态(或称后继节点)，然后检查这组后继状态中有没有目标状态。
如果有，则说明搜索成功，从初始状态到目标状态的一系列算符即是问题的解；若没有，则按照某种控制策略从已生成的状态中再选一个状态作为当前状态，重复上述过程，直到目标状态出现或不再有可供操作的状态及算符时为止。
算法5．1 状态空间图的一般搜索算法①建立一个只含有初始节点S0的搜索图G，把S放入OPEN表中。
②建立CLOSED表，且置为空表。
③判断OPEN表是否为空表，若为空，则问题无解，退出。
④选择OPEN表中的第一个节点，把它从OPEN表移出，并放入CLOSED表中，将此节点记为节点n。
⑤考察节点n是否为目标节点，若是，则问题有解，并成功退出。
问题的解的这条路径得到。
即可从图G中沿着指针从n到S⑥扩展节点n生成一组不是n的祖先的后继节点，并将它们记作集合M，将M中的这些节点作为n的后继节点加入图G中。
⑦对那些未曾在G中出现过的(即未曾在OPEN表上或CLOSED表上出现过的)M中的节点，设置一个指向父节点(即节点n)的指针，并把这些节点加入OPEN 表中；对于已在G中出现过的M中的那些节点，确定是否需要修改指向父节点(n 节点)的指针；对于那些先前已在G中出现并且已在COLSED表中的M中的节点，确定是否需要修改通向它们后继节点的指针。
实验一搜索策略一、实验内容1.熟悉和掌握启发式搜索的定义、估价函数和算法过程，比较不同算法的性能。
2.以八数码问题或路径规划等问题为例设计启发式搜索算法，改变启发函数，观察结果的变化，分析原因。
二、实验目的熟悉和掌握各种启发式搜索策略的思想，掌握A*算法的定义、估价函数和算法过程，理解求解流程和搜索顺序。
三、实验内容1、分别以各种搜索算法为例演示搜索过程，比较不同算法的性能；2、分析各种算法中的OPEN表CLOSE表的生成过程；3、分析估价函数对搜索算法的影响；4、以八数码问题或路径规划等问题为例设计启发式搜索算法，改变启发函数，观察结果的变化，分析原因。
四、实验记录搜索策略实验报告表一启发式搜索A*算法框图路径规划问题中的启发函数在之前的作业中我们就已经写过A*算法的程序代码。
在八数码路径规划问题中，利用A*算法去找出一条最短路，最要关注的就是估价函数，在本实验中，估价函数为路径代价g 和启发函数h之和。
进而我们需要关注启发函数。
在原启发函数的定义用该点到目标点的曼哈顿距离估计从该点到目标节点的代价。
源节点目标节点7 2 4 0 1 25 06 3 4 58 3 1 6 7 8源程序如下：def setH(self, endNode):for x in range(0, 3):for y in range(0, 3):for m in range(0, 3):for n in range(0, 3):if self.array2d[x][y] == endNode.array2d[m][n]:self.h += abs(x-m)+abs(y-n)上图中的多层循环意在取值该节点到目标节点的曼哈顿距离。
而在曼哈顿距离下的花销如下：一共需要26步完成。
并且程序执行速度也比较快。
欧式距离作为启发式def setH(self, endNode):for x in range(0, 3):for y in range(0, 3):for m in range(0, 3):for n in range(0, 3):if self.array2d[x][y] == endNode.array2d[m][n]:#self.h += abs(x-m)+abs(y-n)self.h += (abs(x-m)*abs(x-m) + abs(y-n)*abs(y-n)) ** 0.5用欧式距离代替曼哈顿距离发现同样是26步，可以知道26步是该情况解的最优解。
浅谈人工智能中的启发式搜索策略
一、启发式策略
启发式策略是指在解决复杂问题时，根据人的经验和技巧来寻求最优解的方法。
它是人工智能领域中的一种和规划技术，可以解决形式化的各种问题。
启发式策略广泛应用于机器学习、图形图计算、机器人控制和计算机图形学等多种领域。
启发式策略包括：A*算法、B*树算法、启发式和动态规划等。
A*算法是一种非常有效的启发式方法，它采用了一个启发函数来估计待访问节点的最优价值，从而可以根据最小价值节点而进行，的效果比较好。
B*树算法是一种静态的启发式方法，该算法在每一步都可以通过比较不同节点价值来确定最优路径，从而更有效地出最优路径。
启发式和动态规划都是一种在状态空间中采取其中一种方法或策略以获得最优解的技术，两者最大的不同点在于，启发式依赖于当前状态，动态规划则更倾向于最终目标。
二、应用
启发式策略广泛应用于人工智能领域，它可以用来解决各种形式化问题，如游戏、自然语言处理问题等。
人工智能a算法
人工智能中的A算法是一种启发式搜索算法，也被称为A算法。
它利用估
价函数f(n)=g(n)+h(n)对Open表中的节点进行排序，其中g(n)是从起始
节点到当前节点n的实际代价，h(n)是从当前节点n到目标节点的估计代价。
A算法在搜索过程中会优先选择估价值最小的节点进行扩展，这样可以更有效地逼近目标节点，提高搜索效率。
A算法可以根据搜索过程中选择扩展节点的范围，将其分为全局择优搜索算法和局部择优搜索算法。
全局择优搜索算法会从Open表的所有节点中选择一个估价值最小的节点进行扩展，而局部择优搜索算法仅从刚生成的子节点中选择一个估价值最小的节点进行扩展。
A算法的搜索过程可能包括以下步骤：
1. 把初始节点S0放入Open表中，计算其估价值f(S0)=g(S0)+h(S0)。
2. 如果Open表为空，则问题无解，算法失败退出。
3. 把Open表的第一个节点取出放入Closed表，并记该节点为n。
4. 考察节点n是否为目标节点。
若是，则找到了问题的解，算法成功退出。
5. 若节点n不可扩展，则转到第2步。
6. 扩展节点n，生成子节点ni(i=1,2,…… )，计算每一个子节点的估价值f(ni) (i=1,2,……)。
7. 把子节点放入Open表中，并根据估价值进行排序。
8. 重复步骤2-7，直到找到目标节点或Open表为空。
总之，人工智能中的A算法是一种有效的人工智能搜索策略，它可以用于解决许多不同的问题，例如路径规划、机器人控制、游戏AI等。
人工智能的分支之启发式算法
启发式算法（Heuristic Algorithm）是人工智能的一个重要分支，主要用于求解复杂优化问题。
它基于直观或经验构造，能够在可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个可行解，但该可行解与最优解的偏离程度一般不能被预计。
启发式算法以仿自然体算法为主，主要有蚁群算法、模拟退火法、神经网络等。
启发式算法的主要特点是可以利用问题自身的一些特征信息（启发式信息）来指导搜索的过程，从而可以缩小搜索范围，提高搜索效率。
这种方法注重在近似解空间中进行搜索，能够快速找到较好的结果，但并不能保证找到最优解。
因此，在具体应用时需要考虑各个参数和随机性对算法效果的影响，并根据实际问题和需求选择适当的启发式算法。
启发式算法在组合优化、约束优化、排队论、路径规划、生产调度等领域中得到了广泛应用，并被证明在某些情况下能够为问题提供更好的解决方案。
总的来说，启发式算法是人工智能领域中的一种重要技术，它通过模拟人类或自然界中的智慧和经验来寻找问题的最优解，为解决复杂问题提供了一种有效的途径。
<B style='color:black;background-color:#ffff66'>浅谈</B>人工智能中的启发式搜索策略<B style='color:black;background-color:#ffff66'>浅谈</B>人工智能中的启发式搜索策略关键词:人工智能;启发式搜索;估价函数摘要:人工智能所要解决的问题大部分是非结构化或结构不良的问题,启发式搜索可以极大提高效率。
讲述了搜索策略中的启发式搜索,对它的原理进行讲解,前景进行了展望。
盲目搜索即是按预定的控制策略进行搜索[1],这种搜索具有盲目性,效率不高,不便于复杂问题的求解。
为解决此类问题,人们提出启发式搜索策略,即在搜索中加入与问题有关的启发式信息,用以指导搜索朝着最有希望的方向前进,加速问题求解的效率并找到最优解。
一、启发式搜索策略的发展历史40年代:由于实际需要,提出了启发式算法,具有快速有效的特点。
50年代:启发式搜索逐步繁荣,其中贪婪算法和局部搜索得到人们的关注。
60年代:反思阶段,人们发现以前提出的启发式算法速度很快,但是解的质量不稳定,而且对大规模的问题仍然无能为力。
70年代:计算复杂性理论的提出。
人们发现贪婪算法和局部搜索算法速度快,但解不好的原因是得到的解没有全局最优性。
Holland的遗传算法的出现再次引发了人们研究启发式算法的兴趣。
80年代以后,模拟退火算法,人工神经网络,禁忌搜索等新式算法相继出现。
二、启发式搜索策略的工作原理盲目式搜索求解的过程中,节点的扩展次序是随意的,且没有利用已解决问题的特性,为此需要扩展的节点数会非常大。
启发式搜索则克服了上述缺点,它利用搜索过程中的有用信息优化搜索。
一一般搜索过程基本思想[2]:把初始结点作为当前状态,选择适用的算符对其进行操作,生成一组子状态,然后检查目标状态是否在其中出现。
<B style='color:black;background-color:#ffff66'>浅谈</B>人工智能中的启发式搜索策略<B style='color:black;background-color:#ffff66'>浅谈</B>人工智能中的启发式搜索策略关键词:人工智能;启发式搜索;估价函数摘要:人工智能所要解决的问题大部分是非结构化或结构不良的问题,启发式搜索可以极大提高效率。
讲述了搜索策略中的启发式搜索,对它的原理进行讲解,前景进行了展望。
盲目搜索即是按预定的控制策略进行搜索[1],这种搜索具有盲目性,效率不高,不便于复杂问题的求解。
为解决此类问题,人们提出启发式搜索策略,即在搜索中加入与问题有关的启发式信息,用以指导搜索朝着最有希望的方向前进,加速问题求解的效率并找到最优解。
一、启发式搜索策略的发展历史40年代:由于实际需要,提出了启发式算法,具有快速有效的特点。
50年代:启发式搜索逐步繁荣,其中贪婪算法和局部搜索得到人们的关注。
60年代:反思阶段,人们发现以前提出的启发式算法速度很快,但是解的质量不稳定,而且对大规模的问题仍然无能为力。
70年代:计算复杂性理论的提出。
人们发现贪婪算法和局部搜索算法速度快,但解不好的原因是得到的解没有全局最优性。
Holland的遗传算法的出现再次引发了人们研究启发式算法的兴趣。
80年代以后,模拟退火算法,人工神经网络,禁忌搜索等新式算法相继出现。
二、启发式搜索策略的工作原理盲目式搜索求解的过程中,节点的扩展次序是随意的,且没有利用已解决问题的特性,为此需要扩展的节点数会非常
大。
启发式搜索则克服了上述缺点,它利用搜索过程中的有用信息优化搜索。
一一般搜索过程基本思想[2]:把初始结点作为当前状态,选择适用的算符对其进行操作,生成一组子状态,然后检查目标状态是否在其中出现。
若出现,则搜索成功,否则从已生成的状态中再选一个状态作为当前状态。
重复上述过程,直到目标状态出现或者不再有可供操作的状态和算符时为止。
在给出具体过程之前,首先介绍两个数据结构――OPEN表和CLOSED表。
OPEN表用于存放刚生成的节点。
CLOSED表用于存放将要扩展或者已经扩展的节点。
搜索的一般过程如下: 1.把初始节点S0放入OPEN表,并建立目前只包含S0的图,记为G。
2.检查OPEN表是否为空,若为空则问题无解,退出。
3.把OPEN表的第一个节点取出放入到CLOSED 表,并记该节点为节点n。
4.考察节点n是否为目标节点。
若是,则求得了问题的解,退出。
5.扩展节点n,生成一组子节点。
把其中不是节点n先辈的那些子节点记作集合M,并把这些子节点作为节点n的子节点加入到G中。
6.针对M中子节点的不同情况,分别进行如下处理:①对于那些未曾在G中出现过的M成员设置一个指向父节点即节点n 的指针,并把他们放入OPEN表中;②对于那些先前已在G中出现过的M成员,确定是否需要修改指向父节点的指针;
③对于那些先前已在G中出现并且已经扩展了M的成员,确定是否需要修改其后继节点指向父节点的指针。
7.按某种搜索策略对OPEN表中的节点进行排序。
8.转向2步。
由以上介绍可知,问题的求解过程实际上就是搜索过程,问题的求解的状态空间
图是通过搜索逐步形成的,边搜索边形成,而且搜索每前进一步,就要检查一下是否到达了目标状态,这样就可尽量少生成与问题无关的状态,即节省了存储空间,又提高了求解效率。
二估价函数用于估价节点重要性的函数称为估价函数[3],其一般形式为:f x g x +h x ,g x 为从初始节点S0到节点x已经实际付出的代价;h x 是从节点x到目标节点Sg的最优路径的估计代价,它体现了问题的启发性信息,其形式要根据问题的特性确定。
例如,它可以是节点x到节点的距离,也可以是处于最优路经上的概率等;h x 称为启发函数。
估价函数f x 表示从初始节点经过节点x到目标节点的最优路径的代价估价值,它的作用是估价OPEN表中各节点的重要程度,决定它们在OPEN表中的次序。
其中g x 指出了搜索的横向趋势,它有利于搜索的完备性,但影响搜索的效率。
如果我们只关心到达目标节点的路径,并且希望有较高的搜索效率,则g x 可以忽略,但此时会影响搜索的完备性,因此,在确定f x 时,要权衡各种利弊得失,使g x 与h x 各占适当的比重。
三、小结启发式搜索算法是一种很实用、很有效的算法,比如SA算法具有对初始点的不依赖性,可以任意选取初始解和随机序列,应用广泛。
SA普及的最重要的原因是能在复杂的情况下产生更高质量的解,因此,它特别适用于非线性和复杂的系统。
在多目标优化领域,SA还处于起步阶段,在种群选择以及如何与Pareto前沿结合等方面,还需要进一步地研究,SA具有广阔的发展前景。
参考文献: [1]George F.Luger著,史忠植,张银奎译.人工智能[M].北京:机械工业出版社,2004 [2]田中.人工智
能中搜索策略的探讨[J].福建电脑,2004, 08 :30-31 [3]王万森.智能原理及其应用第2版 [M].北京:电子工业出版社,2007 摘要：本文提出了将“C程序设计”教学分成引导入门、实践提高、实
际应用三个阶段进行，每个阶段均有不同的学习任务和内容，并根据
不同阶段的特点选用不同的教学方法。
分段教学能使学生在具备扎实
的基础知识的同时，又具备解决实际问题的能力。
关键词本文
来自：计算机毕业网：建构主义；分段教学；“C程序设计”教学
信息社会对计算机专业的学生提出了更高的要求：不仅要会使用编程
工具，而且要能应用编程工具解决实际问题。
然而，传统的程序设计
教学方法过多地关注语言细节而缺乏对学生程序设计方法和能力的
训练，并在一个人为简化了的教学环境下传授知识，不利于知识迁移，
因此出现了学生学完了程序设计课程却不会编程的现象。
如何使学生
具备扎实的基础知识，同时又具备解决实际问题能力，是目前亟待解
决的问题。
建构主义因其倡导的有意义学习，被越来越多的教
师用于指导程序设计课程的教学，并塑造了一些教学运作的新方式[1]。
但建构主义理论本身还在不断完善和发展中，建构主义在程序
设计教学实践中的应用还有待进一步的探讨。
1建构主义
教学观实际教学中倾向于选择建构主义教学观还是传统
教学观，应该根据学生的认知规律与教学内容特点而定。
传统
教学观与建构主义教学观处于一个系统的两个极端[2]。
传统教学观
不太强调学习者内在的条件，认为外在知识的内容和结构能完全复制
到学生的头脑中，为了减少学习者的混乱而简化了真理；建构主义则处于另一个极端，强调学习者，认为学习是对学习者已有概念重新调整的过程，强调提供丰富多彩的学习环境以利于技能的迁移。
以教师为中心的传统教学观忽视了学习者对知识的主动建构，忽视了发展学习者的高阶思维能力。
尽管传统教学观遭到批判，但它依然是广大教师使用最广泛的教学模式之一，有其存在的价值。
传统的讲授法是一种高效的形式和方法，有利于基础知识和基本技能的系统传授，并能最大限度地发挥教师的主控作用，教学操作性强，适合学习者初级阶段的发展水平。
建构主义教学观越来越受到普遍的关注。
建构主义在知识观、学习观、教学观、师生关系观和信息技术应用观等方面提出了与传统教学观不同的观点，有利于促进学习者高阶学习和高阶能力。
它与当前我国教育理念改革和教育信息化的发展方向是一致的。
对于初学程序设计的大学一年级新生，因为没有建立有效的计算机模型，适于在较为简单的、限制的环境中，循序渐进地建立关于程序设计的基本概念。
此阶段主要采用传统教学方法，帮助初学者较快地建立有效的计算机模型。
当学生不再对计算机感到困惑时，应该由传统教学方法逐步过渡到建构主义教学方法，所呈现的教学情景越来越接近真实问题的环境，从而使学生分析问题、用编程工具解决问题的能力得到越来越多的训练。
根据“C程序设计”教学内容的特点及学生认知能力的发展过程，教学可分3个阶段，分别选用不同的教学方法进行见表1 。
2分阶段选用不同的教学方法 2.1引导入门阶段对于刚接触程序设
计的初学者来说，本阶段的任务是快速建立有效的计算机模型，掌握程序的基本构成及常用算法模式，掌握用计算机检验所学知识的方法，为后继阶段的学习作积累。
主要学习的内容包括：程序基本构成，控制结构，简单函数。
上机实践内容主要是学习使用编程环境，验证和熟悉语法，熟悉常用算法模式，会用计算机来验证语言知识，分析程序的执行。
教学一开始就应将课程的整体框架引入，让学生有个整体的概念和学习目标。
“概念图”、“思维导图”之类的图形化工具有助于概念知识的表达，可以用于整体框架的引入，也可用于评价学生的学习。
课堂教学中，主要学习程序的阅读与分析。
通过已编好的难度合适的程序将枯燥的数据类型、运算符等基本概念引入课堂，通过问题的解决来研究语法的结构、功能和使用效果；研究各部分代码的来龙去脉，形成完整的程序结构；研究常见算法模式与编程技巧。
同时也。
