如何证明统一成本搜索是 A* 的一个特例?我如何证明这一点?
如何证明统一成本搜索是 A* 的一个特例?
人工智能
比较
搜索
证明
一个明星
统一成本搜索
2021-11-03 09:17:53
1个回答
是的,UCS 是 A* 的一个特例。
UCS 使用评估函数, 在哪里是从起始节点到路径的长度,而 A* 使用评估函数, 在哪里与 UCS 中的含义相同,并且,称为“启发式”函数,是对距到目标节点。在 A* 算法中,必须是可接受的。
UCS 是 A* 的一个特例,对应于具有. 启发式函数其中有,, 显然是可以接受的,因为它总是“低估”到目标的距离,它不能小于,除非你有负边缘(但我假设所有边缘都是非负的)。所以,确实,UCS 是 A* 的一个特例,它的启发式函数甚至是可以接受的!
用一个例子来看这个,只需画一个简单的图形,然后应用 A* 算法使用, 对所有人,然后将 UCS 应用于同一图形。您将获得相同的结果。