人工智能的无信息搜索

在人工智能中,当你面对一些问题不知道怎么解决的时候,有一类常用的解决问题的方法,叫做搜索。就好像你在一片迷雾的森林里,不知道怎么办时,走一步算一步,走起来再说。 搜索的话,分为两种类型,一种是无关问题背景信息的搜索,如广度优先搜索、深度优先搜索,另一种是结合问题的背景信息的搜索,如A*搜索,最小代价优先搜索。 每种搜索实现的形式有两种分类,根据展开节点是否曾经被展开过来区分为按树搜索还是按图搜索。按树搜索时,你展开的节点可以包括你已经搜过的节点。而按图搜索,只展开你还没搜过的节点。 接下来了解两种重要的无背景信息的搜索: 一、广度优先搜索:

优先展开同一层级的节点,实现时用的是一个先进先出的队列来保存节点,每次都取出最早加入的节点展开,保证了同一层级依次展开的顺序。

优点:

只要你的问题的代价随着搜索层级的深度递增的就能保证找到最优解。 缺点:

展开的越深,节点以指数级增长,内存容易爆掉。

所以,问题较小时,用广度优先搜索能比较直观的解决问题。 二、深度优先搜索:

只要下一层的节点还能展开,则优先展开它。实现时用的时一个后进先出的队列来保存节点,最后展开的节点加入了队列,只要它还能展开,就继续取出它展开,保证了不断深入的而顺序。

优点:

展开的节点增长是多项式级的,内存消耗小。 缺点:

难以保证能找到最优解,因为当你不确定问题的情况时,搜索就可能无限深入下去而不回头了。

所以需要改进它的缺点。

改进的方式是迭代逐次加深的深度优先搜索。

每次设定一个深度,搜索完以后如果没找到结果,则加深一个深度,再从头到尾搜一遍,不断递增深度,直到找到最优解为止。

这样的搜索方法,即利用了深度优先的内存优势,也因为类似深度优先搜索的逐层递增方式,保证了找到最优解。

原文发布于微信公众号 - 林欣哲(gh_aba6caba3ac7)

原文发表时间:2017-11-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Petrichor的专栏

深度学习: global pooling (全局池化)

今天看SPPNet论文时,看到“global pooling”一词,不是很明白是啥概念。上网查了一下定义,在StackOverflow 上找到了答案:

4133
来自专栏大数据文摘

Python入门之数据处理——12种有用的Pandas技巧

2085
来自专栏算法修养

矩阵快速幂小结

      矩阵快速幂大概是用来解决这样一类问题,当你知道了一个递推式比如a[n]=a[n-1]+a[n-2] 题目要求你求出a[n]。如果n大于1亿怎么办? ...

3155
来自专栏机器学习和数学

[数据结构和算法]《算法导论》动态规划笔记(1)

动态规划是求解最优化问题的方法,这类问题有很多可行解,每个解都有一个值,我们希望寻找具有最优值的解。我们称这个解为问题的一个最优解,而不是最优解,因为可能有多个...

38610
来自专栏深度学习自然语言处理

【笔记】高效率但却没用过的一些numpy函数

最近在看源码的时候,碰到了一些大佬们常用,但自己暂时还没用过的numpy函数,特意来总结下。

642
来自专栏数据魔术师

干货|十分钟教你用动态规划算法解Travelling Salesman Problem(TSP)问题,附代码……

乍一看标题,大家是不是觉得“动态规划”这四个字组合在一起有点眼熟?似乎哪会儿学过来着……但是吧,细细一琢磨,又忘了它具体是什么、怎么用、用来解决哪些问...

4.8K11
来自专栏coolblog.xyz技术专栏

科普:String hashCode 方法为什么选择数字31作为乘子

某天,我在写代码的时候,无意中点开了 String hashCode 方法。然后大致看了一下 hashCode 的实现,发现并不是很复杂。但是我从源码中发现了一...

66819
来自专栏技术翻译

Python中的NLP

自然语言处理(NLP)是数据科学中最有趣的子领域之一,数据科学家越来越期望能够制定涉及利用非结构化文本数据的解决方案。尽管如此,许多应用数据科学家(来自STEM...

2895
来自专栏Pytorch实践

python实现字符串模糊匹配

之前笔者写过一篇文章关于如何做搜索,但那篇文章的角度是从文本相似度角度写的。那种方式是目前发展的趋势,但是真正的搜索特别是网页搜索不可能在大范围的文本之间两两算...

3.5K6
来自专栏机器之心

资源 | Tensorlang:基于TensorFlow的可微编程语言

30711

扫码关注云+社区

领取腾讯云代金券