相对于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)的节点。
/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，有可能发生以下情况。
/1.5 Completeness Proof/
* Optimality:
Yes, 上面所解释的“最优解“。
* Time Complexity:
O(b^(1+C/ε))
C*: 从搜索点n到Goal的optimal Cost
ε:预估的step cost
Solution:
/1.6 Time Complexity Proof/
* Space complexity:
O(b^(1+C/ε))
证明同Time Complexity。
关注个人公众号:CS课堂小记
|更多资料咨询|
