人工智能第六章——约束满足问题（CSP）
摘要本文会讲清楚：1）什么是CSP（约束满足问题）2）约束传播与局部相容性3）CSP形式化为一个搜索问题（回溯法）4）如何提高搜索效率（变量/值的顺序，提前检查失败等）
一、CSP使用要素化来描述状态：一组变量，每个变量有自己的值。当每个变量都有自己的赋值同时满足所有关于变量的约束时，问题就得到了解决。这类问题就叫做约束满足问题（CSP），全称ConstraintSatisfactionProblem。
CSP利用了状态结构的优势，使用的是通用策略而不是问题专业启发式来求解复杂问题。
主要思想：通过识别违反约束的变量/值的组合迅速消除大规模的搜索空间。
1.2定义CSPCSP包含三个成分X,D,C：X：变量集合（variables）D：值域集合，每个变量有自己的值域（domain）C：描述变量取值的约束集合（constraint）
C的形式一般是：
1.3CSP的优点图1.3.1CSP的优点对比局部搜索（全分配，每次必须考虑整个状态），但是CSP，是部分分配，每次只需要考虑部分赋值。（一旦不是解，立即丢弃）
1.4CSP的形式化用约束语言来表示CSP的约束条件。一元约束：只限制单个变量的取值二元约束：与两个变量有关。
变量个数任意的约束称为全局约束。
图1.4.1约束优化问题（COP）二、约束传播核心思想：局部相容性。
2.1节点相容单个变量（对应一个节点）值域中的所有取值满足它的一元约束，就是节点相容的。
2.2弧相容如果CSP中某变量值域中所有取值满足该变量所有二元约束，则此变量弧相容。
比如：对变量X1，X2，如果D1中每个数值在D2中都存在一些数值满足弧（X1，X2）的二元约束，那么X1相对X2是弧相容的。
如果每个变量相对其他变量都是弧相容的，则称该网络是弧相容的。
图2.2.1弧相容算法AC-32.3路径相容弧相容可能缩小变量的值域，有时甚至还能找到解（每各变量值域大小都为1时），或者有时发现CSP无解（一些变量的值域大小=0）。
但是弧相容也会失败（比如澳大利亚地图着色问题，如果只有两种颜色，弧相容意义不大），所以才要用更强的相容概念。
路径相容：观察变量得到隐式约束，并以此来加强二元约束。
图2.3.1路径相容的定义2.4k-相容如果对于任何k-1个变量的相容赋值，第k个变量总能被赋予一个和前k-1个变量相容的值，那么这个CSP就是k相容的。
三、全局约束1）Alldiff约束：表示所有相关变量必须取不同的值。2）atmost约束（另一个重要的高阶约束）：也叫资源约束。
如果对于每个变量X和它的取值上下界，每个变量Y都存在某个取值满足X和Y之间的约束，则称该CSP是边界相容（此边界传播广泛应用于实际CSP）。
四、CSP的回溯搜索很多CSP只用推理是无法求解的，还需要通过搜索来求解。
部分赋值的回溯搜索算法：可以用标准的深度优先搜索，状态可能是部分赋值，行动是将var=value加入到赋值中。
回溯搜索用于深度优先搜索中，每次为一个变量选一个赋值，没有合法的值的时候就回溯。
图4.1CSP的简单回溯算法五、有效解决CSP5.1变量和取值顺序变量：1）选择“合法”取值最少的变量——称为最少剩余值（MRV）启发式。（做一个强有力的引导，方便提早遇到失败，从而剪枝）2）度启发式：通过选择与其他未赋值变量约束最多的变量来试图降低未来的分支因子。（用来打破僵局，如选择第一个着色区域）
值：最少约束至：优先选择的赋值是给邻居变量留下更多的选择（为了找到一个解，所以没必要排序，二十要最少约束）
5.2搜索与推理交错进行前向检验：只要变量X被赋值，就对它进行弧相容检查，对每个通过约束与X相关的未赋值变量Y，从Y值域中删去与X不相容的值。
5.3智能回溯：向后看主要概念：前向检验；冲突集；回跳
六、CSP的局部搜索局部搜索算法对求解许多CSP都是很有效的。它们使用完整状态的形式化：初始状态是给每个变量都赋一个值，搜索过程是一次改变一个变量的取值。
七、文末诗词满恨游丝兼落絮。红杏开时，一霎（sha，四声）清明雨。浓睡觉来莺乱语。惊残好梦无寻处。——晏殊《蝶恋花·六曲阑干偎碧树》
人工智能——状态空间搜索及状态空间表示法
朋友们，如需转载请标明出处：人工智能AI技术的博客_CSDN博客-python系列教程,人工智能,程序人生领域博主
1. 搜索
搜索（Search），设法在庞大状态空间图中找到目标。
主要分为两类性质的搜索：
基本搜索，是一种没有任何经验和知识起作用的、由某种规则所确定的非智能性的搜索；启发式搜索（HeuristicSearch）：其特点在于是一种有准备的、追求效率而有的放矢的智能搜索，它要求依据某种知识及信息的指导，通过逐一状态比较而找到符合规定条件的目标状态解。2. 问题的状态空间图搜索
问题的状态空间可用有向图来表达，又常称其为状态树(StateTree)。图中，节点Sk表示状态，状态之间的连接采用有向弧(Arc)，弧上标以操作数OK来表示状态之间的转换关系。
图1问题求解的状态树表示
用状态空间法搜索求解问题:
首先要把待求解的问题表示为状态空间图;
把问题的解表示为目标节点Sg。
求解就是要找到从根节点S0到达目标节点Sg的搜索路径。
状态空间图在计算机中有两种存储方式：一种是图的显式存储，另一种是图的隐式存储。
3. 状态空间表示法
状态空间
状态，描述某一类事物在不同时刻所处于的信息状况
操作，描述状态之间的关系
问题的状态空间可用一个三元序组来表示：
：问题的全部初始状态的集合
：操作的集合
：目标状态的集合
利用状态空间图求解的具体思路和步骤：
（1）设定状态变量及确定值域；
（2）确定状态组，分别列出初始状态集和目标状态集；
（3）定义并确定操作集；
（4）估计全部状态空间数，并尽可能列出全部状态空间或予以描述之；
（5）当状态数量不是很大时，按问题的有序元组画出状态空间图，依照状态空间图搜索求解。
传教士和野人问题（TheMissionariesandCannibalsProblem）
在河的左岸有三个传教士、一条船和三个野人，传教士们想用这条船将所有的成员都运过河去，但是受到以下条件的限制：
①教士和野人都会划船，但船一次最多只能装运两个；
②②在任何岸边野人数目都不得超过传教士，否则传教士就会遭遇危险：被野人攻击甚至被吃掉。
此外，假定野人会服从任何一种过河安排，试规划出一个确保全部成员安全过河的计划。
（1）设定状态变量及确定值域。
为了建立这个问题的状态空间，设左岸传教士数为m，则
m={0,1,2,3}；
对应右岸的传教士数为3－m； 左岸的野人数为c，则有
c={0,1,2,3}；
对应右岸野人数为3－c；左岸船数为b，故又有b={0,1}，右岸的船数为1－b.
（2）确定状态组，分别列出初始状态集和目标状态集。
问题的状态可以用一个三元数组来描述，以左岸的状态来标记，即
Sk=（m,c,b），
右岸的状态可以不必标出。
初始状态一个： S0=（3,3,1），初始状态表示全部成员在河的左岸；
目标状态也只一个： Sg=（0,0,0），表示全部成员从河左岸渡河完毕。
（3）定义并确定操作集。
仍然以河的左岸为基点来考虑，把船从左岸划向右岸定义为Pij操作。其中,第一下标i表示船载的传教士数,第二下标j表示船载的野人数；同理，从右岸将船划回左岸称之为Qij操作，下标的定义同前。则共有10种操作，操作集为
F={P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20}
（4）估计全部的状态空间数，并尽可能列出全部的状态空间或予以描述之。
在这个问题世界中，S0=（3,3,1）为初始状态，S31=Sg=（0,0,0）为目标状态。全部的可能状态共有32个，如表所示。
表1传教士和野人问题的全部可能状态
注意：按题目规定条件，应划去非法状态，从而加快搜索效率。
1）首先可以划去左岸边野人数目超过传教士的情况，即S4、S8、S9、S20、S24、S25等6种状态是不合法的；
2）应划去右岸边野人数目超过修道士的情况，即S6、S7、S11、S22、S23、S27等情况；
3）应划去4种不可能出现状态：划去S15和S16——船不可能停靠在无人的岸边；划去S3——传教士不可能在数量占优势的野人眼皮底下把船安全地划回来；划去S28——传教士也不可能在数量占优势的野人眼皮底下把船安全地划向对岸。可见，在状态空间中，真正符合题目规定条件的只有16个合理状态。
（5）当状态数量不是很大时，按问题的有序元组画出状态空间图，依照状态空间图搜索求解。
根据上述分析，共有16个合法状态和允许的操作，可以划出传教士和食人者问题的状态空间图，如图所示。
图2传教士和野人问题的状态空间
任何一条从S0到达S31的路径都是该问题的解。
人工智能中的搜索算法
下一节→←上一节人工智能中的搜索算法搜索算法是人工智能最重要的领域之一。本主题将解释有关AI中搜索算法的所有信息。
问题解决代理：在人工智能中，搜索技术是通用的问题解决方法。AI中的理性代理或问题解决代理主要使用这些搜索策略或算法来解决特定问题并提供最佳结果。问题解决代理是基于目标的代理并使用原子表示。在本主题中，我们将学习各种解决问题的搜索算法。
搜索算法术语：搜索：搜索是在给定搜索空间中解决搜索问题的逐步过程。搜索问题可能具有三个主要因素：
搜索空间：搜索空间表示系统可能具有的一组可能的解决方案。
开始状态：这是代理开始搜索的状态。
目标测试：观察当前状态并返回是否达到目标状态的函数。
搜索树：搜索问题的树表示称为搜索树。搜索树的根是初始状态对应的根节点。
动作：它向代理提供所有可用动作的描述。
转换模型：对每个动作做什么的描述，可以表示为转换模型。
路径成本：它是一个函数，它为每条路径分配一个数字成本。
解：它是一个从起始节点到目标节点的动作序列。
最优解：如果一个解在所有解中成本最低。
搜索算法的特性：以下是搜索算法的四个基本属性，用于比较这些算法的效率：
完整性：如果搜索算法保证在任何随机输入至少存在任何解决方案时返回解决方案，则称该搜索算法是完整的。
最优性：如果保证为算法找到的解决方案是所有其他解决方案中的最佳解决方案（最低路径成本），那么这种解决方案就称为最优解决方案。
时间复杂度：时间复杂度是算法完成其任务的时间度量。
空间复杂度：它是搜索过程中任何一点所需的最大存储空间，作为问题的复杂度。
搜索算法的类型根据搜索问题，我们可以将搜索算法分为无信息（Blindsearch）搜索和有信息搜索（Heuristicsearch）算法。
不知情/盲目搜索：无信息搜索不包含任何领域知识，例如接近度、目标位置。它以蛮力方式运行，因为它只包含有关如何遍历树以及如何识别叶节点和目标节点的信息。无信息搜索是一种搜索树的搜索方式，在搜索树中没有任何关于搜索空间的信息，如初始状态算子和测试目标，因此也称为盲搜索。它检查树的每个节点，直到达到目标节点。
它可以分为五种主要类型：
广度优先搜索
统一成本搜索
深度优先搜索
迭代深化深度优先搜索
双向搜索
知情搜索知情搜索算法使用领域知识。在知情搜索中，问题信息可用于指导搜索。有信息的搜索策略可以比无信息的搜索策略更有效地找到解决方案。知情搜索也称为启发式搜索。
启发式方法可能并不总是保证获得最佳解决方案，但可以保证在合理的时间内找到一个好的解决方案。
知情搜索可以解决许多其他方式无法解决的复杂问题。
知情搜索算法的一个例子是旅行商问题。
贪婪搜索
A*搜索
恭喜你，领取到一张面值0元的优惠券只有购买全集内容0.00元，才可抵扣使用。有效期截止于：2020-12-1223:59是否立即使用？上一主题没有了下一主题无信息搜索算法使用社交账号登录,本站支持全部评论(0)人工智能领域技术，主要包含了哪些核心技术
从语音识别到智能家居，从人机大战到无人驾驶，人工智能的“演化”给我们社会上的一些生活细节，带来了一次又一次的惊喜，未来更多智能产品依托的人工智能技术会发展成什么样呢?让我们来看看2018人工智能标准化白皮书里面，对人工智能关键技术的定义。
人工智能技术关系到人工智能产品是否可以顺利应用到我们的生活场景中。在人工智能领域，它普遍包含了机器学习、知识图谱、自然语言处理、人机交互、计算机视觉、生物特征识别、AR/VR七个关键技术。
一、机器学习
机器学习(MachineLearning)是一门涉及统计学、系统辨识、逼近理论、神经网络、优化理论、计算机科学、脑科学等诸多领域的交叉学科，研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使之不断改善自身的性能，是人工智能技术的核心。基于数据的机器学习是现代智能技术中的重要方法之一，研究从观测数据(样本)出发寻找规律，利用这些规律对未来数据或无法观测的数据进行预测。根据学习模式、学习方法以及算法的不同，机器学习存在不同的分类方法。
根据学习模式将机器学习分类为监督学习、无监督学习和强化学习等。
根据学习方法可以将机器学习分为传统机器学习和深度学习。
二、知识图谱
知识图谱本质上是结构化的语义知识库，是一种由节点和边组成的图数据结构，以符号形式描述物理世界中的概念及其相互关系，其基本组成单位是“实体—关系—实体”三元组，以及实体及其相关“属性—值”对。不同实体之间通过关系相互联结，构成网状的知识结构。在知识图谱中，每个节点表示现实世界的“实体”，每条边为实体与实体之间的“关系”。通俗地讲，知识图谱就是把所有不同种类的信息连接在一起而得到的一个关系网络，提供了从“关系”的角度去分析问题的能力。
知识图谱可用于反欺诈、不一致性验证、组团欺诈等公共安全保障领域，需要用到异常分析、静态分析、动态分析等数据挖掘方法。特别地，知识图谱在搜索引擎、可视化展示和精准营销方面有很大的优势，已成为业界的热门工具。但是，知识图谱的发展还有很大的挑战，如数据的噪声问题，即数据本身有错误或者数据存在冗余。随着知识图谱应用的不断深入，还有一系列关键技术需要突破。
三、自然语言处理
自然语言处理是计算机科学领域与人工智能领域中的一个重要方向，研究能实现人与计算机之间用自然语言进行有效通信的各种理论和方法，涉及的领域较多，主要包括机器翻译、机器阅读理解和问答系统等。
机器翻译
机器翻译技术是指利用计算机技术实现从一种自然语言到另外一种自然语言的翻译过程。基于统计的机器翻译方法突破了之前基于规则和实例翻译方法的局限性，翻译性能取得巨大提升。基于深度神经网络的机器翻译在日常口语等一些场景的成功应用已经显现出了巨大的潜力。随着上下文的语境表征和知识逻辑推理能力的发展，自然语言知识图谱不断扩充，机器翻译将会在多轮对话翻译及篇章翻译等领域取得更大进展。
语义理解
语义理解技术是指利用计算机技术实现对文本篇章的理解，并且回答与篇章相关问题的过程。语义理解更注重于对上下文的理解以及对答案精准程度的把控。随着MCTest数据集的发布，语义理解受到更多关注，取得了快速发展，相关数据集和对应的神经网络模型层出不穷。语义理解技术将在智能客服、产品自动问答等相关领域发挥重要作用，进一步提高问答与对话系统的精度。
问答系统
问答系统分为开放领域的对话系统和特定领域的问答系统。问答系统技术是指让计算机像人类一样用自然语言与人交流的技术。人们可以向问答系统提交用自然语言表达的问题，系统会返回关联性较高的答案。尽管问答系统目前已经有了不少应用产品出现，但大多是在实际信息服务系统和智能手机助手等领域中的应用，在问答系统鲁棒性方面仍然存在着问题和挑战。
自然语言处理面临四大挑战：
一是在词法、句法、语义、语用和语音等不同层面存在不确定性;
二是新的词汇、术语、语义和语法导致未知语言现象的不可预测性;
三是数据资源的不充分使其难以覆盖复杂的语言现象;
四是语义知识的模糊性和错综复杂的关联性难以用简单的数学模型描述，语义计算需要参数庞大的非线性计算
四、人机交互
人机交互主要研究人和计算机之间的信息交换，主要包括人到计算机和计算机到人的两部分信息交换，是人工智能领域的重要的外围技术。人机交互是与认知心理学、人机工程学、多媒体技术、虚拟现实技术等密切相关的综合学科。传统的人与计算机之间的信息交换主要依靠交互设备进行，主要包括键盘、鼠标、操纵杆、数据服装、眼动跟踪器、位置跟踪器、数据手套、压力笔等输入设备，以及打印机、绘图仪、显示器、头盔式显示器、音箱等输出设备。人机交互技术除了传统的基本交互和图形交互外，还包括语音交互、情感交互、体感交互及脑机交互等技术。
五、计算机视觉
计算机视觉是使用计算机模仿人类视觉系统的科学，让计算机拥有类似人类提取、处理、理解和分析图像以及图像序列的能力。自动驾驶、机器人、智能医疗等领域均需要通过计算机视觉技术从视觉信号中提取并处理信息。近来随着深度学习的发展，预处理、特征提取与算法处理渐渐融合，形成端到端的人工智能算法技术。根据解决的问题，计算机视觉可分为计算成像学、图像理解、三维视觉、动态视觉和视频编解码五大类。
目前，计算机视觉技术发展迅速，已具备初步的产业规模。未来计算机视觉技术的发展主要面临以下挑战：
一是如何在不同的应用领域和其他技术更好的结合，计算机视觉在解决某些问题时可以广泛利用大数据，已经逐渐成熟并且可以超过人类，而在某些问题上却无法达到很高的精度;
二是如何降低计算机视觉算法的开发时间和人力成本，目前计算机视觉算法需要大量的数据与人工标注，需要较长的研发周期以达到应用领域所要求的精度与耗时;
三是如何加快新型算法的设计开发，随着新的成像硬件与人工智能芯片的出现，针对不同芯片与数据采集设备的计算机视觉算法的设计与开发也是挑战之一。
六、生物特征识别
生物特征识别技术是指通过个体生理特征或行为特征对个体身份进行识别认证的技术。从应用流程看，生物特征识别通常分为注册和识别两个阶段。注册阶段通过传感器对人体的生物表征信息进行采集，如利用图像传感器对指纹和人脸等光学信息、麦克风对说话声等声学信息进行采集，利用数据预处理以及特征提取技术对采集的数据进行处理，得到相应的特征进行存储。
识别过程采用与注册过程一致的信息采集方式对待识别人进行信息采集、数据预处理和特征提取，然后将提取的特征与存储的特征进行比对分析，完成识别。从应用任务看，生物特征识别一般分为辨认与确认两种任务，辨认是指从存储库中确定待识别人身份的过程，是一对多的问题;确认是指将待识别人信息与存储库中特定单人信息进行比对，确定身份的过程，是一对一的问题。
生物特征识别技术涉及的内容十分广泛，包括指纹、掌纹、人脸、虹膜、指静脉、声纹、步态等多种生物特征，其识别过程涉及到图像处理、计算机视觉、语音识别、机器学习等多项技术。目前生物特征识别作为重要的智能化身份认证技术，在金融、公共安全、教育、交通等领域得到广泛的应用。
七、VR/AR
虚拟现实(VR)/增强现实(AR)是以计算机为核心的新型视听技术。结合相关科学技术，在一定范围内生成与真实环境在视觉、听觉、触感等方面高度近似的数字化环境。用户借助必要的装备与数字化环境中的对象进行交互，相互影响，获得近似真实环境的感受和体验，通过显示设备、跟踪定位设备、触力觉交互设备、数据获取设备、专用芯片等实现。
虚拟现实/增强现实从技术特征角度，按照不同处理阶段，可以分为获取与建模技术、分析与利用技术、交换与分发技术、展示与交互技术以及技术标准与评价体系五个方面。获取与建模技术研究如何把物理世界或者人类的创意进行数字化和模型化，难点是三维物理世界的数字化和模型化技术;分析与利用技术重点研究对数字内容进行分析、理解、搜索和知识化方法，其难点是在于内容的语义表示和分析;交换与分发技术主要强调各种网络环境下大规模的数字化内容流通、转换、集成和面向不同终端用户的个性化服务等，其核心是开放的内容交换和版权管理技术;展示与交换技术重点研究符合人类习惯数字内容的各种显示技术及交互方法，以期提高人对复杂信息的认知能力，其难点在于建立自然和谐的人机交互环境;标准与评价体系重点研究虚拟现实/增强现实基础资源、内容编目、信源编码等的规范标准以及相应的评估技术。
目前虚拟现实/增强现实面临的挑战主要体现在智能获取、普适设备、自由交互和感知融合四个方面。在硬件平台与装置、核心芯片与器件、软件平台与工具、相关标准与规范等方面存在一系列科学技术问题。总体来说虚拟现实/增强现实呈现虚拟现实系统智能化、虚实环境对象无缝融合、自然交互全方位与舒适化的发展趋势。人工智能、大数据、云计算和物联网的未来发展值得重视，均为前沿产业，多智时代专注于人工智能和大数据的入门和科谱，在此为你推荐几篇优质好文：在网络大时代背景下，人工智能技术是如何应用的http://www.duozhishidai.com/article-15277-1.html未来人工智能技术，主要包含哪几种？http://www.duozhishidai.com/article-4938-1.html人工智能时代，你需要了解的9大技术领域http://www.duozhishidai.com/article-3845-1.html
多智时代-人工智能和大数据学习入门网站|人工智能、大数据、物联网、云计算的学习交流网站
人工智能导论 第二章 搜索技术
2.1搜索的基本概念搜索：一种求解问题的一般方法
问题求解的基本方法：搜索法、归约法、归结法、推理法及产生式
基本问题：1、是否一定能找到一个解
2、找到的是否是最佳解
3、时间和空间复杂度
4、是否会终止运行or死循环
主要过程：1、从初始或目的状态出发，并将其作为当前状态
2、扫描操作算子集，将适用当前状态的一些操作算子作用于当前状态而得到新的状态，并建立指向父节点的指针
3、检查所生成的新状态是否满足结束状态。若满足，反向得出解答路径；否则将新状态定义为当前状态返回2
概念术语搜索方向（1）数据驱动：初始状态出发正向搜索
（2）目的驱动：从目的状态出发逆向搜索
（3）双向搜索找到汇合点
盲目搜索与启发式搜索（1）盲目搜索：不针对特定问题任何有关信息，按照固定步骤搜索
（2）启发式搜索：考虑特定问题可应用的知识，动态确定算子，优先选择合适算子，减少步骤
状态表示系统状态、事实等叙述性知识的一组变量或数组
操作表示引起状态变化的过程型知识的一组关系或函数
2.2状态空间的搜索策略状态空间：利用状态变量和操作符号，标识系统或问题的有关知识的符号体系，三元组（S、F、G）
S：状态集合F：操作算子的集合G：目的状态集合
求解路径从S0到G结点的路径，状态空间的一个解是一个有限的操作算子序列
表示方法：图描述八数码问题的图描述
TSP问题的图描述
2.3盲目搜索回溯策略从初始状态出发不停试探路径，直到到达目的或“不可解节点”。若遇到不可解节点就回溯到路径中最近的父节点上，查看该节点是否还有其他子节点未被扩展。
算法：
1、PS表：保存当前搜索路径上的状态，如果找到目的，PS就是解路径上的状态有序集
2、NPS表：新的路径状态表，包含等待搜索的状态，后裔状态还未被搜索到
3、NSS表：不可解状态集，列出找不到接替路径的状态。如果在搜索中扩展出他的元素，可立即排除
图搜索算法（DFSBFS最好优先搜索）的回溯思想
（1）用NPS使算法可以回归到任意状态
（2）用NSS避免算法重新搜索无解路经
（3）PS表中记录当前搜索路径状态，满足目的时可以将其作为结果返回
（4）为避免死循环，需要对子状态及性能检查，看是否在3张表中
广度优先搜索策略例题：机器人积木动作序列问题
算子MOVE（X，Y）的先决条件：
1、被搬动积木顶必为空
2、若Y是积木，Y顶部也必须为空
3、同状态下操作算子运用次数不得多于1次
深度优先搜索策略深度优先搜索中，当搜索到某一状态，其所有子状态及子状态的后裔状态必须先于该状态的兄弟状态被搜索。并且为了保证找到解，应选择合适的深度限制或不断加大深度限制值，反复搜索。
深度优先搜索并不能保证第一次搜索到某个状态时的路径是到这个状态的最短路径，如果算法多次搜索到同一个状态时应当保留最短路径
盲目搜索——代价树搜索代价树搜索：用于寻找最小代价路径问题，是推广版的BFS（如果权值都一致的话就是BFS）
比较图搜索与树搜索：
最短路径的图搜索：搜索算法认为一个状态只能对应搜索图中的一个节点
最短路径的树搜索：同一个状态可以多次出现在树中，相同状态可以同时出现在搜索中代表不同节点
实际操作中可以从搜索树构造搜索图搜索算法，从边缘集合中取出那些会导致搜索出现重复状态的节点。
搜索图是动机的角度，搜索树是实现的角度。
例题：卒子穿阵问题
2.4启发式图搜索启发式策略启发：关于发现和发明操作算子及搜索方法的研究
在状态空间搜索中，启发式被定义成一系列操作算子，并能从状态空间中选择最有希望到达问题解的路径。
启发式策略：利用问题相关的启发信息进行搜索
运用启发策略的两种基本情况1、一个问题由于在问题陈述和数据获取方面的模糊性，可能使它没有确定解
2、虽有可能有确定解，但是状态空间特别大，生成扩展的状态数会随搜索深度指数级增长
启发信息和估价函数求解问题中利用的大多是非完备的启发信息
1、求解问题系统不能知道与实际问题有关的全部信息，无法知道所有状态空间，无法用一套算法求解所有问题
2、虽然理论上存在求解算法，但工程实践中不是效率太低就是无法实现
启发信息分类1、陈述性2、过程性
3、控制性（没有任何控制性知识作为搜索依据，所以每一步都是随意的；有充分的控制知识作为依据，因而搜索的每一步选择都是正确的）
估价函数：估计代搜索节点的有希望程度，并依次给它们拍定次序
估价函数f（n）从初始节点经过n节点到达目的节点的路径的最小代价估计值f=g+h（g越大先用宽度优先，h越大表示启发能力越强）
总结：利用知识来引导搜索，减少搜索范围，降低问题复杂度
启发信息的强度可以分为：强：降低搜索工作量，可能导致找不到最优解
弱：导致工作量加大，极限情况下可以盲目搜索，但可能找到最优解
引入启发知识，在保证找到最优解的情况下尽可能缩小搜索范围，提高搜索效率
例题：八数码的估价函数
A搜索算法启发式图搜索算法的基本特点：寻找并设计一个与问题相关的h（n）及构出f（n）=g+h，然后以f（n）的大小来排列待扩展状态的次序，每次选f值最小者进行
open表：保留所有已生成而未扩展的状态
closed表：记录已扩展过的状态
进入open表的状态是根据其估值的大小插入到表中合适的位置，每次从表中优先取出启发估价函数值最小的状态进行扩展。
每次重复时，A搜索算法从open表中取出第一个状态。如果该状态满足目标条件，则算法返回到该状态的搜索路径。
如果open表的第一个状态非目的状态，则算法通过一系列操作算子进行相应操作来产生其子状态。若某子状态在open&closed表中出现过，即该状态再一次被发现时 ，通过刷新祖先状态的历史记录，使算法可能找到更短路径。
A搜索算法接着open表中每个状态的估价函数值，按照值大小重新排序，将值最小的状态放在表头，使其第一个被扩展。
例题：利用A搜索算法求解八数码问题的搜索树，估价函数定义为f=d+w
d：为状态深度，每步代价为单位代价。w：以“不在位”的将牌数作为启发信息的量度。
（A&A*搜索树）
A*搜索算法及其特性分析若某一问题有解，A*一定能搜索到解且一定能得到最优解。
A算法没有对估价函数f（n）作任何限制，实际上估价函数对搜索过程也十分重要
A*就是对估价函数加上一些限制后得到的一种启发式搜索算法
可容性：启发函数不会高估从节点n到终止节点所应付出的代价
一致性：三角不等式h(n)