人工智能导论 基础搜索算法
基础搜索算法在本章中,我们首先会对推断这一逻辑过程进行建模,并将其含义与搜索整合起来,解释将推断的逻辑行为建模和实现为搜索算法的原理与合理性.
其次,我们将介绍包括深度优先搜索(DFS)在内的数种基础搜索算法.
1.推断和搜索下面介绍两种对问题的建模思路:将问题建模为状态转换问题和将问题建模为逻辑推断问题.
1.1将问题建模为状态转换问题考虑如下的一个问题:
给定如上图所示的初始条件,我们需要生成一系列由Dalek所执行的操作组成的策略,从而使得书架被运到客厅(sittingroom),且Dalek最终位于大厅(hall)内.
我们可以如下分别表达这个问题所描述的两种事实:
//Fluents[in(dalek,hall),in(bookcase,hall),in(table,study)]//Permanents[adjacent(bedroom,hall)adjacent(hall,sitting-room),adjacent(sitting-room,study)]并且我们可以将问题的目标描述如下:
//Goals[in(dalek,hall),in(table,sitting-room)]注意在这里我们使用数组存储可变事实,既定事实和目标.
我们首先对推断这一逻辑操作进行行为上的拆解.任何推断都必须存在一个被推断主体,也就是问题本身,因此要对推断建模,我们首先需要对问题本身进行建模.
进一步地,问题的本质是:我们需要生成一个符合某些限制条件的策略,使得问题中所提出的要求可以通过执行策略来满足.显然地,任何一个问题又可细分为四个部分:
当前已知,但会随着我们采取行为而被改变的可变事实(Fluents).当前已知,且永不会被改变的既定事实(Permanents).问题所提出的目标(Goal).策略的组成部分:我们可以执行的所有行为(Actions).我们下面限定Dalek的行为:
//Actionscarry(bookcase,study,sitting-room),go(sitting-room,hall)显然更进一步地,任何行为又包含四个部分:
我们具体要执行的操作.该行为能够被执行所需要满足的前提条件.在行为执行后,所出现的新事实.在行为执行后,所消失的旧事实.我们可以进一步地细化两个行为:
//carryaction-type(carry(Object,Room1,Room2),pre-conds([in(Object,Room1),in(dalek,Room1),adjacent(Room1,Room2)]),add-list([in(dalek,Room2),in(Object,Room2)]),del-list([in(dalek,Room1),in(Object,Room1)]).)//goaction-type(go(Room1,Room2),pre-conds([in(dalek,Room1),adjacent(Room1,Room2)]),add-list([in(dalek,Room2)]),del-list([in(dalek,Room1)]).)而通过将细化的行为描述中所有的变量赋值,我们就可以将其实例化.
我们可以将所有可能采取的行策略表示为一个多叉树,其中:节点由一个表示当前状态的可变事实列表代表,而每一条边都是一个被实例化的行为.
每个节点对应的子树数量为在该节点上可采取的行为的种数,而每层节点的数量为上一整层节点在进行所有可能的行为后所能被变换到的新状态的数量总和.
在完成对问题的建模后,我们还需要对应的逻辑方法用于解决问题并给出可行解.由于我们将问题的状态转换建模为树,我们相应地就需要一套用来在树中搜索可行路径(在解空间内搜索可行解)的方法.
称程序用于在所有可能的推断中选择用于解决问题达成目标的特定推断的算法为启发算法(Heuristics).
1.2将问题建模为逻辑推断问题我们除了将求解问题的过程视为状态转换过程外,还可以将其抽象为逻辑推断问题.在这一建模思想下,解决问题的核心是下图所示的逻辑推断规则:
显然,在开始解决问题时我们有一系列的已知事实.通过应用不同的推断规则,已知事实就会发生不同的变化:我们可能从已知的一些事实中推断出新的.
由此,从初始状态下的已知事实出发,执行所有可能被应用的逻辑推断规则的过程就可同样地被建模成知识状态树:
通过逐步地确定在不同的状态下基于当前的知识应该应用哪条三段论推理规则最终使知识状态(KnowledgeState)和目标状态保持一致,我们也可以求得问题的解.在这一建模思想下,求解问题的过程也就是在知识状态树上搜索的过程.
2.搜索算法从上一节中可以看出,从对现实问题的两种建模方式出发,解决问题的本质最终都殊途同归地表示为了在某种状态树上的搜索过程.因此,在本节中,我们介绍四种基础的搜索算法.
2.1深度优先搜索DFS深度优先搜索的原理是,搜索到某个节点后,若它不为所需要的节点,则下一步总是以搜索它的子节点而非同级节点为最高优先.该原理决定了其行为是:一条条地纵向遍历,从上到下地完整搜索每一条可行路径,直到得到一个可行路径(可行解)为止.其伪代码如下:
dfs(Queue):ifQueueisnon-empty:FirstNode:=Queue.pop()ifFirstNodeisgoal_node:returnFirstNodeadd_daughters_of_FirstNode_to_the_front_of_the_queuereturndfs(Queue)returnfailure我们也可以这样递归地实现DFS:
dfs(Node):ifNodeisgoal_node:returnNodeforeachDaughterindaughters_of_Node:ifdfs(Daughter)!=failure:returndfs(Daughter)returnfailure2.2广度优先搜索BFS广度优先的原理是,搜索到某个节点时,若它不为所需要的节点,则下一步总是以搜索与其同级的节点而非其子节点为最高优先.故其行为是:一级级地横向遍历,从左到右地完整搜索每一级上的全部节点,直到得到一个可行路径(可行解)为止.其伪代码如下:
bfs(Queue):ifQueueisnon-empty:FirstNode:=Queue.pop()ifFirstNodeisgoal_node:returnFirstNodeadd_daughters_of_FirstNode_to_the_end_of_the_queuereturnbfs(Queue)returnfailure深度优先和广度优先搜索仍然属于结构最为简易的搜索方法,它们给出的解可能并非解空间中的最优解.
为了分别解与解之间的优劣,我们引入代价的概念,它刻画了一个人为定义的,反映实际情况中为了实现某个解所需要付出的成本的大小.为了找到成本最低的解,我们进行如下假设:
假定我们可能采取的任何行为都有一个(!非负的)成本(Cost).因此,每个节点ν uν对应地有一个数据C(ν)C( u)C(ν)表示从根节点执行一系列行为后到达该点所需要付出的成本Costso-far.
假设对任何问题而言,为了实现目标所需要付出的代价都是有限的,因此存在一个非负的成本下界(lowerbound).结合假设1,我们可知每个节点ν uν都有一个对应的从该状态转移到问题可满足状态所需要付出的代价的最小估计U(ν)U( u)U(ν).
需要注意:深度优先和广度优先搜索伪代码除了可以表示为上文提到的栈实现外,还可表示为(实际上最常用到的)递归实现,递归实现在实际程序执行时生成的内部栈和栈实现是完全一致的,二者实际上等价.
我们下面介绍两种可用于求解成本最低解的算法:分支定界算法(branch-and-bound)和A*:
2.3分支定界算法BranchandBound我们定义总代价K(ν)K( u)K(ν):
K(ν):=C(ν)+U(ν)K( u):=C( u)+U( u)K(ν):=C(ν)+U(ν)
根据上述分析,此式显然成立.在算法执行之初,K(ν)K( u)K(ν)是未知的.当算法找到第一个解时,其代价C(ν)C( u)C(ν)被自然地赋值为K(ν)K( u)K(ν),因为U(ν)=0U( u)=0U(ν)=0,此式我们记录下该解并对K(ν)K( u)K(ν)赋值.随着算法继续执行搜索,我们可能找到更多的解.若某个解的K(μ)⩽K(ν)K(mu)leqslantK( u)K(μ)⩽K(ν),我们更新最优解和相应的K(ν)K( u)K(ν).在确定筛选完了所有解后,此时的ν uν就是所需的最优解.
在实际的分支定界算法中,为了提高算法效率我们还会对搜索树进行剪枝.
分支定界算法始终围绕状态树进行.将原问题视为根节点并从这里出发,搜索行为类似于深度优先搜索.分支的含义就是将大的问题分割成小的问题.大问题可以看成是搜索树的父节点,故从大问题分割出来的小问题就是子节点,分支就是不断增加子节点的过程.
定界指在分支的过程中检查子问题的成本上下界.若子问题不能产生更优解,则对这一支执行剪枝.直到所有子问题都不能产生一个更优的解时,算法结束.
分支定界算法的伪代码如下:
#BestCost变量维护当前已知最优解的最低代价BestCost=INFINITY#初始化已知最低代价CurrentBest=none#初始化当前最优解bnb(Queue,BestCost):ifQueueisnon-empty:#逐个检查序列中的所有节点FirstNode:=Queue.pop()#只考虑成本上界低于当前最低代价的节点ifK(FirstNode)【学习笔记】人工智能导论
文章目录一、概论二、状态搜索空间表示及其搜索技术状态空间法图搜索盲目式搜索启发式搜索三、问题归约知识表示及搜索技术问题归约法及与或图与或树的宽度搜索与深度搜索博弈与博弈树搜索四、谓词逻辑表示与推理技术机器自动推理与命题逻辑谓词逻辑消解原理与子句集求解消解反演与反演求解五、模糊逻辑与模糊推理模糊逻辑及模糊集合模糊集合运算与合成模糊推理六、遗传算法生物学背景及遗传算法的原理遗传算法求解优化问题实例七、群智能算法粒子群算法蚁群算法八、人工神经网络人工神经网络原理深度学习九、人工智能应用案例一、概论人工智能的概念：只要能够模仿人类进行智能活动的机械、设备、软件、系统等都可以归类为人工智能人工智能的三大学派：符号主义、连接主义、行为主义
二、状态搜索空间表示及其搜索技术状态空间法基于解答空间的问题表示和求解方法，它是以状态和算符为基础来表示和求解问题的状态空间的图示形式称为状态空间图（有向图）。其中，图的节点表示状态，图的边表示算符问题求解过程就是寻找图的某一路径的问题，实际上是一个搜索过程
图搜索盲目式搜索启发式搜索启发式搜索是利用与问题有关的启发性信息，并以这些启发性信息指导的搜索的问题求解过程
三、问题归约知识表示及搜索技术问题归约法及与或图问题归约法的基本思路是：应用一系列算符将原始问题的描述变换或分解成为子问题的描述
与或树的宽度搜索与深度搜索宽度优先搜索是先产生的节点排在OPEN表最前面，先进行扩展深度优先的要点则是新产生的节点先被扩展
博弈与博弈树搜索宽度优先是先产生的节点先被考察深度优先是新产生的节点先被考察博弈树搜索是与或树搜索中的启发式搜索的特例，它是适用于双方博弈的搜索方法
四、谓词逻辑表示与推理技术机器自动推理与命题逻辑谓词逻辑谓词逻辑允许我们表达那些无法用命题逻辑表达的事情
消解原理与子句集求解消解原理的基本思想是理解消解反演证明和反演求解的基础
要进行消解反演证明与反演求解，必须先将谓词公式化为子句集
消解反演与反演求解最一般合一：通过置换最少的变量以使表达式一致
五、模糊逻辑与模糊推理模糊逻辑及模糊集合模糊概念有一个共同点从属于该概念到不属于该概念之间无明显分界线
模糊集合运算与合成两个模糊关系合成后还是一个模糊关系，因而也还是一个模糊集合
模糊推理模糊推理的基本模式：（1）模糊假言推理（2）模糊拒取式推理
六、遗传算法生物学背景及遗传算法的原理遗传算法求解优化问题实例七、群智能算法粒子群算法蚁群算法蚁群算法的基本要素：
1、路径构建2、信息素更新
TSP问题举例：工件排序计算机布线……
八、人工神经网络人工神经网络原理深度学习九、人工智能应用案例卓居产品导盲仗渐冻人智慧生活眼控轮椅机器学习遥感影像……
人工智能导论——智能计算（进化算法+群智能优化）
【C++算法快速上手】顺序结构（更新中）CSDN-Ada助手:非常感谢CSDN博主的分享，这篇关于C++算法顺序结构的博客非常实用。我觉得可以继续分享C++中常用的算法之一——选择结构，介绍如何使用if、elseif、else语句实现选择结构，同时结合实例演示其应用场景。这样的技术文章对其他用户也会有很大帮助。相信下一篇博客会有更多读者关注和学习。为了方便博主创作，提高生产力，CSDN上线了AI写作助手功能，就在创作编辑器右侧哦～（https://mp.csdn.net/edit?utm_source=blog_comment_recall）诚邀您来加入测评，到此（https://activity.csdn.net/creatActivity?id=10450&utm_source=blog_comment_recall）发布测评文章即可获得「话题勋章」，同时还有机会拿定制奖牌。
【C++算法快速上手】顺序结构（更新中）Jagitova•Alina_:帮助很大！
人工智能导论——搜索求解m0_58487218:可以写一下深度广度搜索的open，close表吗
【rPPG论文阅读】LearningtoRemoveandEmbedrPPGSignalsviaDoubleCycleConsistentLearningCSDN-Ada助手:你好，CSDN开始提供#论文阅读#的列表服务了。请看：https://blog.csdn.net/nav/advanced-technology/paper-reading。如果你有更多需求，请来这里https://gitcode.net/csdn/csdn-tags/-/issues/34给我们提。
面向对象程序设计——计算阿姆斯特朗数（C++）TZFNEVERDEFEAT:时间过长可以调整吗