第4章 图搜索策略

图搜索策略112----⎧⎪⎧⎪⎨⎪⎩⎪⎪⎧⎪⎪⎪⎪⎪⎨⎨⎪⎪⎪⎩⎪⎪⎪⎪⎪⎧⎪⎨⎪⎩⎩⎧⎪⎨⎪⎩一、图搜索概论：①，树的定义和基本术语，图的意义②，图的存储结构2，图的定义1，顶点,2，边,③，显示图的常用术图搜索回顾3，图,4，数据元素隐式图术语，子集树，，排列树二、状态图搜索：①，搜索定义②，搜索树定义广度优先盲目穷举式深度优先有界深度优先全局择优1，树式搜索局部择优分启发式状态图搜索③，搜索方式分类*--A --121*2 4A ⎧⎧⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎩⎩⎪⎧⎪⎧⎪⎨⎪⎪⎩⎪⎨⎪⎧⎪⎪⎨⎪⎪⎩⎩⎩⎧⎧⎧⎪⎪⎨⎨⎪⎩⎨⎪⎪⎩⎪⎩A Beam Search 支界限最近择优算法算法随机碰撞盲目回溯穷举2，线式搜索不回溯启发式可回溯深度优先搜索穷举式搜索，盲目搜索广度优先搜索④，搜索策略盲目碰撞搜索，启发式搜索，⑤搜搜寻算法，3，二分取中查索法找算法算， ⎧⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎩⎩Branch and bound1 2⎧⎨⎩⎧⎨⎩1，猴子与香蕉三，简单实例回顾：2，猴子与香蕉的状态空间图，图搜索一般过程四，图搜索过程，图搜索框过程框图五，通过文章加深图搜索策略（《人工智能图搜索策略的研究》）一，图搜索概论：①图搜索回顾：1.11.2②图的存储结构：1.11.2③图及其术语：1.11.2显示图与隐式图：1.3，显示图的常用术语：1.4隐式图术语二，状态图搜索：①，搜索定义，②，搜索树定义：③，搜索方式分类：④图搜索策略：1.1盲目式搜索：1.2启发式搜索：⑤图搜索算法1.1树搜索方法1.3树搜索举例1.4状态图搜索：1.5状态图搜索举例⑥，常见搜索算法下面是一些比较重要的算法，原文罗列了32个，但我觉得有很多是数论里的或是比较生僻的，和计算机的不相干，所以没有选取。

《人工智能》课程教学大纲课程代码：H0404X课程名称：人工智能适用专业：计算机科学与技术专业及有关专业课程性质：本科生专业基础课（学位课）主讲教师：中南大学信息科学与工程学院智能系统与智能软件研究所蔡自兴教授总学时：40学时（课堂讲授36学时，实验教学4学时）课程学分：2学分预修课程：离散数学，数据结构一. 教学目的和要求：通过本课程学习，使学生对人工智能的发展概况、基本原理和应用领域有初步了解，对主要技术及应用有一定掌握，启发学生对人工智能的兴趣，培养知识创新和技术创新能力。

人工智能涉及自主智能系统的设计和分析，与软件系统、物理机器、传感器和驱动器有关，常以机器人或自主飞行器作为例子加以介绍。

一个智能系统必须感知它的环境，与其它Agent和人类交互作用，并作用于环境，以完成指定的任务。

人工智能的研究论题包括计算机视觉、规划与行动、多Agent系统、语音识别、自动语言理解、专家系统和机器学习等。

这些研究论题的基础是通用和专用的知识表示和推理机制、问题求解和搜索算法，以及计算智能技术等。

此外，人工智能还提供一套工具以解决那些用其它方法难以解决甚至无法解决的问题。

这些工具包括启发式搜索和规划算法，知识表示和推理形式，机器学习技术，语音和语言理解方法，计算机视觉和机器人学等。

通过学习，学生能够知道什么时候需要某种合适的人工智能方法用于给定的问题，并能够选择适当的实现方法。

