美文网首页
AI Search之Uninformed search: Uni

AI Search之Uninformed search: Uni

作者: 不拘一格的jojojoahan | 来源:发表于2018-12-12 22:53 被阅读0次

相对于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)的节点。

AI Search之Uninformed search: Uniform search

/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,有可能发生以下情况。

AI Search之Uninformed search: Uniform search

/1.5 Completeness Proof/

* Optimality:

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

* Time Complexity:

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

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

ε:预估的step cost

Solution:

AI Search之Uninformed search: Uniform search

/1.6 Time Complexity Proof/

* Space complexity:

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

证明同Time Complexity。


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

                                                              |更多资料咨询|

相关文章

网友评论

      本文标题:AI Search之Uninformed search: Uni

      本文链接:https://www.haomeiwen.com/subject/bvemhqtx.html