启发式使用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难。这意味着，不仅存在的（几乎可以肯定）的没有快速的确切的算法，但也有（几乎可以肯定）的没有很好的近似的算法。

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屋！