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).
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).
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?
EDIT: More formalized, let
f(n) = g(n) + h(n)
be the utility of a node, composed by:
g(n): what I gain when going from the starting node to nh(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)Should h(n) be overestimated and f(n) be maximized in order to identify the best path?
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.
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.