Gain maximization on trees

Question

Consider a tree in which each node is associated with a system state and contains a sequence of actions that are performed on the system.

The root is an empty node associated with the original state of the system. The state associated with a node n is obtained by applying the sequence of actions contained in n to the original system state. The sequence of actions of a node n is obtained by queuing a new action to the parent's sequence of actions.

Moving from a node to another (i.e., adding a new action to the sequence of actions) produces a gain, which is attached to the edge connecting the two nodes.

Some "math":

• each system state S is associated with a value U(S)
• the gain achieved by a node n associated with the state S cannot be greater than U(S) and smaller than 0
• If n and m are nodes in the tree and n is the parent of m, U(n) - U(m) = g(n,m), i.e., the gain on the edge between n and m represents the reduction of U from n to m

See the figure for an example.

My objective is the one of finding the path in the tree that guarantees the highest gain (where the gain of a path is computed by summing all the gains of the edges on the path):

Path* = arg max_{path}  (sum g(n,m), for each adjacent n,m in path)

Notice that the tree is NOT known at the beginning, and thus a solution that does not require to visit the entire tree (discarding those paths that for sure do not bring to the optimal solution) to find the optimal solution would be the best option.

NOTE: I obtained an answer here and here for a similar problem in offline mode, i.e., when the graph was known. However, in this context the tree is not known and thus algorithms such as Bellman-Ford would perform no better than a brute-fore approach (as suggested). Instead, I would like to build something that resembles backtracking without building the entire tree to find the best solution (branch and bound?).

EDIT: U(S) becomes smaller and smaller as depth increases.

Answer 1

As you have noticed, a branch and bound can be used to solve your problem. Just expand the nodes that seem the most promising until you find complete solutions, while keeping track of the best known solution. If a node has a U(S) lower than the best known solution during the process, just skip it. When you have no more node, you are done.

Here is an algorithm :

pending_nodes <- (root)
best_solution <- nothing

while pending_nodes is not empty
    Drop the node n from pending_nodes having the highest U(n) + gain(n)

    if n is a leaf
        if best_solution = nothing
            best_solution <- n
        else if gain( best_solution ) < gain( n )
            best_solution <- n
        end if
    else
        if best_solution ≠ nothing
            if U(n) + gain(n) < gain(best_solution)
                stop. best_solution is the best
            end if
        end if

        append the children of n to pending_nodes
    end if
end while