二. 课程内容简介人工智能的主要讲授内容如下：1.叙述人工智能和智能系统的概况，列举出人工智能的研究与应用领域。

2.研究传统人工智能的知识表示方法和搜索推理技术，包括状态空间法、问题归约法谓词逻辑法、语义网络法、盲目搜索、启发式搜索、规则演绎算法和产生式系统等。

3.讨论高级知识推理，涉及非单调推理、时序推理、和各种不确定推理方法。

4.探讨人工智能的新研究领域，初步阐述计算智能的基本知识，包含神经计算、模糊计算、进化计算和人工生命诸内容。

湖北省高等教育自学考试课程考试大纲课程名称：人工智能导论课程代码：07844第一部分课程性质与目标一、课程性质与特点人工智能导论是电子信息工程专业的必修核心课程。

本课程系统阐述了人工智能的基本理论、基本方法和基本技术。

本课程是人工智能方向的引导性课程，对后续在人工智能领域的进一步研究工作和软件实践奠定良好的基础。

二、课程目标与基本要求人工智能导论是理论性较强，涉及知识面较广，方法和技术较复杂的一门学科。

通过对本课程的学习，学生应掌握人工智能的一个问题和三大技术，即通用问题求解和知识表示技术、搜索技术、推理技术。

学生在较坚实打好的人工智能数学基础上，能够利用这些数学手段对确定性和不确定性的知识完成推理；理解问题求解的状态空间法，能应用几种主要的盲目搜索和启发式搜索算法完成问题求解；熟悉几种重要的不确定推理方法，利用数值分析中常用方法进行正确计算。

认识机器学习对于智能软件研制的重要性，掌握机器学习的相关概念，机器学习的方法及其相应的学习机制，几个典型的机器学习系统的学习方法、功能和领域应用。

三、与本专业其他课程的关系与本课程相关的课程有：数字图像处理、计算机信息处理等专业课程。

第二部分考核内容与考核目标第1章概述一、学习目的与要求本章包括人工智能研究目标、研究内容、研究的途径（方法）、研究的领域等内容。

通过对本章的学习，学生应理解什么是智能、理解什么是人工智能、人工智能研究的目标、人工智能研究的内容、人工智能研究的途径，了解人工智能研究的历史和研究领域。

二、考核知识点与考核目标（一）人工智能定义；人工智能的技术特征；（重点）识记：（1）人工智能的定义；理解：（1）人工智能的技术特征；（二）专家系统和知识工程（次重点）识记：（1）专家系统的定义；理解：（1）知识工程的主要研究内容；（三）人工智能应用系统（一般）理解：（1）人工智能的研究领域和应用领域；第2章用搜索求解问题的基本原理一、学习目的与要求通过对本章的学习，了解搜索求解问题的基本思路，掌握实现搜索过程的三大要素，理解通过搜索求解问题的方法，理解问题特征分析方法。

第一章人工智能：主要研究如何用人工的方法和技术,使用各种自动化机器或智能机器（主要指计算机）模仿、延伸和扩展人的智能,实现某些机器思维或脑力劳动自动化。

为什么要研究人工智能：1）普通计算机智能低下，不能满足社会需求。

2)研究人工智能也是当前信息化社会的迫切需求。

3）智能化是自动化发展的必然趋势。

4）研究人工智能,对人类自身智能的奥秘也提供有益帮助。

远期目标是要制造智能机器。

具体讲就是使计算机具有看、听、说、写等感知和交互能力，具有联想、学习、推理、理解、学习等高级思维能力，还要有分析问题解决问题和发明创造的能力。

近期目标：是实现机器智能。

即先部分地或某种程度地实现机器智能，从而使现有的计算机更灵活好用和更聪明有用。

