对于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*
顾名思义，着重于横向搜索:
/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处理方法可以用以下圆筒模型定义:
/1.2 FIFO Model/
@ Completeness:
Yes,有且只要branching factor（通常用b表示）有限。
（completeness 是用来表示Goal的达成度的。如果Goal能够达成，Completeness就是Yes，反之为No）
这个可以很好的理解，branching factor表示的是每一层展开的路径数。如果路径数无限，那怎么能找到最终解。
@ Optimality:
Yes, 有且只有path-cost是一个non-decrease function的时候。
/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课堂小记
｜更多资料查询 |
