algorithm - A-star 中成本函数的系数

Question

我想扩展这个问题:

Why does the A-star algorithm need g(n)?

Dijkstra 算法使用代价函数 f(n) = g(n) 而 A* 使用成本函数 f(n) = g(n) + h(n)，其中 g(n) 是从起始节点开始的路径成本到节点 n，h(n) 是一个启发式函数，用于估计从节点 n 到目标的最便宜路径的成本。

从这个问题中可以清楚地看出，A* 在代价函数中需要它的g(n) 函数。 然而，我的问题如下。可以使用成本函数吗:

f(n) = αg(n) + (1-α)h(n)

对于一些 alpha 0<α<1 ?

我问是因为在某些情况下，我观​​察到(通过系数)将估计成本优先于已经遍历的成本可能要快得多。但是，我不确定这是否仍会产生最佳轨迹？

编辑:将启发式 ℎ(𝑛) 乘以某个 alpha 0<𝛼<1 是允许的，因为此操作仍然低估了 ℎ(𝑛) 是否已经完成(这是获得最佳路径所必需的)。我更关心𝑔(𝑛)的乘法。

Answer 1

f 的全局比例因子，假设它是一个正比例，没有关系，因为f 只是在相对意义上使用。按正比例缩放的数字保持相同的顺序。

因此，f(n) = αg(n) + (1-α)h(n) 可以重写为 f'(n) = g(n) + ( (1-α)/α)h(n)，不相等但等价。因此，尽管您对缩放 g 感兴趣，但实际上这等同于缩放 h，在考虑到全局尺度之后。

效果是将启发式缩放一定数量，只要 (1-α)/α ≤ 1(因此:α ≥ 0.5)就可以，否则会导致与通常情况下 Not Acceptable 启发式相同的麻烦.