精华内容
下载资源
问答
  • 人工智能 ——与/或启发式搜索

    千次阅读 2019-06-13 06:40:43
    与/或启发式搜索过程就是不断地选择、修正希望的过程,在该过程中,希望是不断变化的。它需要符合以下三个条件: 初始结点S0在希望T 如果n是具有子结点n1, n2, … , nk的或结点,则n的某个子结点ni在希望...

    希望树

    希望树是指搜索过程中最有可能成为最优解树的那棵树。与/或树的启发式搜索过程就是不断地选择、修正希望树的过程,在该过程中,希望树是不断变化的。它需要符合以下三个条件:

    1. 初始结点S0在希望树T
    2. 如果n是具有子结点n1, n2, … , nk的或结点,则n的某个子结点ni在希望树T中的充分必要条件是
      在这里插入图片描述
    3. 如果n是与结点,则n的全部子结点都在希望树T中。

    启发式搜索过程

    在这里插入图片描述
    在这里插入图片描述


    启发式搜索实例

    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 启发式搜索启发式搜索中,每当遇到一个状态,就可能出现的很多后续的状态,这些状态和分支就构成了一棵叶子节点的值是近似值函数,然后向前备份直到当前的状态。一旦计算出了每个节点的备份值,我们就选择...

    在人工智能领域经典的状态空间规划算法是决策时规划,这类算法也被总称为启发式搜索。本节将介绍什么是启发式搜素以及启发式搜索的应用。

    启发式搜索

    在启发式搜索中,每当遇到一个状态,就可能出现的很多后续的状态,这些状态和分支就构成了一棵树。树叶子节点的值是近似值函数,然后向前备份直到当前的状态。一旦计算出了每个节点的备份值,我们就选择具有组好备份值的动作作为当前的动作,然后所有备份值都被丢弃了。

    所有我们可以看到,启发式搜索其实和前面讲的n-step TD算法很像,尤其是前面讲的树备份算法。除了不保存备份值。实际上,在启发式搜索中值函数通常是人为设计的,并且保持不变。但是,更合理的做法是利用搜索过程中的备份值,或者书中讲的其他方法来逐渐的改变值函数。

    如果考虑启发式搜索备份的过程,其实贪婪算法,

    -贪婪算法或者是UCB行为选择方法和启发式搜索也很像,这是规模小一些。例如,给定环境模型和一个状态值函数,为了选择贪婪的行为,我们必须往前看一步,找到所有可能的下一个状态(搜索),然后利用当前回报和估计的下一个状态的值函数(备份)来选择最佳的动作(其实就是one-step的值迭代)。
    传统的启发式搜索也是同样的思路,只是不保存备份值。因此,启发式搜索可以看成是贪婪策略的多步扩展。

    为什么不用单步搜索,而是往更深的搜索,目的在于获得更好的动作选择。如果我们有一个完美的模型和一个步准确的值函数,那么搜索越深通常会得到更好的策略。怎么理解呢?模型是理想的意味着我们搜索的方向是对的,值函数不准确会影响我们备份值的计算。但是搜索越深,值函数对于备份值的影响就越小了,如果一直搜索到一个episode的末尾,那么就类似于MC方法,得到的备份是精确的,不再受到值函数的影响。当然如果搜索到第

    层,且
    足够小,那么得到的动作也是接近最优的。这是因为
    足够小,那么
    对于备份值的影响也很小了。所以得到的动作依然是接近最优的。但是另一个方面,搜索的越深,需要的计算量也越大,响应时间就越慢。一个例子就是Tesauro编写的下双陆棋的程序。这个系统利用TD学习方法来学习afterstate值函数,使用启发式搜索来决定如何走每一步。对于模型,TD-Gammon 假设对手总是选择TD-Gammon 认为最好的动作。Tesauro发现搜索的越深,TD-Gammon就表现的越好,但是每一步花费的时间也越长。TD-Gammon具有很多的分支,导致其计算量随着搜索深度增长很快。因此通常它只能搜索几步。但是即使这样,搜索也会明显的改善动作的选择。

    为什么启发式搜索会如此高效?

    启发式搜索的一个特点是:专注于当前的状态。在你下棋的时候,无论你采取什么样的策略,你总是最关心当前这一步该怎么走,当前状态的值函数是否准确也是最为紧要的。而启发式搜索总是通过搜索来更新当前状态的值。这样就能将计算资源和内存资源优先使用在我们关系的当前状态上,因此十分高效。

    深度优先搜索

    启发式搜素一种可能的情形如下:

    631688a19d3ad4c0665d2d4d426e9696.png

    我们通过自下向上的单步更新(注意1到10的每一步都是一个单步的更新),通过拼接这些更新,获得上一层的更新,最终得到根节点的值函数,这种更新次序叫做深度优先启发式搜索(depth-first heuristic search)。比如上图中1,2,3对应更新的状态形成了一个子树。更新4-10形成了另一棵树。通过两个子树的更新,分别得到a1的值为8,a2的值为10,那么启发式搜索就会在当前状态选择a2,然后继续下一步的搜索。

    展开全文
  • 与或的盲目搜索和启发式搜索

    千次阅读 2017-11-20 21:25:57
    与或的盲目搜索 与或的一般搜索过程如下 (1)把原始问题作为初始节点S0,并把它作为当前节点 (2)应用分解或等价变换操作对当前节点进行扩展 (3)为每个子节点设置指向父节点的指针 (4)选择合适的子...
    与或树的盲目搜索


    与或树的一般搜索过程如下

    (1)把原始问题作为初始节点S0,并把它作为当前节点
    (2)应用分解或等价变换操作对当前节点进行扩展
    (3)为每个子节点设置指向父节点的指针
    (4)选择合适的子节点作为当前节点,反复执行第(2)步和第(3)步,在此期间需要多次调用可解标记过程或不可解标记过程,直到初始节点被标记为可解节点或不可解节点为止

    上述搜索过程将形成一棵与或树,这种由搜索过程形成的与或树称为搜索树。当搜索成功时,经可解标记过程标识的由初始节点极其下属的可解节点构成的子树称为解树。

    与或树搜索过程中的可解标记过程与不可解标记过程都是自下而上进行的,即由子节点的(不)可解性确定父节点、祖父节点的(不)可解性。

    在与或树中,除端节点和终止节点外,一个节点的可解性完全是由其子节点来决定的。对与节点,只有其所有子节点都为可解时它才可解,只要有一个子节点不可解它就不可解;对于或节点,只要有一个子节点可解它就是可解的,仅当所有子节点都是不可解时它才为不可解。

    可解标记过程:由可解子节点来确定其父节点、祖父节点为可解节点的过程
    不可解标记过程:由不可解子节点来确定其父节点、祖父节点为不可解节点的过程

    由于与或树搜索的目标是寻找解树,因此,如果搜索过程确定某个节点为可解节点,则其不可解的后裔节点就可以从搜索树中删去;同样,如果搜索过程能确定某个节点未不可解节点,则其后裔节点也可以从搜索树中删去。


    与或树的广度优先搜索

    与或树的广度优先搜索与状态空间的广度优先搜索类似,只是在搜索过程中需要多次调用可解标记过程或不可解标记过程,其搜索算法如下:
    (1)把初始节点S0放入Open表中
    (2)把Open表的第一个节点取出放入Closed表,并记该节点为n
    (3)如果节点n可扩展,则做下列工作:
    • 扩展节点n,将其子节点放入Open表的尾部,并为每一个子节点设置指向父节点的指针
    • 考察这些子节点中是否有终止节点。若有,则标记这些终止节点为可解节点,并用可解标记过程对其父节点及其先辈节点中的可解节点进行标记。如果初始解节点S0能够被标记为可解节点,就得到了解树,搜索成功,退出搜索过程;若果不能确定S0为可解节点,则从Open表中删去具有可解先辈的节点
    • 转第(2)步
    (4)如果节点n不可扩展,则做下列工作:
    • 标记节点n为不可解节点
    • 应用不可解标记过程对节点n的先辈中不可解的节点进行标记。如果初始解节点S0也被标记为不可解节点,则从Open表中删去具有不可解先辈的节点
    • 转第(2)步


    与或树的深度优先搜索

    与或树的深度优先搜索和与或树的宽度优先搜索过程基本相同,其主要区别在于Open表中节点的排列顺序不同。在扩展节点时,与或树的深度优先搜索过程总是把刚生成的节点放在Open表的首部
    与或树的有限深度优先算法:
    (1)把初始节点s0放入Open表中
    (2)把Open表的第一个节点取出放入Closed表,并记该节点为n
    (3)如果节点n的深度等于dm,则转第(5)步的第一点
    (4)如果节点n可扩展,则做下列工作
    • 扩展节点n,将其子节点放入Open表的首部,并为每一个子节点设置指向父节点的指针
    • 考察这些子节点中是否有终止节点。若有,则标记这些终止节点为可解节点,并用可解标记过程对其父节点中的可解节点进行标记。如果初始节点S0能够被标记为可解节点,就得到了解树,搜索成功,退出搜索过程;如果不能确定S0为可解节点,则从Open表中删去具有可解先辈的节点
    • 转第(2)步
    (5)如果节点n不可扩展,则做下列工作
    •    标记节点n为不可解节点
    • 应用不可解标记对节点n的先辈中不可解的节点进行标记。如果初始节点S0也被标记为不可解节点,则搜索失败,表明原始问题无解,退出搜索过程;如果不能确定为不可解节点,则从Open表中删去具有不可解先辈的节点
    • 转第(2)



    与或树的启发式搜索

    与或树的盲目搜索时按确定路线进行的,没有考虑要付出的代价,因而求得的解树不一定是代价最小的解树,即不一定是最优解树。因此,我们需要考虑与或树的启发式搜索。
    与或树的启发式搜索过程是一种利用搜素过程所得到的启发性信息寻找最优解的过程
    对搜索的每一步,算法都试图找到一个最有希望成为最优解的子树
    最优解树是指代价最小的那棵解树

    要寻找最优解树,首先需要计算解树的代价。在与或树的启发式搜索过程中,解树的代价可按如下规则计算:
    (1)若n为终止节点,则其代价h(n)=0
    (2)若n为或节点,且子节点为n1,n2,...,nk,则n的代价为h(n)=min{c(n.\,ni)+h(ni)}(1<=i<=k)其中,c(n,ni)是节点n到其子节点ni的边代价
    (3)若n为与节点,且子节点为n1,n2,...nk,则n的代价可用和代价法或最大代价法
       若用和代价法,则其计算公式为    h(n)=求和((c(n,ni)+h(ni))  i=1,2,......k
       若用最大代价法,则其计算公式为  h(n)=max{c(n,ni)+h(ni)}  (1<=i<=k)
    (4)若n是端节点,但又不是终止节点,则n不可扩展,其代价定义为h(n)=无穷大
    (5)根节点的代价即为解树的代价

    为了找到最优解树,搜索过程的任何时刻都应该选择那些最有希望成为最优解树一部分的节点进行扩展。由于这些节点及其父节点所构成的与或树最有可能成为最优解树的一部分,因此称它为希望解树,也简称为希望树。
    搜索过程:
    (1)把初始节点S0放入到Open表中,计算h(S0)
    (2)计算希望树T
    (3)依次在Open表中取出T的端点放入Closed表,并记该节点为n
    (4)如果节点n为终止节点,则做下列工作
    • 标记节点n为可解节点
    • 在T上应用可解标记过程,对n的先辈节点中的所有可解节点进行标记
    • 如果初始节点S0能够标记为可解节点,则T就是最优解树,成功退出
    • 否则,从Open表中删去具有可解先辈的所有节点
    • 转第(2)步
    (5)如果节点n不是终止节点,但可扩展,则做下列工作
    • 扩展节点n,生成n的所有子节点
    • 把这些子节点都放入Open表中,并为每一个子节点设置指向父节点n的指针
    • 计算这些子节点及其先辈节点的h值
    • 转第(2)步
    (6)如果节点n不是终止节点,且不可扩展,则做下列工作
    • 标记节点n为不可解节点
    • 在T上应用不可解标记过程,对n的先辈节点中的所有不可解节点进行标记
    • 如果厨师节点S0能够被标记为不可解节点,则问题无解,失败退出
    • 否则,从Open表中删去具有不可解先辈的所有节点
    • 转第(2)步
    展开全文
  • 博弈是启发式搜索的一个重要应用领域,博弈的过程可以用一棵博弈搜索树表示,通过对博弈树进行搜索求取问题的解,搜索策略常采用α-β剪枝技术。在深入研究α-β剪枝技术的基础上,提出在扩展未达到规定深度节点时,...
  • 人工智能—— 博弈启发式搜索

    千次阅读 2019-06-13 08:04:39
    一、概述 博弈的概念 博弈是一类具有智能行为的竞争活动,如下棋、战争等。...若把双人完备信息博弈过程用图表示出来,就得到一棵与/或,这种与/或被称为博弈。在博弈中,那些下一步该MAX走步的结...

    一、概述

    博弈的概念

    博弈是一类具有智能行为的竞争活动,如下棋、战争等。

    博弈的类型

    • 双人完备信息博弈:两位选手(例如MAX和MIN )对垒,轮流走步,每一方不仅知道对方已经走过的棋步,而且还能估计出对方未来的走步。
    • 机遇性博弈:存在不可预测性的博弈,例如掷币等。

    博弈树

    若把双人完备信息博弈过程用图表示出来,就得到一棵与/或树,这种与/或树被称为博弈树。在博弈树中,那些下一步该MAX走步的结点称为MAX结点,下一步该MIN走步的结点称为MIN 结点。

    博弈树的特点

    1. 博弈的初始状态是初始结点;
    2. 博弈树中的“或”结点和“与”结点是逐层交替出现的;
    3. 整个博弈过程始终站在某一方的立场上,例如MAX方。所有能使自己一方获胜的终局都是本原问题,相应的结点是可解结点;所有使对方获胜的终局都是不可解结点。

    二、极大极小过程

    (1)算法思想

    极大极小过程用当前正在考察的结点生成一棵部分博弈树,并利用估价函数f(n)对叶结点进行静态估值。

    求叶结点的值

    • 对MAX有利的结点,其估价函数取正值
    • 对MIN有利的结点,其估价函数取负值
    • 使双方均等的结点,其估价函数取接近于0的值。

    求非叶结点的值:

    必须从叶结点开始向上倒退。其倒退方法是:

    • 对于MAX结点,由于MAX 方总是选择估值最大的走步,因此,MAX结点的倒退值应该取其后继结点估值的最大值。
    • 对于MIN结点,由于MIN方总是选择使估值最小的走步,因此MIN结点的倒推值应取其后继结点估值的最小值。
    • 这样一步一步的计算倒推值,直至求出初始结点的倒推值为止。这一过程称为极大极小过程。

    (2)极大极小过程实例
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述


    三、α-β剪枝

    (1)算法思想

    极大极小过程是先生成与/或树,然后再计算各结点的估值,这种生成结点和计算估值相分离的方式,需生成规定深度内的所有结点,搜索效率较低。如果能边生成结点边对结点估值,并剪去一些没用的分枝,这种技术被称为α-β剪枝。

    剪枝方法

    1. MAX结点(或结点)的α值为当前子结点的最大倒推值;
    2. MIN结点(与结点)的β值为当前子结点的最小倒推值;
    3. α-β剪枝的规则如下:
    • β剪枝: 任何MAX结点n的α值大于或等于它先辈结点的β值,则n 以下的分枝可停止搜索,并令结点n的倒推值为α。这种剪枝称为β剪枝。
    • α剪枝: 任何MIN结点n的β值小于或等于它先辈结点的α值,则n 以下的分枝可停止搜索,并令结点n的倒推值为β。这种剪枝称为α剪枝。

    (2)α-β剪枝实例

    在这里插入图片描述

    1. 剪枝1:
    在这里插入图片描述
    α剪枝: MIN结点G的β值(<=1)小于或等于它先辈结点C的α值(>=4),结点G不可能让先辈结点C的α值增大,则G以下的分枝可停止搜索,并令结点n的倒推值为β(<=1)。这种剪枝称为α剪枝。

    详解: 在该图中,K、L、M的估值推出结点F的到推值为4,即F的β值为4,由此可推出结点C的到推值≥4。 记C的到推值的下界为4,不可能再比4小,故C的α值为4。由结点N的估值推知结点G的倒推值小于≤1,无论G的其它子结点的估只是多少,G的倒推值都不可能比1大。因此,1是G的倒推值的上界,所以G的值≦1 。另已知C的倒推值≥4,G的其它子结点又不可能使C的倒推值增大。因此对G的其它分支不必再搜索,相当于把这些分枝剪去。

    2. 剪枝2:

    在这里插入图片描述

    β剪枝: MAX结点D的α值(>=5)大于它先辈结点A的β值(<=4),则D以下的分枝可停止搜索,结点D不可能让先辈结点A的β值减小,并令结点D的倒推值为α(>=5)。这种剪枝称为β剪枝。

    详解: 由F、G的倒推值可推出结点C的倒推值≥4 ,再由C可推出结点A的倒推值≤4,即A的β值为4。另外,由结点P、Q推出的结点I的倒推值为5,因此D的倒推值 ≥5,即D的α值为5。此时,D的其它子结点的倒推值无论是多少都不能使D及A的倒推值减少或增大,所以D的其他分枝被减去,并可确定A的倒推值为4 。

    3. 其它剪枝(省略)

    展开全文
  • 常用搜索算法—盲目搜索和启发式搜索

    万次阅读 多人点赞 2019-05-25 00:51:39
    搜索算法 本文主要以一些概念对较为常见的搜索作简单介绍: 一、盲目搜索 ...深度优先搜索算法(简称DFS)是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当...
  • 1.问题描述 在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。这些数码可以在棋盘上移动,其移动规则是...盲目搜索就是无“向导”的搜索,启发式搜索就是有“向导”的搜索。 启发式.
  • 启发式搜索算法概述 随着计算机性能的提高,搜索算法利用计算机的计算资源有目的穷举一个问题解空间的部分或所有的可能情况,从而求解出问题的解。现阶段搜索类算法一般有深度/广度优先搜索、枚举算法、A-Star算法...
  • A*启发式搜索

    千次阅读 2015-02-15 11:56:20
    A*算法,作为启发式算法中很重要的一种,被广泛应用在最优路径求解和一些策略设计的问题中。而A*算法最为核心的部分,就在于它的一个估值函数的设计上: ...另一部分,即h(n),它表示启发式搜索中最为重要的
  • A* 算法是启发式搜索算法中的经典,经常应用于路径搜索和规划中。这里以八数码问题状态空间图的搜索为例,初步介绍以A*算法为代表的启发式搜索。 # 一、启发性信息和估价函数 ## 1.启发性信息: 启发式搜索是利用...
  • 搜索算法 本文主要以一些概念对较为常见的搜索作简单介绍: 一、盲目搜索 对一个图进行搜索意味着按照某种特定的顺序依次访问其顶点。...深度优先搜索算法(简称DFS)是一种用于遍历或搜索树...
  • 采用启发式搜索求解TSP问题步骤为:首先利用最小生成算法构造无向图 G 的TSP问题的最小生成;然后从最小生成开始构造闭合回路(N个城市不重复排列序列);最后采用枚举的方法,确定从不同最小生成开始构造的...
  •   搜索是人工智能里面研究的一个核心问题,像强化学习其本质我也是理解为一种搜索算法,不过其用了一些值函数近似的方法,并做了进一步改良,使其功能...  启发式搜索(Heuristically Search)又称为有信息搜索(I...
  • 一、启发式搜索和启发式函数 二、贪婪算法(贪婪最佳优先搜索)greedy best-first search (GBS) 三、A*搜索(结合UCS和GBS) A*搜索算法结束的条件是什么? ​怎么判证明A* 搜索的最优性?(这个容易出证明...
  • 基于最优原则的最大简约法的启发式搜索,将模拟退火算法引入遗传算法群体更新的阶段,既保证群体多样性,又在后期逐步加快收敛速度,克服遗传算法早熟现象,最终目标是尽量使得最大简约长最小、搜索时间最短。...
  • 贪婪算法是启发式算法的代表算法之一,其核心思想是每次都选择局部最优解,但该算法并不能保证最后得出的结果是全局最优解。贪婪算法比较典型的案例就是最短路径搜索。之前,大部分的贪婪算法都是基于图的方式寻找...
  • 决策树启发式和修剪 我们可以将决策定义为计算,其中每个节点都包含一个关于属性的问题,节点的每个分支都包含对该问题的答案。 哪个问题/属性应该放在每个节点中,由决策学习算法确定。 如Mitchel中所述,为...
  • (一)问题描述 在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。这些数码可以在棋盘上移动,其移动规则是:与空格...搜索方式有两种基本的方式,即树式搜索和线式搜索。搜索策略...
  • P1379 八数码难题 题意:在3×3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字。棋盘中留有一个空格,空格用0来表示。... 思路:迭代加深就是每次限制搜索深度 ,这样可以在整个搜索树深度很大而...
  • 随机局部搜索决策 该存储库用于我的第一个科学启动项目。 关于 决策是在机器学习,数据挖掘和统计中使用的一种预测建模方法。 在决策中,每个内部节点代表一个功能上的测试,每个终端(或叶子)节点代表一个类...
  • 贪心算法::启发式搜索

    千次阅读 2012-10-29 09:26:04
    但当问题的解比较多,则不宜使用,常用的做法是剪枝,剪枝是一种形象的描述,因为按深搜的算法,图可以描述为与之对应的或森林,而剪枝的意思就是去掉某些子树,为什么要去掉,这里要用到一个剪枝判断,判断的方法...
  • 博弈树搜索对于计算机博弈至关重要。优秀的搜索算法通过搜索较少的节点就可以获得最佳路径,从而提高计算机的博弈水平。论文以中国象棋计算机博弈作为背景,在alpha-beta基本搜索算法上,详细阐述了置换表启发算法的...
  • 通过对上述问题的研究,给出了最优密钥结构的定义,并提出一种构建最优密钥启发式搜索算法。与传统LKH密钥结构相比,最优树的不同层具有不同的分支数,因此其可降低密钥更新过程中的处理开销。理论分析与...
  • 八数码问题(启发式搜索)

    万次阅读 2007-03-25 02:22:00
    (一)问题描述在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。这些数码可以在棋盘上移动,其移动规则是:与空格相邻的数码方格...搜索方式有两种基本的方式,即树式搜索和线式搜索。
  • 600E - Lomsat gelral 题意 给出一颗以 1 为根的,每个点有颜色,如果某个子上某个颜色出现...启发式合并模板题。 参考blog1 参考blog2 复杂度证明 如果暴力去搜索,显然是 \(O(n^2)\) 的算法,可以考虑优化...
  • 这时我们可以利用启发式合并。每次暴力把小的一棵树搜索一次,同时加入大的一棵的主席中,同时更新倍增维护LCA。这样就实现了合并。对于每一个点,这样的合并不会超过O(logn)O(logn)O(logn)次。所以时间复杂度和...
  • 实用算法实现-第 14 篇 启发式搜索

    千次阅读 2011-10-23 00:15:58
    A*(A star)算法是一种很好的树搜索策略,在许多人工智能的书籍中有所介绍。比如《人工智能,一种现代方法》和《人工智能,复杂问题求解的结构和策略》。 [i]文介绍到,A*算法使用估价函数F(N)来估算从初始状态S到...

空空如也

空空如也

1 2 3 4 5 ... 15
收藏数 283
精华内容 113
关键字:

启发式搜索树