如何证明统一成本搜索是 A* 的一个特例?

人工智能 比较 搜索 证明 一个明星 统一成本搜索
2021-11-03 09:17:53

如何证明统一成本搜索是 A* 的一个特例?我如何证明这一点?

1个回答

是的,UCS 是 A* 的一个特例。

UCS 使用评估函数f(n)=g(n), 在哪里g(n)是从起始节点到路径的长度n,而 A* 使用评估函数f(n)=g(n)+h(n), 在哪里g(n)与 UCS 中的含义相同,并且h(n),称为“启发式”函数,是对距n到目标节点。在 A* 算法中,h(n)必须是可接受的。

UCS 是 A* 的一个特例,对应于具有h(n)=0,n. 启发式函数h其中有h(n)=0,n, 显然是可以接受的,因为它总是“低估”到目标的距离,它不能小于0,除非你有负边缘(但我假设所有边缘都是非负的)。所以,确实,UCS 是 A* 的一个特例,它的启发式函数甚至是可以接受的!

用一个例子来看这个,只需画一个简单的图形,然后应用 A* 算法使用h(n)=0, 对所有人n,然后将 UCS 应用于同一图形。您将获得相同的结果。