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

Question

我想我在这个 wiki 上发现了一个问题页面上发现了一个问题：

我认为`

成本最多为 ε 倍

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

成本小于 ε 倍

反而。

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

提前谢谢你的帮助 ：）

Answer 1

我相信以“加权 A*。如果 ha(n) 为”开头的段落是正确的，并且保证找到的路径的成本最多是 eta 乘以最佳路径的成本是您想要的保证 - 因为您正在寻找成本最低的路径并试图减少 cpu 时间您正在解决次优（更高成本）的解决方案，但要保证成本不会太差 - 最多 eta 乘以最佳路径的成本。

我确实认为在本段中使用 eta 与在上段中使用不一致 - 我不知道这是否是一个错误，或者它是否源于加权 A* 和更近似解的一般定义。

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