Search code examples
algorithmtreea-star

A* vs trees in longest path

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:

  1. Is A* suitable for this type of problem? Will I find the optimal solution by applying it?
  2. 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?
  3. 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.

Solution

  • Analysis

    The reason is as follows. Suppose you assert that a path P is optimal, and have not examined edge e. I can, without loss of generality, set the gain for e to a value greater than the sum of all other gains in the tree. Then your path P is not optimal.

    So any assertion of optimality made before examining all edges' gains is false.

    Conclusion

    If no additional information is given about the gains on edges, you cannot find the optimal path without exploring the entire tree.

    If you had, for example, an upper bound on gain values, you could use A* to more-efficiently find the optimal path and not examine every edge.

    Responses to the changes you made to the question after this answer was written are in the comments below. Make sure to review them.