AI课堂笔记之Search算法介绍: BFS

对于goal-based Agent, search和planning算法被经常性的使用以找到我们的Goal。此章节着重讲述我们的search算法。

Search算法具体用在什么情况下呢?

游戏里NPC的路径设置。最近玩了个游戏，叫明日之后。这里面NPC用到了Search的算法，当你在僵尸NPC的攻击范围内时，僵尸会来攻击你。在你玩游戏时，你会发现僵尸总会以最短距离攻击过来。所以大家可以思考一下，在这个僵尸NPC上，到底用了怎样的Search算法。

我们通提到的Search算法着重分为两类: Uninformed(blind) search和informed search。

Uninformed Search顾名思义，盲目搜索。在现实生活中大家都有经验啊，因为盲目，你可能找东西花的时间多，你也可能搜索容量大。比如你找钥匙，如果你的钥匙丢在外面，你搜到钥匙的时间一定比你在家里弄丢钥匙搜索的时间长，当然你要是在外面丢了钥匙，很大的可能性是找不回来的。而为了定义search算法的特征（以上提到了的时间长短，找不着的回来，等问题），我们引入了Completeness，Optimality， Time and Space complexity这几个概念(to evaluate the search strategies)。

这次小结主要介绍以下Uninformed search:

*  Breath-First search(BFS): 广度优先搜索

*  Depth-First Search(DFS): 深度优先搜索

*  Uniform-Cost Search

*  Depth-limited Search

*  Interactive Deepening search

---

                                                                  *Breath-First search*

顾名思义，着重于横向搜索:

AI课堂笔记之Search算法介绍: BFS

/1.1 BFS/

@/FIFO(First in First out)/

上图可视，BFS拥有FIFO(First-IN-First-OUT)的特征。

1. 搜索A点得到B，C两个点，Clear A点。（Frontier是B，C）

2. 搜索B点，得到D，E两个点。Clear B点。（Frontier是C，D，E）

3. 以此内推。。。。

这种形式的Memory处理方法可以用以下圆筒模型定义:

AI课堂笔记之Search算法介绍: BFS

/1.2 FIFO Model/

@ Completeness:

Yes,有且只要branching factor（通常用b表示）有限。

（completeness 是用来表示Goal的达成度的。如果Goal能够达成，Completeness就是Yes，反之为No）

  这个可以很好的理解，branching factor表示的是每一层展开的路径数。如果路径数无限，那怎么能找到最终解。

@ Optimality:

Yes, 有且只有path-cost是一个non-decrease function的时候。

AI课堂笔记之Search算法介绍: BFS

/1.3 Problem of BFS/

@ Time complexity:

BFS的cost很高，因为会花很长的时间，因此Time complexity的计算量很高:

1+b+b^2+b^3+...+b(b^d−1)        b: branching factor

由以上式子可以看出，BFS是一层一层的展开的，所以复杂度由指数形式增长。因此time complexity也可以写成O(b^(d+1))

@ Space complexity:

Space complexity表示的是Memory的大小，复杂度计算跟上面Time complexity相同，不过Time complexity会多加一个b的(d+1)次方。因为需要验证当depth等于d时，是否把所有情况展开完。

---

                                                                关注个人公众号: CS课堂小记

                                                                        ｜更多资料查询 |