AI Search之Uninformed search: Uniform search

相对于BFS，Uniform-Cost search相对的有策略性一点。BFS采取FIFO的形式进行搜索，这种形式有一定的弊端，如果我一直从左到右的搜索，会发生图1.3所发生的问题。BFS这种完全不考虑Cost的傻瓜算法需要得到优化。而Uniform-cost search便是他的优化算法。

假设 - evaluation function: f(n)

        -total path cost: g(n)

Uniform-cost search满足条件f(n)=g(n)。

Uniform-cost search 总是展开最小g(n)的节点。

图片发自简书App

/1.4 Uniform-cost Search/

如图可视，第一层展开后得到A，B，C三个节点。A是最小Cost的节点，展开得到G。现在G，B，C是我的frontier，我们先验证frontier里面的最小值，发现B最小且可以展开，由此得到g(n)等于10的Goal。

相比较以上两种算法，uniform-cost search虽然只加了g(n)这一个条件，却能得到最优解，因此这个算法的实用性十分高。(ATTENTION: 最优解！)

当然，通过分析，我们也可以得出，BFS那种没有目的性的搜索就好比Uniform-Cost search的特殊情况，我们令每段step cost相同或者等于1，那我们的Uinform Cost Search也会像BFS一样从左至右按部就班的搜索。

* Completeness:

Yes, 当然，有且只有我们的step cost>0的情况。

可以想象，如果step cost<=0，有可能发生以下情况。

图片发自简书App

/1.5 Completeness Proof/

* Optimality:

Yes, 上面所解释的“最优解“。

* Time Complexity:

O(b^(1+C/ε))

C*: 从搜索点n到Goal的optimal Cost

ε:预估的step cost

Solution:

图片发自简书App

/1.6 Time Complexity Proof/

* Space complexity:

O(b^(1+C/ε))

证明同Time Complexity。

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

                                                              |更多资料咨询|