开发者

Artificial Intelligence Uniform-cost search

I have some questions about the search functions in artificial intelligence that I cannot understand. I know that Uniform-cost search is a special case of the A* search algorithm if its heuristic is a constant function. Also I k开发者_StackOverflow中文版now that Breadth-first search (BFS) is a special case of A* when all edge costs are positive and identical. Best-first search is also a special case of A* search. But ho can I show that? How can I prove that all the above are correct?


Erm, I don't really know how to state it elegantly, but everything you said is true by... definition!

In A*, you've got a heuristic function, and you greedily explore your tree selecting the most promising branches.

If the cost for each edge is identical, then A* only starts with the nodes that are at "distance 1" because they all have the smallest cost : 1. Then, A* explores the nodes at "distance 2" from the root node, because their cost is now the smallest from all possible nodes : 2. Recursively, this leads to BFS.

This is identical for Uniform-cost. For Best-First search, it's a bit different, A* is a special case of Best-first search, not the other way round =).

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