algorithm - 维基百科上的加权 A*

Question

我想我在这个 wiki 上发现了一个问题 page :

我认为`

have a cost of at most ε times

在加权A*算法部分应该是

have a cost less than ε times

相反。

因为这里假设ε > 1。但是我不确定，只是想听听大家对此的看法..

提前感谢您的帮助:)

Answer 1

我相信以“Weighted A*. If ha(n) is”开头的段落是正确的，并且保证找到的路径的成本至多是 eta 乘以最佳路径的成本是对你的一种保证想要 - 因为您正在寻找成本最低的路径并试图减少 cpu 时间，所以您正在接受一个次优(更高成本)的解决方案，但要保证成本不会太差 - 最多是 eta 的成本最佳路径。

我确实认为在本段和上一段中使用 eta 之间存在不一致 - 我不知道这是一个错误还是源于加权 A* 之间约定的不幸差异以及更一般的近似解定义。

该段与http://inst.eecs.berkeley.edu/~cs188/sp11/slides/SP11%20cs188%20lecture%204%20--%20CSPs%206PP.pdf处的注释一致- pdf 第 5 页的底部和粗略的证明。当加权 A* 认为它有一个成本为 g(x) 的解决方案时，所有仍在运行的节点必须至少有一个预测成本 g(y) + eh(y)。为了获得最大可能的误差，假设 g(y) 为零并且 eh(y) = g(x) 对于正确的解 y 并且我们看到解 A* 认为它找到的是 y 的 e 倍 - 因为我们假设原始的 h() 是可接受的，因此是成本的上限。