2

假设我想改变 A* 中的逻辑，试图找到最有用的路径（即增益最高的路径）而不是找到最短路径（即成本最低的路径）。

就我而言，目标不是固定为唯一的结束节点。节点定义为距B起点有距离的任何节点。

在香草版本（“寻找最短路径”）中，我需要不要高估成本（即，找到小于或等于实际成本的启发式）。

相反，在我的修改版本（“寻找最有用的路径”）中，边缘被标记为效用而不是成本，并且我想最大化最终增益，给定通过最多 B 个边缘的约束。我是否应该高估效用（即找到大于或等于实际效用的启发式算法）以使 A* 起作用？

编辑：更正式，让

f(n) = g(n) + h(n)

是一个节点的效用，由以下组成：

  • g(n)：从起始节点到n
  • h(n)：启发式，即对我从n到达目标时获得的估计（其中目标是与起点的距离为 的节点B）

为了确定最佳路径，是否应该h(n)高估并最大化？f(n)

请注意，这B是一个预算，因此它可以完全用完，即没有必要找到比B步骤更短的路径。

4

1 回答 1

1

Your problem is the longest path problem, which is strongly NP-Hard. This means that, not only is there (almost certainly) no fast exact algorithm, but there is also (almost certainly) no good approximate algorithm.

You will unfortunately either have to brute-force it, or resort to various global optimization techniques, like annealing, genetic programming etc.

Negating the sign of the edge-weights, as @Charles suggests, will not work, as A* cannot handle negative edge-weights. And other algorithms which can handle negative edge-weights still cannot handle negative cycles.

于 2013-06-06T14:48:26.993 回答