人工智能的研究内容1)搜索与求解2）学习与发现3)知识与推理4)发明与创造5)感知与交流6）记忆与联想7）系统与建造8）应用与工程研究途径与方法：1)心理模拟,符号推演法就是以人脑的心理模型为依据，将问题或知识表示成某种逻辑网络，采用符号推演的方法,实现搜索、推理、学习等功能，从宏观上来模拟人脑的思维,实现人工智能.2)生理模拟,神经计算就是用人工神经元组成的人工神经网络来作为信息和知识的载体，用称为神经计算的方法实现学习、记忆、联想、识别和推理等功能，从而来模拟人脑的智能行为,使计算机表现出某种智能。

3）行为模拟,控制进化是一种基于感知－行为模型的研究途径和方法,它是在模拟人在控制过程中的智能活动和行为特性，如自适应，自寻优、自学习、自组织等，来研究和实现人工智能。

4)群体模拟，仿生计算模拟生物群落的群体智能行为，从而实现人工智能.5)博采广鉴，自然计算就是模仿或借鉴自然界的某种机理而设计计算模型，这类计算模型通常是一类具有自适应、自组织、自学习、自寻优能力的算法.6)原理分析，数学建模就是通过对智能本质和原理的分析,直接采用某种数学方法来建立智能行为模型.人工智能的基本技术1）表示a符号智能的表示是知识表示b计算智能的表示一般是对象表示2)运算a符号智能的运算是基于知识表示的推理或符号操作b计算智能的运算是基于对象表示的操作或计算3)搜索a符号智能在问题空间内搜索进行问题求解b计算智能在解空间搜索进行求解第三章1广度优先搜索的特点广度优先中OPEN表是一个队列，CLOSED表是一个顺序表，表中各节点按顺序编号，正被考察的节点在表中编号最大，广度优先策略是完备的广度优先搜索策略与问题无关，具有通用性.缺点搜索效率低。

第4章搜索策略参考答案4.5 有一农夫带一条狼，一只羊和一框青菜与从河的左岸乘船倒右岸，但受到下列条件的限制：(1) 船太小，农夫每次只能带一样东西过河；(2)如果没有农夫看管，则狼要吃羊，羊要吃菜。

请设计一个过河方案，使得农夫、浪、羊都能不受损失的过河，画出相应的状态空间图。

题示：(1) 用四元组（农夫，狼，羊，菜）表示状态，其中每个元素都为0或1，用0表示在左岸，用1表示在右岸。

(2) 把每次过河的一种安排作为一种操作，每次过河都必须有农夫，因为只有他可以划船。

解：第一步，定义问题的描述形式用四元组S=（f，w，s，v）表示问题状态，其中，f，w，s和v分别表示农夫，狼，羊和青菜是否在左岸，它们都可以取1或0，取1表示在左岸，取0表示在右岸。

第二步，用所定义的问题状态表示方式，把所有可能的问题状态表示出来，包括问题的初始状态和目标状态。

由于状态变量有4个，每个状态变量都有2种取值，因此有以下16种可能的状态：S0=(1,1,1,1)，S1=(1,1,1,0)，S2=(1,1,0,1)，S3=(1,1,0,0)S4=(1,0,1,1)，S5=(1,0,1,0)，S6=(1,0,0,1)，S7=(1,0,0,0)S8=(0,1,1,1)，S9=(0,1,1,0)，S10=(0,1,0,1)，S11=(0,1,0,0)S12=(0,0,1,1)，S13=(0,0,1,0)，S14=(0,0,0,1)，S15=(0,0,0,0)其中，状态S3，S6，S7，S8，S9，S12是不合法状态，S0和S15分别是初始状态和目标状态。

第三步，定义操作，即用于状态变换的算符组F由于每次过河船上都必须有农夫，且除农夫外船上只能载狼，羊和菜中的一种，故算符定义如下：L(i)表示农夫从左岸将第i样东西送到右岸（i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除农夫外不载任何东西）。

由于农夫必须在船上，故对农夫的表示省略。