人工智能搜索策略(上)

人工智能搜素策略

状态空间盲目搜索  

 广度优先搜素(Breadth-First-Search)   

深度优先搜素(Depth-First-Search)  

状态空间启发搜索 

  A搜索算法(A search algorithm)

A星搜索算法(A Star search algorithm)

状态空间盲目搜索

首先是思想基础,在此我罗列了BFS和DFS的科学定义,另还有我的通俗解释

   广度优先搜索: 从初始节点S0开始逐层向下扩展,在第n层节点还没有全部搜索完之前,不进入第n+1层节点的搜索。Open表中的节点总是按进入的先后排序,先进入的节点排在前面,后进入的节点排在后面。

   深度优先搜索: 从初始节点S0开始,在其子节点中选择一个最新生成的节点进行考察,如果该子节点不是目标节点且可以扩展,则扩展该子节点,然后再在此子节点的子节点中选择一个最新生成的节点进行考察,依此向下搜索,直到某个子节点既不是目标节点,又不能继续扩展时,才选择其兄弟节点进行考察。

如果你对上述的定义感到讨厌(当然这是不好的),不妨看看下面我的通俗解释:

广度优先搜索:假如采用BFS进行搜索查找N,那么就是先搜索第一层,如果第一层没有就搜索第二层,然后再搜索第三层

深度优先搜索:假如采用DFS进行搜索查找N,那么先选择一个子数,比如左子树,然后在选择左子树的子节点,直到目标没有找到或者没有子节点再返回,也就是说深度优先搜索是一路走,不到天黑不回头

理解到字面意识绝不意味着结束,下面是一个九宫问题(八数码问题),相信他会让你进一步理解

我们的目的是用最少的步骤移动空格,把S0变成SG,而空格只能选择左右上下移动

1)采用广度优先搜索

上图就是采用广度优先搜素策略的解法,不要带有恐惧的第一感觉去看这个图,仔细看看它真的非常简单,第一次先列出空格向上下左右走的情况,假如我们讨论图一1到图二2,1图的空格向左走得到了2,然后2由于左边没有了所以只有三种选择,再看看这三种选择,如果向右走显然就回到了图一,因此经过过滤与筛选图二只有两种走法,然后再继续直到找到目标节点 (图26)。

2)采用深度优先搜索

很遗憾的是没有画出完整的解法图,因为实在太长了,这就是深度优先搜索,一路走,不到天黑不回头。

状态空间启发性搜索

假如形象来所BFS和DFS,BFS像一个胆小的孩纸,遇到困难会尝试每一种解决方法,DFS,像一个胆大的孩纸,遇到困难会选择一种解决方法进行实践,直到解决或者实践失败

BFS和DFS不适用于人工智能,因为他没有体现出一种智能,只是盲目的寻找目标,试想一下,如果九宫格变成了一百宫格,而解法是在一般树的最后一层,那BFS和DFS的性能无法直视,于是就产生了适用于人工智能的启发性搜索-A*搜索(这里我不会讲解A*搜索算法,而是A搜索算法)

在讲它之前有必要了解一下启发性概念和估价函数

     启发性信息的概念:

     启发性信息是指那种与具体问题求解过程有关的,并可指导搜索过程朝着最有希望方向前进的控制信息。    

估价函数:

     用来估计节点重要性的函数。估价函数f(n)被定义为从初始节点S0出发,约束经过节点n到达目标节点Sg的所有路径中最小路径代价的估计值。它的一般形式为:

             f(n)=g(n)+h(n)

其中,g(n)是从初始节点S0到节点n的实际代价;h(n)是从节点n到目标节点Sg的最优路径的估计代价。 

如果时间充足建议你多度一下上方绿色部分,并记住上面的形式,它将会很有用

还是接着上面的九宫问题,如果我们考虑用A*搜解决就可以设估价函数如下:

f(n)=d(n)+W(n)

d(n)表示节点n在一般搜索树中的深度

W(n)表示节点与Sg不匹配的个数,W(n)的值越大就表明这个方法离成功越远

上图就是利用A搜索 (注意不是A星)的解法图,每个格子左上方的值表示估价函数f(n)的值,将选择f(n)最小的路走,直到成功,就如上图,第一层(假设root不算层),每个走法的估价值分别是4,4,5,5,所以我们根本不考虑5的情况,大大减小了运行时间,从而快速找到目标点。

由于其它关系我准备把A*算法放在(下)中讲解,希望你能认真体会A算法,另我把本文制作成了一个doc文档以供离线浏览http://download.csdn.net/detail/u013524455/6893047

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PPV课数据科学社区

【学习】《R实战》读书笔记(第二章)

“读书会是一种在于拓展视野、宏观思维、知识交流、提升生活的活动。PPV课R语言读书会以“学习、分享、进步”为宗旨,通过成员协作完成R语言专业书籍的精读和分享,达...

36890
来自专栏微信公众号:Java团长

写出优质Java代码的4个技巧

如果现在要求对你写的Java代码进行优化,那你会怎么做呢?作者在本文介绍了可以提高系统性能以及代码可读性的四种方法,如果你对此感兴趣,就让我们一起来看看吧。

8010
来自专栏阮一峰的网络日志

贝叶斯推断及其互联网应用(三):拼写检查

(这个系列的第一部分介绍了贝叶斯定理,第二部分介绍了如何过滤垃圾邮件,今天是第三部分。) 使用Google的时候,如果你拼错一个单词,它会提醒你正确的拼法。 比...

430120
来自专栏CreateAMind

CS231n课程笔记翻译:Python Numpy教程

译者注:本文智能单元首发,翻译自斯坦福CS231n课程笔记Python Numpy Tutorial,由课程教师Andrej Karpathy授权进行翻译。本篇...

12730
来自专栏Golang语言社区

麻将游戏数据结构和AI算法

用休息时间零零散散写完了网络麻将游戏,感觉其中有不少值得记录的东西。 基础数据结构     数据结构确定决定了程序的开发难易程度,就像是游戏的骨架,对于电脑AI...

1.1K20
来自专栏数据分析

[数据分析工具] Pandas 功能介绍(二)

我们需要看第一季度的数据是怎样的,就需要使用条件过滤

25270
来自专栏Hongten

Lucene学习总结之一:全文检索的基本原理

根据http://lucene.apache.org/java/docs/index.html定义:

1.5K30
来自专栏数说戏聊

Python3分析Excel数据

使用xlrd和xlwt扩展包,确定工作簿中工作表的数量、名称和每个工作表中行列的数量。 1excel_introspect_workbook.py

13120
来自专栏代码永生,思想不朽

utf8中文字符串的多模式匹配算法的优化

上个月接触到了我组的一个关于在海量文本中匹配字符串业务。读源代码时发现一些问题,并针对这些问题做了优化工作,效果非常明显。

52630
来自专栏数据分析

[数据分析工具] Pandas 功能介绍(二)

条件过滤 我们需要看第一季度的数据是怎样的,就需要使用条件过滤 ? 体感的舒适适湿度是40-70,我们试着过滤出体感舒适湿度的数据 ? 最后整合上面两种条件,在...

37760

扫码关注云+社区

领取腾讯云代金券