Let T be a tree in which each node represents a state. The root represents the initial state. An edge going from a parent to a child specifies an action that can be performed on the parent in order to change state (the new state will be the child). Each edge is associated with a gain, i.e., I gain something by transitioning from the parent state to the child state.
Moreover, suppose that each path from the root to a leaf node has length Q.
My objective is the one of finding the most promising path of length Q, i.e., the path that guarantees the largest gain (where the path gain is defined as the summation of the gains attached to the edges in the path).
Obviously, I would like to do this without exploring the entire tree, since T could be very huge.
Thus, I thought about applying A*. I know that A* can be used to find the shortest path in a graph, but:
- I don't have costs, I have gains
- I want to find the longest path (actually not the longest in distance from the start node, but the one whose weights, if summed up, give the highest value)
- I have a tree and not a graph (no cycles!)
Eventually, I came up with a set of question that I would like to pose to you:
- Is A* suitable for this type of problem? Will I find the optimal solution by applying it?
- Since A* requires to use an (under)estimate of the cost from the current node to the goal in case of shortest path, am I required to look for an (over)estimate of the gain from the current node to the goal and use it as a heuristic?
- Given a node n in T, my idea was to compute the heuristic h(n) as the summation of the gains achieved by the children of n, which might not be so tight. Do you think there could be a better solution?
EDIT: given a node n in the tree, the gain attached to an edge outgoing from n cannot be greater than a quantity U(n). Moreover, U(n) becomes smaller and smaller as the depth of n increases.