对于统一的成本搜索,C会首先扩展D,因为这是最便宜的,还是G,因为目标是?
通常的规则是,统一成本搜索将扩展最便宜的节点,然而G是目标,而且它将是最低成本?
你能解释一下吗?

发布于 2020-04-28 01:30:39
在本例中,您已经找到了成本为4的目标。但是,想象一下,如果存在从D到G的成本为0.5的边,那么,您将需要继续从S-A-C-D-G找到成本为3.5的路径。如果你一找到低于C的目标就停下来,你会得到一个次优解的结果。
但是,如果您知道最小边成本是1,那么您可以停止,因为通过D的最佳路径将成本为4,这与路径S-A-C-G相同。
这里的要点是,你不能停下来,直到你证明你正在探索的每一条道路都将至少与迄今为止找到的最佳解决方案一样昂贵。
https://stackoverflow.com/questions/61448850
复制相似问题