gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:51:42 25 4
gpt4 key购买 nike

我想扩展这个问题:

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

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

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

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

对于一些 alpha 0<α<1 ?

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

编辑:将启发式 ℎ(𝑛) 乘以某个 alpha 0<𝛼<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 启发式相同的麻烦.

关于algorithm - A-star 中成本函数的系数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57974474/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com