《人工智能导论》第一章 绪论
本文是中国人工智能学会编著的《人工智能导论（面向非计算机专业）》第一章的摘要与笔记，仅供个人学习之用。其它章节请访问下列相应URL。第一章绪论（本章）第二章概念表示第三章知识表示
章节目录第一章绪论1.1人工智能的起源和定义 1.1.1人工智能的起源 1.1.2人工智能的定义1.2人工智能的流派概念的定义概念的功能1.2.1符号主义1.2.2连接主义1.2.3行为主义1.3人工智能的进展和发展趋势第一章绪论1.1人工智能的起源和定义 1.1.1人工智能的起源现代人工智能的起源公认是1956年的达特茅斯会议。
1.1.2人工智能的定义时至今日，还没有一个被大家一致认同的精确的人工智能定义。
但目前最常见的AI定义有两个： ①一个是明斯基提出的，即“人工智能是一门科学，是使用机器做那些人需要通过智能来做的事情”； ②另一个更专业一些的定义是尼尔森给出的，即“人工智能是关于知识的科学”，所谓“知识的科学”就是研究知识的表示、知识的获取和知识的运用。
在这两个定义中，专业人士更偏向于第二个定义。原因很简单，因为第一个定义中涉及两个未明确定义的概念，一个是人，一个是智能。什么是人？什么是智能？到现在依然是很难清楚回答的问题。相比之下，第二个定义只涉及一个未明确定义的概念，就是知识。在人、智能、知识三个概念当中，知识被研究的应该是比较彻底的。同时，人和智能的定义也与知识紧密相关，而且知识是智能的基础。如果没有任何知识，很难发现什么是智能。
1.2人工智能的流派根据前面的论述，我们知道要理解人工智能就要研究如何在一般的意义上定义知识。可惜的是准确定义知识也是一个十分复杂的事情。
但关于知识，至少有一点是明确的，那就是知识的基本单位是概念。精通掌握一门知识，必须从这门知识的基本概念开始学习。而知识自身也是一个概念。
据此，人工智能的问题就变成了如下三个问题——如何定义（或者表示）一个概念、如何学习一个概念、如何应用一个概念。
概念的定义经典概念的定义由三部分组成：第一部分是概念的符号表示，即概念的名称，说明这个概念叫什么，简称概念名；第二部分是概念的内涵表示，由命题来表示，命题就是能判断真假的陈述句；第三部分是概念的外延表示，由经典集合来表示，用来说明与概念对应的实际对象是哪些。
概念定义的组成{概念的符号表示概念的内涵表示概念的外延表示概念定义的组成egin{cases}概念的符号表示\概念的内涵表示\概念的外延表示end{cases}概念定义的组成⎩⎪⎨⎪⎧概念的符号表示概念的内涵表示概念的外延表示
举一个常见的经典概念的例子——素数。其概念名在汉语中为“素数”，在英语中为“primenumber”；其内涵表示是一个命题：只能够被1和自身整除的自然数；其外延表示是一个经典集合：{1，2，3，5，7，11，13，17，…}。
概念的功能很容易发现，经典概念定义的三部分各有其作用，且彼此不能互相代替。具体来说，概念有三个作用或功能，要掌握一个概念，必须清楚其三个功能。
第一个功能是概念的指物功能，即指向客观世界的对象，表示客观世界的对象的可观测性。
举一个《阿Q正传》里的例子：那赵家的狗，何以看我两眼呢？句子中“赵家的狗”应该是指现实世界当中的一条真正的狗。但概念的指物功能有时不一定能够实现，有些概念其设想存在的对象在现实世界并不存在，例如“鬼”。
第二个功能是指心功能，即指向人心智世界里的对象，代表心智世界里的对象表示。概念的指心功能一定存在。如果对于某一个人，一个概念的指心功能没有实现，则该词对于该人不可见，简单说，该人不理解该概念。
鲁迅有一篇著名的文章《论丧家的资本家的乏走狗》，显然，这个“狗”不是现实世界的狗，只是他心智世界中的狗，即心里的狗（在客观世界，梁实秋先生显然无论如何不是狗）。
最后一个是指名功能，即向认知世界或者符号世界表示对象的符号名称，这些符号名称组成各种语言。
最著名的例子是乔姆斯基的“colorlessgreenideassleepfuriously”，这句话翻译过来是“无色的绿色思想在狂怒地休息”。这句话没有什么意思，但是完全符合语法，纯粹是在语义符号世界里，即仅仅指向符号世界而已。
概念的功能{指名功能指物功能指心功能概念的功能egin{cases}指名功能\指物功能\指心功能end{cases}概念的功能⎩⎪⎨⎪⎧指名功能指物功能指心功能
知道了概念的三个功能之后，就可以理解人工智能的三个流派以及各流派之间的关系。人工智能也是一个概念，而要使一个概念成为现实，自然要实现概念的三个功能。人工智能的三个流派关注于如何才能让机器具有人工智能，并根据概念的不同功能给出了不同的研究路线。
专注于实现AI指名功能的流派称为符号主义；专注于实现AI指心功能的流派称为连接主义；专注于实现AI指物功能的流派称为行为主义。1.2.1符号主义符号主义提出了物理符号系统假设：只要在符号计算上实现了相应的功能，那么在现实世界就实现了对应的功能，这是智能的充分必要条件。
著名的“图灵测试”就是在符号层面进行的。有了图灵测试，我们就可以将研究的重点放在智能的外在功能性表现上，使智能在工程上看似乎是可以实现和判断的。
但在指名功能里实现了概念的功能，并不能说明一定实现了概念的功能。实际上，根据指名与指物的不同，哲学家Searle专门设计了著名的“中文屋实验”用来批判图灵测试。这是哲学上对符号主义的一个正式批评，明确指出了按照符号主义实现的人工智能不等同于人的智能。
1.2.2连接主义连接主义认为大脑是一切智能的基础，主要关注于大脑神经元及其连接机制，试图发现大脑的结构及其处理信息的机制、揭示人类智能的本质机理，进而在机器上实现相应的模拟。
按照这条路，连接主义认为可以实现完全的人工智能。对此，哲学家普特南设计了著名的“缸中之脑”实验，可以看作是对连接主义的一个哲学批判。缸中之脑实验说明即使连接主义实现了，指心没有问题，但指物依然存在严重问题。因此，连接主义实现的人工智能也不等同于人的智能。
尽管如此，连接主义仍是目前最为大众所知的一条AI实现路线。在围棋上，采用了深度学习技术的AlphaGo战胜了李世石，之后又战胜了柯洁。在机器翻译上，深度学习技术已经超过了人翻译的水平。在语音识别和图像识别上，深度学习也已经达到了实用水准。客观地说，深度学习的研究已经取得了工业级的进展。
1.2.3行为主义行为主义假设智能取决于感知和行动，不需要知识、表示和推理，只需要将智能行为表现出来就好，即只要能实现指物功能就可以认为具有智能了。
对此，哲学家普特南也设计了“完美伪装者和斯巴达人”实验，可以看作是对行为主义的哲学批判。因此，行为主义路线实现的人工智能也不等同于人的智能。
1.3人工智能的进展和发展趋势简单地说，人工智能三大流派假设之所以能够成立的前提是指名、指物、指心功能等价。然而，在现实生活中概念的指名、指物与指心功能并不等价，单独实现概念的一个功能并不能保证具有智能。因此，单独遵循一个学派不足以实现人工智能，现在的人工智能研究已经不再强调人工智能的单一学派。很多时候会综合各个流派的技术。
在围棋上战胜人类顶尖棋手的AlphaGo综合使用了三种学习算法——强化学习（行为主义）、蒙特卡罗树搜索（符号主义）、深度学习（连接主义）。
目前的人工智能还有很大的缺陷，其使用的知识表示还是建立在经典概念的基础之上。经典概念的基本假设还是指名、指物与指心等价，这与人类的日常生活经验严重不符，过于简单化了。因此，在经典概念表示不成立的情况下，如何进行概念表示是一个极具挑战性的问题。
《人工智能导论》第三章 知识表示
本文是中国人工智能学会编著的《人工智能导论（面向非计算机专业）》第三章的摘要与笔记，仅供个人学习之用。其它章节请访问下列相应URL。第一章绪论第二章概念表示第三章知识表示（本章）
章节目录第三章3.1知识与知识表示的概念3.1.1知识的概念3.1.2知识的特性3.1.3知识表示的概念3.2产生式表示法3.2.1产生式3.2.2产生式系统3.2.3产生式系统的特点3.3框架表示法3.3.1框架的一般结构3.3.2用框架表示知识的例子3.4状态空间表示法3.4.1状态空间表示3.4.2状态空间的图描述第三章人类的智能活动主要是获得并运用知识。知识是智能的基础。为了使计算机具有智能，能模拟人类的智能行为，就必须使它具有知识。但人类的知识需要用适当的模式表示出来，才能存储到计算机中并能够被运用。因此，知识的表示称为人工智能中一个十分重要的研究课题。
3.1知识与知识表示的概念3.1.1知识的概念知识是人们在长期的生活及社会实践中、在科学研究及实验中积累起来的对客观世界的认识与经验。人们把实践中获得的信息关联在一起，就形成了知识。一般来说，把有关信息关联在一起所形成的信息结构称为知识。（知识是一种信息结构。作为一种结构，很容易联想到能否用某种数据结构来表示知识。这个问题在以下“知识表示”部分探讨） 信息之间有多种关联形式，其中用得最多的是一种用“如果……，则……”表示的关联形式。在人工智能中，这种知识被称为“规则”，它反映了信息之间的某种因果关系。
例如，我国北方的人们经过多年的观察发现，每当冬天即将来临，就会看到一批批的大雁向南方飞去，于是把“大雁向南飞”与“冬天就要来临了”这两个信息关联在一起，得到了如下知识：如果大雁向南飞，则冬天就要来临了。 又如，“雪是白色的”也是一条知识，它反映了“雪”与“白色”之间的一种关系。在人工智能中，这种知识被称为“事实”。
3.1.2知识的特性1.相对正确性
知识是人类对客观世界认识的结晶，并且受到长期实践的检验。因此，在一定的条件及环境下，知识是正确的。*这里，“一定的条件及环境”是必不可少的，它是知识正确性的前提。因为任何知识都是在一定的条件及环境下产生的，因而也就只有在这种条件及环境下才是正确的。*知识的这一特性称为相对正确性。
例如，1+1=2，这是一条妇孺皆知的正确知识，但它也只是在十进制的前提下才是正确的；如果是二进制，它就不正确了。
在人工智能中，知识的相对正确性更加突出。除了人类知识本身的相对正确性外，在建造专家系统时，为了减少知识库的规模，通常将知识限制在所求解问题的范围内。也就是说，只要这些知识对所求解的问题是正确的就行。
例如，在后面介绍的动物识别系统中，因为仅仅识别虎、金钱豹、斑马、长颈鹿、企鹅、鸵鸟、信天翁七种动物，所以知识“IF该动物是鸟AND善飞，则该动物是信天翁”就是正确的。
2.不确定性
由于现实世界的复杂性，信息可能是精确的，也可能是不精确的、模糊的；关联可能是确定的，也可能是不确定的。这就使知识并不总是只有“真”与“假”两种状态，而是在“真”与“假”之间存在许多中间状态，即存在为“真”的程度问题。知识的这一特性称为不确定性。
造成知识具有不确定性的原因是多方面的，主要有：
①由随机性引起的不确定性。由随机事件所形成的知识不能简单地用“真”或“假”来刻画，它是不确定的。
例如，“如果头痛且流涕，则有可能患了感冒”这条知识，虽然大部分情况是患了感冒，但有时候具有“头痛且流涕”的人不一定都是“患了感冒”。其中的“有可能”实际上就是反映了“头痛且流涕”与“患了感冒”之间的一种不确定的因果关系。因此，它是一条具有不确定性的知识。
②由模糊性引起的不确定性。由于某些事物客观上存在的模糊性，使得人们无法把两个类似的事物严格区分开来，不能明确地判定一个对象是否符合一个模糊概念；又由于某些事物之间存在着模糊关系，使得我们不能准确地判定它们之间地关系究竟是“真”还是“假”。像这样由模糊概念、模糊关系所形成的知识显然是不确定的。
例如，“如果张三长得很帅，那么他一定很受欢迎”，这里的“长得很帅”“很受欢迎”都是模糊的。
③由经验引起的不确定性。人们对客观世界的认识是逐步提高的，只有在积累了大量的感性认识后才能升华到理性认识的高度，形成某种知识。因此，知识有一个逐步完善的过程。在此过程中，或者由于客观事物表露得不够充分，致使人们对它的认识不够全面；或者对充分表露的事物一时抓不住本质，使人们对它的认识不够准确。这种认识上的不完全、不准确必然导致相应的知识是不准确的、不确定的。不完全性是使知识具有不确定性的一个重要原因。
3.可表示性与可利用性
知识的可表示性是指知识可以用适当的形式表示出来，如用语言、文字、图形、神经网络等，这样才能被存储、传播。知识的可利用性是指知识可以被利用。这是不言而喻的，我们每个人天天都在利用自己掌握的知识来解决各种问题。
3.1.3知识表示的概念知识表示（knowledgerepresentation）就是将人类知识形式化或者模型化。 知识表示的目的是能够让计算机存贮和运用人类的知识。下面先介绍常用的产生式、框架、状态空间知识表示方法，其他（如神经网络等）几种知识表示方法将在后面章节结合其应用再介绍。
3.2产生式表示法产生式表示法又称产生式规则（productionrule）表示法。“产生式”这一术语是由美国数学家波斯特（E.Post）在1943年首先提出来的，如今已经被应用于多领域，成为人工智能中应用最多的一种知识表示方法。
3.2.1产生式产生式通常用于表示事实、规则以及它们的不确定性度量，适合于表示事实性知识和规则性知识。
1.确定性规则的产生式表示 确定性规则的产生式表示的基本形式是IF P THEN QIF\\P\\THEN\\QIF P THEN Q 或者P→QP→QP→Q 其中，PPP是产生式的前提，用于指出该产生式是否可用的条件；QQQ是一组结论或操作，用于指出当前提PPP所指示的条件满足时，应该得出的结论或者应该执行的操作。整个产生式的含义是：如果前提PPP被满足，则结论QQQ成立或执行所规定的操作。
例如：r4: IF 动物会飞 AND 会下蛋 THEN 该动物是鸟r_4:\\IF\\动物会飞\\AND\\会下蛋\\THEN\\该动物是鸟r4: IF 动物会飞 AND 会下蛋 THEN 该动物是鸟 就是一个产生式。其中r4r_4r4是该产生式的编号；“动物会飞AND会下蛋”是前提PPP；“该动物是鸟”是结论QQQ。
2.不确定性规则的产生式表示 不确定性规则的产生式表示的基本形式是IF P THEN Q (置信度)IF\\P\\THEN\\Q\\(置信度)IF P THEN Q (置信度) 或者P→Q (置信度)P→Q\\(置信度)P→Q (置信度)
例如，在专家系统MYCIN中有这样一条产生式：IF 本微生物的染色斑是革兰氏阴性 AND 本微生物的形状呈杆状 AND 病人是中间宿主 THEN 该微生物是绿脓杆菌 (0.6)IF\\本微生物的染色斑是革兰氏阴性\\AND\\本微生物的形状呈杆状\\AND\\病人是中间宿主\\THEN\\该微生物是绿脓杆菌\\(0.6)IF 本微生物的染色斑是革兰氏阴性 AND 本微生物的形状呈杆状 AND 病人是中间宿主 THEN 该微生物是绿脓杆菌 (0.6) 它表示当前前提中列出的各个条件都得到满足时，结论“该微生物是绿脓杆菌可以相信的程度为0.6。这里，用0.6表示知识的强度。
3.确定性事实的产生式表示 确定性事实一般用三元组表示(对象，属性，值)(对象，属性，值)(对象，属性，值) 或者(关系，对象1，对象2)(关系，对象1，对象2)(关系，对象1，对象2)
例如，“老李年龄是40岁”表示为(Li,Age,40)(Li,Age,40)(Li,Age,40)，“老李和老王是朋友”表示为(Friend,Li,Wang)(Friend,Li,Wang)(Friend,Li,Wang)。
4.不确定性事实的产生式表示 不确定性事实一般用四元组表示(对象，属性，值，置信度)(对象，属性，值，置信度)(对象，属性，值，置信度) 或者(关系，对象1，对象2，置信度)(关系，对象1，对象2，置信度)(关系，对象1，对象2，置信度)
例如，“老李年龄很可能是40岁”表示为(Li,Age,40,0.8)(Li,Age,40,0.8)(Li,Age,40,0.8)，“老李和老王不大可能是朋友”表示为(Friend,Li,Wang,0.1)(Friend,Li,Wang,0.1)(Friend,Li,Wang,0.1)。这里用置信度0.1表示可能性比较小。
产生式又称为规则或产生式规则；产生式的“前提”有时又称为“条件”“前提条件”“前件”“左部”等；其“结论”部分有时称为“后件”或“右部”等。
3.2.2产生式系统把一组产生式放在一起，让它们相互配合、协同作用，一个产生式生成的结论可以供另一个产生式作为已知事实使用，以求得问题的解，这样的系统称为产生式系统。 一般来说，一个产生式系统由规则库、综合数据库、控制系统（推理机）三部分组成。它们之间的关系如图3.1所示。1.规则库 用于描述相应领域内知识的产生式集合称为规则库。
显然，规则库是产生式系统求解问题的基础。因此，需要对规则库中的知识进行合理的组织和管理，检测并排除冗余及矛盾的知识，保持知识的一致性。采用合理的结构形式，可使推理避免访问那些与求解当前问题无关的知识，从而提高求解问题的效率。
2.综合数据库 综合数据库又称为事实库、上下文、黑板等，用于存放问题的初始状态、原始证据、推理中得到的中间结论及最终结论等信息。当规则库中某条产生式的前提可与综合数据库的某些已知事实匹配时，该产生式就被激活，并把它推出的结论放入综合数据库中作为后面推理的已知事实。显然，综合数据库的内容是不断变化的。
3.推理机 推理机由一组程序组成，除了推理算法，还控制整个产生式系统的运行，实践对问题的求解。粗略地说，推理机要做以下几项工作：
①推理。按一定的策略从规则库中选择与综合数据库中的已知事实进行匹配。所谓匹配是指把规则的前提条件与综合数据库中的已知事实进行比较，如果两者一致或者近似一致且满足预先规定的条件，则称匹配成功，相应的规则可被使用；否则称为匹配不成功。
②冲突消解。如果匹配成功的规则不止一条，称为“发生了冲突”。此时，推理机必须调用相应的解决冲突的策略进行消解，以便从匹配成功的规则中选出一条执行。
③执行规则。如果某一规则的右部是一个或多个结论，则把这些结论加入综合数据库中；如果规则的右部是一个或多个操作，则执行这些操作。对于不确定性知识，在执行每一条规则时还要按一定的算法计算结论的不确定性程度。
④检查推理终止条件。检查综合数据库中是否包含了最终结论，决定是否停止系统运行。
3.2.3产生式系统的特点产生式系统适合于表达具有因果关系的过程性知识，是一种非结构化的知识表示方法。产生式表示法既可以表示确定性知识，又可以表示不确定性知识；既可表示启发式知识，又可表示过程性知识。目前，已建造成功的专家系统大部分用产生式来表达其过程性知识。
用产生式表示具有结构关系的知识很困难，因为它不能把具有结构性关系的事物间的区别与联系表示出来。但下面介绍的框架表示法可以解决这一问题。
3.3框架表示法3.3.1框架的一般结构框架（frame)是一种描述所论对象（一个事物、事件或概念）属性的数据结构。
一个框架由若干个被称为“槽（slot）”的结构组成，每一个槽又可根据实际情况划分为若干个“侧面（facet）”。一个槽用于描述所论对象某一方面的属性。一个侧面用于描述相应属性的一个方面。槽和侧面所具有的属性值分别被称为槽值和侧面值。在一个用框架表示知识的系统中一般都含有多个框架，一个框架一般都含有多个不同槽、不同侧面，分别用不同的框架名、槽名及侧面名表示。对于框架、槽或侧面，都可以为其附加上一些说明性的信息，一般是一些约束条件，用于指出什么样的值才能填入到槽和侧面中去。
下面给出框架的一般表示形式： 由上述表示形式可以看出，一个框架可以有任意有限数目的槽；一个槽可以有任意有限数目的侧面；一个侧面可以有任意有限数目的侧面值。槽值或侧面值既可以是数值、字符串、布尔值，也可以是一个满足某个给定条件时要执行的动作或过程，还可以是另一个框架的名字，从而实现一个框架对另一个框架的调用，表示框架之间的横向关系。约束条件是任选的，当不指出约束条件时，表示没有约束。
3.3.2用框架表示知识的例子下面据一些例子，说明建立框架的基本方法。
例3.1教师框架
框架名： 姓名：单位（姓、名） 年龄：单位（岁） 性别：范围（男、女），缺省：男 职称：范围（教授、副教授、讲师、助教），缺省：讲师 部门：单位（系、教研室） 住址： 工资： 开始工作时间：单位（年、月） 截止时间：单位（年、月），缺省：现在
该框架共有九个槽，分别描述了“教师”九个方面的情况，或者说关于“教师”的九个属性。在每个槽里都指出了一些说明性的信息，用于对槽的填值给出某些限制。
对于上述这个框架，当把具体的信息填入槽或侧面后，就得到了相应框架的一个事例框架。例如，把某教师的一组信息填入“教师”框架的各个槽，就可得到：
框架名： 姓名：夏冰 年龄：36 性别：女 职称：副教授 部门：计算机系软件教研室 住址： 工资： 开始工作时间：1988.9 截止时间：1996.7
3.4状态空间表示法3.4.1状态空间表示状态空间（statespace）是利用状态变量和操作符号表示系统或问题的有关知识的符号体系。状态空间可以用一个四元组表示：(S,O,S0,G)(S,O,S_0,G)(S,O,S0,G) 其中，SSS是状态集合，SSS中每一元素表示一个状态，状态是某种结构的符号或数据。O是操作算子的集合，利用算子可将一个状态转换为另一个状态。S0S_0S0是问题的初始状态的集合，是S的非空子集，即S0⊂SS_0subsetSS0⊂S。GGG是问题的目的状态的集合，是SSS的非空子集，即G⊂SGsubsetSG⊂S。GGG可以是若干具体状态，也可以是满足某种性质的路径信息描述。
从S0S_0S0结点到GGG结点的路径称为求解路径。求解路径上的操作算子序列为状态空间的一个解。例如，操作算子序列O1,...,OkO_1,...,O_kO1,...,Ok使初始状态转换为目标状态：S0→O1S1→O2S2→O3...→OkGS_0xrightarrow{O_1}S_1xrightarrow{O_2}S_2xrightarrow{O_3}...xrightarrow{O_k}GS0O1S1O2S2O3...OkG则O1,...,OkO_1,...,O_kO1,...,Ok即为状态空间的一个解。当然，解往往不是唯一的。
任何类型的数据结构都可以用来描述状态，如符号、字符串、向量、多维数组、树和表格等。所选用的数据结构形式要与状态所蕴含的某些特性具有相似性。如对于八数码问题，一个3×33 imes33×3的陈列便是一个合适的状态描述方式。
例3.3八数码问题的状态空间表示 八数码问题（重排九宫问题）是在一个3×33 imes33×3的方格上，放有1~8的数码，另一格为空。空格四周上下左右的数码可移到空格。需要解决的问题是如何找到一个数码移动序列使初始的无序数码转变为一些特殊的排列。例如，图3.4所示的八数码问题的初始状态(a)为问题的一个布局，需要找到一个数码移动序列使初始布局(a)转变为目标布局(b)。23158467 12384765egin{array}{|c|c|c|}hline2&3&1\hline5&&8\hline4&6&7\hlineend{array}spacespacespacespacespacespacespacespaceegin{array}{|c|c|c|}hline1&2&3\hline8&&4\hline7&6&5\hlineend{array}25436187 18726345(a)初始状态 (b)目标状态(a)初始状态spacespacespacespacespacespacespace(b)目标状态(a)初始状态 (b)目标状态图3.4 八数码问题图3.4\八数码问题图3.4 八数码问题 该问题可以用状态空间来表示。此时八数码的任何一种摆法就是一个状态，所有的摆法即为状态集SSS，它们构成了一个状态空间，其数目为9!9!9!。而GGG是指定的某个或某些状态，例如图3.4(b)。 对于操作算子设计，如果着眼在数码上，相应的操作算子就是数码的移动，其操作算子共有4(方向)×8(数码)=324(方向) imes8(数码)=324(方向)×8(数码)=32个。如着眼在空格上，即空格在方格盘上的每个可能位置的上下左右移动，其操作算子可简化成4个：①将空格向上移Up；②将空格向左移Left；③将空格向下移Down；④将空格向右移Right。 移动时要确保空格不会移出方格盘之外，因此并不是在任何状态下都能运用这4个操作算子。如空格在方盘格的右上角时，只能运用两个操作算子——向左移Left和向下移Down。
3.4.2状态空间的图描述状态空间可用有向图来描述，图的节点表示问题的状态，图的弧表示状态之间的关系。初始状态对应于实际问题的已知信息，是图中的根结点。在问题的状态空间描述中，寻找从一种状态转换为另一种状态的某个操作算子序列等价于在一个图中寻找某一路径。 如图3.5所示为用有向图描述的状态空间。该图表示对状态S0S_0S0允许使用操作算子O1O_1O1，O2O_2O2及O3O_3O3，分别使S0S_0S0转换为S1S_1S1，S2S_2S2及S3S_3S3。这样一步步利用操作算子转换下去，如S10∈GS_{10}inGS10∈G，则O2O_2O2，O6O_6O6，O10O_{10}O10就是一个解。 上面是较为形式化的说明，下面再以八数码问题为例，介绍具体问题的状态空间的有向图描述。
例3.5对于八数码问题，如果给出问题的初始状态，就可以用图来描述其状态空间。其中的弧可用4个操作算子来标注，即空格向上移Up、向左移Left、向下移Down、向右移Right。改图的部分描述如图3.6所示。
上面两个例子中，只绘出了问题的部分状态空间图。对于许多实际问题，要在有限的时间内绘出问题的全部状态图是不可能的。因此，要研究能够在有限时间内搜索到较好解的搜索算法。
《人工智能导论》第三章：通过搜索对问题求解(笔记二)
第三章通过搜索对问题求解一.问题求解Agent二.问题实例三.树搜索算法四.无信息搜索策略（必考知识）4.1宽度优先搜索4.2一致代价搜索！！！4.3深度优先搜索4.4深度受限搜索！！！4.5迭代加深的深度优先搜索！！！五.有信息(启发式)的搜索策略5.1最佳优先搜索!!!5.2一致代价搜索-分支定界法5.3A搜索5.4A*搜索三个感叹！表重点一.问题求解Agent搜索为一种求解问题的一般方法。搜索问题：已知一个问题的初始状态和目标状态，找到一个操作序列，使得问题的状态能从初始状态转移到目标状态。最优搜索问题：获得的操作序列不仅是问题的解，而且使得总代价最低。搜索问题特点：（1）初始状态确定（2）当前状态是否为目标转态是可检测的（3）状态空间离散（4）每个状态可以采取的合法行动和相应后继状态是确定的（5）环境是静态的（6）路径代价函数是已知的典序搜索问题（1）八数码难题（2）旅行售货员问题搜索问题四个要素：（1）初始状态（2）后继函数：某个行动输入给定状态，可以输出相应的后继状态（3）目标测试：给定状态是否为目标状态（4）路径代价函数：状态转移所需的代价搜索中需要解决的基本问题：（1）是否一定能找到一个解。（2）找到的解是否是最佳解。（3）时间与空间复杂性如何。（4）是否终止运行了或是否会陷入一个死循环。搜索的主要过程：（1）从初始或目的状态出发，并将它作为当前状态。（2）扫描操作的算子集，将适用当前状态的一些操作算子作用于当前状态而得到新的状态，并建立指向其父结点的指针。（3）检查所生成的新状态是否满足结束状态，如果满足，则得到问题的一个解，并可沿着有关指针从结束状态反向到达开始状态，给出解答的路径；否则，将新状态作为当前状态，返回第(2)步再进行搜索。搜索策略盲目搜索启发式搜索在不具有对特定问题的任何有关信息的条件下，按固定的步骤（依次或随机调用操作算子）进行的搜索。考虑特定问题领域可应用的知识，动态地确定调用操作算子的步骤，优先选择较适合的操作算子，尽量减少不必要的搜索，以求尽快地到达结束状态。按搜索方向进行分类：(1)数据驱动：从初始状态出发的正向搜索。正向搜索——从问题给出的条件出发。(2)目的驱动：从目的状态出发的逆向搜索。逆向搜索：从想达到的目的入手，看哪些操作算子能产生该目的，以及应用这些操作算子产生目的时需要哪些条件。(3)双向搜索：从开始状态出发作正向搜索，同时又从目的状态出发作逆向搜索，直到两条路径在中间的某处汇合为止。二.问题实例实例：Romania（1）已知条件：一个agent在罗马尼亚度假，目前位于Arad城市，Agent明天有航班从Bucharest起飞，不能改签退票（2）（3）真空吸尘器三.树搜索算法基本思路：从初始状态/已知状态开始，通过行动不断地探索其他状态直到找到目标状态(成功)或者没有行动可执行为止(失败)。树表示（1）根节点：初始状态（2）连线：行动（3）结点：状态空间中的状态算法性能评价标准（1）完备性：如果问题有解时，这个算法是否能保证找到解？（2）最优性：能否找到最优解（3）时间复杂度：找到解需要花费多长时间（4）空间复杂度：在执行搜索的过程中需要多少内存时间空间复杂度的度量：（1）时间由搜索过程中产生的结点数目来度量（2）空间由内存中存储的最多结点数量来度量（通常小于状态空间数量|V|+|E|）四.无信息搜索策略（必考知识）无信息搜索：除了问题定义中提供的状态信息外没有任何附加信息，算法只能区分状态是不是目标状态，无法比较非目标状态的好坏。
4.1宽度优先搜索思想：先扩展根结点，再扩展根结点的所有后继，然后再扩展它们的后继。实现：FIFO队列缺点：内存需求大，时间复杂度高4.2一致代价搜索！！！定义：扩展未扩展结点中代价最小的实现：队列按照代价从小到大排列4.3深度优先搜索思想：首先扩展最深的为扩展结点实现：用LIFO队列(栈)来存储结点4.4深度受限搜索！！！对于深度为d+1，分支数为b的情况，深度受限的搜索算法产生的结点数为：N(DLS)=b0+b1+…+bd4.5迭代加深的深度优先搜索！！！1.结合了宽度优先和深度优先的优点2.对于深度为d+1，分支数为b的情况，迭代加深的深度优先算法产生的结点数为：N(IDS)=(d+1)+(d)b+(d-1)*b2+….+(1)bd
五.有信息(启发式)的搜索策略无信息搜索的缺点：（1）广度优先搜索在进一步深入搜索之前先检查了靠近跟的节点，存储空间需求过高，很容易就被中等大小的分支因子给压垮了，例如分支因子=4（一个节点有四个孩子），则k层总共（4^k-1）/3个节点。（2）深度优先搜索（3）在求解"组合爆炸"的问题时，搜索空间增长太快(如从9！变成16！,！为阶乘)，以至于盲目搜索方法无法成功。启发法：一种解决问题的方法，这种方法通过尝试来证明结果，是**“凭经验"或"试错法”**的学习方式。（1）是一个提高复杂问题解决效率的实用策略，它引导程序沿着一条最可能的路径到达解，忽略最没有希望的路径，能避免去检查死角。（2）只使用已收集的数据。（3）可以减少结点数目，适合组合复杂度快速增长的问题（4）好的启发式方法不能保证获得解，但是它们经常有助于引导人们达到解的路径。5.1最佳优先搜索!!!基本思路：通过对每一个结点计算评价函数f(n)值,找到一个f(n)最低的未扩散的结点实现：在队列中，结点按照评价函数值从低到高排序。（大多数评价函数由启发函数h构成，h(n):结点n到目标结点的最小代价估计值）最佳优先搜索实现需要open表和closed表，open表中节点按照节点接近目标状态的启发式估计值进行顺序排列，过程中不保留重复状态。伪代码//最佳优先搜索BestFirstSearch(Root_Node,goal){建open表，将根节点插入open表;while(open表不为空){从open表中取出最前节点放在节点G中(同时加入closed表);if(G是目标节点)return从根节点到G节点一条路径;while(G是子节点){if(子节点不在open表中)将子节点插入open表;else将具有最小估计值的子节点放入open表，删除其他节点;}将open表中节点按值排序;//最小值节点在最前}return失败;}分类：贪婪最佳优先搜索罗马尼亚问题首先扩展与目标结点估测距离最近的结点使用两点之间的直线距离来估测两点之间的实际距离罗马尼亚问题例子:5.2一致代价搜索-分支定界法是不采用剩余距离的启发式搜索，只计算已经走过的部分，h(n)处处为0。按照递增的代价制定搜索路径，搜索的估计成本为：f(n)=g(n)结束条件：其它路径（未到达目标节点）的代价大于or等于当前最优的路径代价。伪代码//分支定界搜索Branch_Bound(Root_Node,goal){创建open表;将根节点插入open表;while(open表不为空){取出open表中第一个元素放入结点G;if(G是目标结点)return到G的路径else将G结点子节点插入open表;按照从根节点到当前节点的路径长度对open表排序;}return失败;}例子：一致代价搜索和最佳优先搜索都是通过启发函数排最优值，它们的区别如下最佳优先搜索一致代价搜索优先值为结点到终点的估计值优先值为结点到起点的真实值估价函数为h(n)估价函数为g(n)5.3A搜索是最佳搜索和一致优先的混合搜索算法，既考虑与源点的真实距离又兼顾与目标点距离的预估值。评价函数f(n)=g(n)+h(n)g(n)=到达结点n已经花费的代价h(n)=结点n到目标节点的评估代价f(n)=通过结点n到达目标结点的总评估代价伪代码B_B_Estimata(Root_Node,goal){创建open表;将根节点插入open表;while(open表不为空){取出open表中第一个元素放入结点G;if(G是目标结点)return到G的路径else将每个子节点的估计距离加到当前距离;将节点G的子节点插入open表按照路径长度对open表排序;}return失败;}例子最佳优先搜索、一致搜索及A算法均****没有对估价函数f(n)做任何限制**5.4A*搜索1.A*算法是最优A搜索算法，其是对估价函数加上一些限制后得到的一种启发式搜索算法。2.伪代码
A*Search(Root_Node,goal){创建open表;将根节点插入open表;while(open表不为空){取出open表中第一个元素放入结点G,并标记G已被访问;if(G是目标结点)return到G的路径else将每个子节点的估计距离加到当前距离;将节点G的子节点中之前未访问过的节点插入open表按照路径长度对open表排序;}return失败;}