启发式使用 A* 找到具有最高增益的路径 [英] Heuristic for using A* to find the path with the highest gain

问题描述

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

Suppose that I want to change the logic in A*, trying to find the most useful path (i.e., the one with the highest gain) instead of finding the shortest path (i.e., the one with the lowest cost).

就我而言，目标没有固定为唯一的结束节点.一个节点被定义为任何距离起点B的节点.

In my case, a goal is not fixed as a unique ending node. A node is defined as any node having distance B from the starting point.

在普通版本(寻找最短路径")中，我被要求不要高估成本(即找到小于或等于实际成本的启发式).

In the vanilla version ("finding the shortest path") I am required to not overestimate the cost (i.e., finding a heuristic that is less or equal to the real cost).

在我修改后的版本中(找到最有用的路径")，边被标记为效用而不是成本，我想最大化最终收益，考虑到通过最大值的限制B边.我是否应该高估效用(即找到大于或等于实际效用的启发式算法)以使 A* 起作用?

In my modified version instead ("finding the most useful path"), edges are tagged with the utility and not with the cost, and I want to maximize the final gain, given a constraint of going through a maximum of B edges. Should I overestimate the utility (i.e., find a heuristic that is greater or equal to the real utility) in order to make A* work?

更正式，让

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

是一个节点的效用，由:

be the utility of a node, composed by:

• g(n):从起始节点到n
的收获
• h(n):启发式，即当从 n 到目标(目标是距离起点是B)

• g(n): what I gain when going from the starting node to n
• h(n): the heuristic, i.e., an estimate of what I gain when going from n to the goal (where the goal is a node whose distance from the starting point is B)

是否应该高估h(n)并最大化f(n)以识别最佳路径?

Should h(n) be overestimated and f(n) be maximized in order to identify the best path?

注意B是一个预算，因此可以完全花掉，即不需要找到比B步短的路径.

Notice that B is a budget, and thus it can be spent completely, i.e., it is not necessary to find a path that is shorter than B steps.

推荐答案

你的问题是最长路径问题，这是强烈的 NP-Hard.这意味着，不仅(几乎肯定)没有快速精确算法，而且还有(几乎肯定)没有好的>近似算法.

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.

正如@Charles 所暗示的那样，否定边权重的符号是行不通的，因为 A* 无法处理负边权重.以及其他算法，可以处理负边缘-weights 仍然无法处理负循环.

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.

这篇关于启发式使用 A* 找到具有最高增益的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！