贪婪搜索和统一成本搜索有什么区别? [英] What is the difference between Greedy-Search and Uniform-Cost-Search?

问题描述

在树中搜索时，我对统一成本搜索的理解是，对于给定节点A，其子节点B，C，D的相关成本为(10、5、7)，我的算法将选择C，作为它具有较低的成本.扩展C之后，我看到节点E，F，G的成本为(40、50、60).它将选择40，因为它具有两个3中的最小值.

现在，这与进行贪婪搜索(您总是选择似乎是最佳操作的方法)不一样吗?

此外，在定义从某些节点到其他节点的成本时，我们应该考虑从树的开始到当前节点的整个成本，还是从节点n到节点n'的成本本身?

谢谢

解决方案

不是.您的理解不太正确.

在进行统一成本搜索的情况下，下一个要访问的节点将是D，因为它从根开始的总成本最低(7，而不是40 + 5 = 45).

贪婪搜索不会返回到树上-它会选择最低值并将其提交.统一成本将从整棵树中选择最低的总成本.

When searching in a tree, my understanding of uniform cost search is that for a given node A, having child nodes B,C,D with associated costs of (10, 5, 7), my algorithm will choose C, as it has a lower cost. After expanding C, I see nodes E, F, G with costs of (40, 50, 60). It will choose 40, as it has the minimum value from both 3.

Now, isn't it just the same as doing a Greedy-Search, where you always choose what seems to be the best action?

Also, when defining costs from going from certain nodes to others, should we consider the whole cost from the beginning of the tree to the current node, or just the cost itself from going from node n to node n'?

Thanks

解决方案

Nope. Your understanding isn't quite right.

The next node to be visited in case of uniform-cost-search would be D, as that has the lowest total cost from the root (7, as opposed to 40+5=45).

Greedy Search doesn't go back up the tree - it picks the lowest value and commits to that. Uniform-Cost will pick the lowest total cost from the entire tree.

这篇关于贪婪搜索和统一成本搜索有什么区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！