如果智能体澳门太阳集团事件真相所找到的结点只是一个极值

当前位置:澳门太阳集团城网址 > 澳门太阳集团事件真相 > 如果智能体澳门太阳集团事件真相所找到的结点只是一个极值
作者: 澳门太阳集团城网址|来源: http://www.hotelginebra.net|栏目:澳门太阳集团事件真相

文章关键词:澳门太阳集团城网址,搜索算法

  为了解决问题,在不同的状态之下会有不同的正确行为。只要我们能在所有状态之下找到正确的行为,再将其放入智能体的行为序列中,智能体就可以解决问题。

  举个例子,我们教小孩子吃苹果。现在我们把小孩子看成一个智能体,这个智能体有两种行为:咬一口、丢掉苹果。我们的目标是:让小孩子吃完苹果。那么这个问题中,苹果的初始状态是:完好,没有被咬。小孩的脑子里会分析苹果的状态,并得出正确的行为是:咬一口。进行完此行为之后,苹果的状态改变,变成:被咬一口的苹果。小孩的行为导致了新的状态,再次分析苹果的状态之后,小孩又做出咬一口的行为。这个行为又会导致新的状态,产生新的行为。直到最后,苹果的状态变成了:苹果核。小孩子分析之后,便产生了行为:丢掉苹果。

  但是在更复杂的问题中,不同状态下的智能体可能会有更加丰富的行为选择。那么,如何在众多行为中找到正确的行为,我们就需要用到搜索算法。

  那么,我们该如何定义一个搜索问题?用“定义问题”这样的方式来表述,可能比较抽象。换而言之的话,就是要开始运用算法解决一个问题,我们需要哪些准备?

  这三点能让我们把握住问题的整个“状态空间”。也就是说:初始状态所能够达到的所有状态的集合。我们可以用树或者图来表示状态空间。

  每个结点都表示一个状态,结点 A 便表示问题的初始状态。每一个箭头都表示一个行为,初始状态 A 随着不同的行为会变成不同的结点( B、C、D ),也就是不同的状态。假设我们所需要解决的问题,就是让智能体所处的环境达到 M 状态,澳门太阳集团事件真相那么智能体所需要做的,就是搜索出从 A 到达 M 的正确路径即可。路径便代表解决问题的方法。

  无信息搜索指的是:除了上面所提到的五条信息之外,没有其他任何信息来源的搜索算法。

  计算机界认为不要重复造轮子,所以我贴了一些文章的链接来代替我的讲解。链接放在了小标题之后。必要的内容我会进行补充。

  广度优先搜索具有非常好的性能,但是有很致命的缺点——时间复杂度和空间复杂度太高。

  广度优先搜索加上最优化的思想,就是一致代价搜索。当所有路径的耗散等价时,广度优先搜索优于一致代价搜索。

  对于图和树,深度优先搜索在图上的效率更高。它在时间复杂度上相较于 BFS 没有优势,在空间复杂度上优于 BFS。

  这里补充一点细节。因为当实际情况的深度无限大时,程序可能会陷入死角。为了防止死循环,我们可以在程序里加入一条深度界限,当搜索的深度达到这条界线时,直接跳出搜索行为。这样虽然解决了死角问题,但是当目标状态的深度深于深度界限时,我们可能会得到一个无解的结果。为此,我们可以引入一种更加灵活的思路——迭代加深的深度搜索。

  当该次的深度搜索没有找到目标结点时,便加深深度界限,继续运行深度搜索函数。

  我们可以从初始状态和目标状态两边开始,同时进行搜索算法。若两条搜索路径最终会触碰到一起,我们就认为我们找到了一条解决问题的路径。

  我将用最简单易懂的方式,讨论一下几种基础的启发式搜索方法。关于更加高阶的启发式搜索,我会单独开一篇文章来讨论。

  所谓的启发式搜索,就是指我们在搜索的过程中,总能得到一些启发式的信息。这些信息可以启示我们下一次搜索该往哪个方向进行。

  那么,什么是贪婪最佳优先搜索?它和贪心算法一样,试图始终让自己走上最小代价的搜索路径。只不过,这种思想和贪心算法一样,也容易出现各种误差。

  是不是挺简单的?不同的问题,启示函数会有不同的构造方式。这里的构造方式只是该问题的许多启示函数中的一种。

  带着新鲜的热乎乎的代价函数,我们来看看这种新的搜索方式。(嗯?我怎么又自己写了?)

  哈哈哈,还真是一样的。只不过这里我们用的是代价函数,所以我们的搜索可以保证最终的路径具有更小的代价。

  虽然我讲得很简单,但是这个算法其实具有更多更加复杂的内容,足够让我水十几篇文章了( 诶嘿嘿 )。要是有兴趣的话,就看看我写的这篇文章吧:

  如果你在阅读本文章之前,对人工智能的搜索算法并不太了解,那么你读到这时,应该已经有点累了。我希望你能打起精神,因为我们还有很多搜索算法的讲解,才刚刚打算开始。

  我们之前所讨论的算法,都是在整个状态空间已知的前提下才可以进行的。如果我们对全局状态不甚了解呢?

  这个时候,我们可以采取局部算法来尝试解决问题。顾名思义,局部算法只需要局部的信息,就可以执行搜索操作。

  这其实是一个很简单的算法,但是为了让读者能够看到它的本质,我会讲得稍微详细点。

  重阳节的时候,不少人会选择去爬山。爬山,其实是一种很简单的事情。只要你有足够的体力,澳门太阳集团事件真相那么你所需要做的,就是顺着大路,不断往更高处爬就是了。当我们爬到山的顶点时,我们可能会被眼前壮阔的风景所吸引,但是人的眼界始终是有限的,我们自以为站在了所有山峰的最高点,然而真正的最高点,可能在远方层层雾气里。

  上面我所讲到的例子,就是一个典型的爬山算法,也是这个算法名字的由来。当我们站在某个位置时,我们会判断哪个方向通往更高处,然后我们会下意识地往能够通向最高处的路线前进。毕竟我们的目标是通往山顶。

  我们现在将山上的位置划分成一个个结点。我们规定,当结点的海拔越高时,结点的估价函数值就会越高。现在,我们来尝试用另一种说明方式来阐述上面的例子。当我们站在某个结点时,我们会用估价函数判断相邻的每个结点的估价函数值,然后我们会下意识地往能够通向最高地估价函数值的路线前进。毕竟我们的目标是通往估价函数值最高的节点处。

  按照这样的步骤的话,就会产生一些问题。比如说,如果智能体所找到的结点只是一个极值,而不是最值,那该怎么办呢?如果智能体爬山的时候,到达了一个高原,然后因为高原是等高的,智能体迷了路怎么办?如果智能体恰好爬到了山峰顶点的左边,结果因为步子设置得过大,稍微迈一步就会买到右边,然后又迈到左边,如此死循环怎么办?

  这些问题,我们都会有一些相应的对策。但是我想之后再讨论这些细节,我们先看揭露爬山算法的本质——这就是一种贪心算法。如果你真正理解了贪心算法,应该可以直接理解这句话是什么含义。我相信读者中大部分人应该都可以理解,所以我不再多做解释。没看懂的读者,稍微想一下,也是可以想明白的。爬山算法只是一种特殊的贪心算法而已。我们现在再来讨论一下之前所提到的问题。

  如果搜索到的只是“极值”该怎么办?要知道,因为我们对状态空间的全貌是不了解的,所以我们也不能保证它一定就不是最值。那么怎么办呢?你可以在开始搜索之前,先根据某些先验知识,估计一下目标节点的估价函数值。然后在算法的开头加上一句:如果最终搜索到的估价函数值小于我们所估计的值,则随机生成另一个结点,重新开始搜索。这样就可以在一定程度上解决问题。这种方法也被称为:“随机重启爬山法”。

  如果遇到了“高原”该怎么办?你只要设置一个“横向移动”程序就可以了。当该节点与相邻结点的值相等时,暂时停止搜索行为,随机找一个相邻结点作为自己的下一个结点,直到相邻结点中出现比自己更高值的结点。这样的话,理论上只要你有足够的时间,你总能拜托高原。不是现实往往是我们并没有足够多的时间,万一程序运行几个月相信也不是不可能( 哈哈 ),所以一般我们都会给“横向移动”设立一个界限。当横向移动的次数超过一定界限,将停止横向移动,若依旧没有拜托高原,那么只能搜索失败。

  如果遇到了“在山峰左右不断循环”该怎么办?还能怎么办,重新建模呗。事实上,这儿确实记录了其他方法。比如,你可以随机生成另一个结点,然后重新进行搜索。毕竟其他途径逼近极值点的话,可能不会出现这样的问题。但是这种方法可能还不如去重新建模来得实在点。

  爬山算法有很多变式,但是内核都是一样的。理解了我上面所写的内容,学什么样的变式都会很快的。要是觉得这个算法很有意思,想要继续学习的话。你可以去学一下“禁忌搜索”和“STAGE”算法。

  我想了一下,笔者的精力和时间毕竟有限,为了更新更多的内容,该贴链接的还是要用贴链接来解决。实在找不到的,我会自己进行讲解。适当的情况下,我再进行补充。

  依旧用之前的爬山例子做模型。现在我们假设一个小孩子也想要到达山顶,但是这个小孩子不喜欢一般的走路方式,他喜欢跳着走。他的想法也很简单,那就是哪个方向比较高,他就往哪个方向跳。我们再加强一下假设,假设这个小孩不是一个普通的小孩,他是一个超人小孩,他随便一跳可能就是十万八千米。因为这个小孩实在心太大了,所以在他跳着爬山的过程中,经常可能会跳过头。不过没关系,因为小孩子的体力是有限的,所以这个超人小孩所跳的距离会越来越短。虽然他经常会跳过头,但是每次他都会盲目地往最高的方向上跳,所以只要给他足够的时间,他就会成为一个典型的模拟退火算法。

  3、遗传算法:如何通俗易懂地解释遗传算法? - 尼布甲尼撒的回答 - 知乎

  关于局部搜索,我们还可以讨论更多的东西。目前我们所讨论的搜索方法都是假定在智能体可以从环境中收集所有信息的情况,然后事实上,智能体在现实环境中只能收集到部分信息。这就导致了不确定性,这意味着环境的变化可能不会如实按照状态空间所记录的那样。这个时候,我们就需要引入“与或树”的概念。但是这里不打算讨论过多的内容。有兴趣的读者可以自行进行探索。

  本文没有讨论博弈搜索和并行搜索,因为这两部分目前属于笔者的知识盲区。若是读者对这两部分感兴趣,可私信我或评论区留言,我再安排时间继续讨论这两部分内容。

网友评论

我的2016年度评论盘点
还没有评论,快来抢沙发吧!