Longest Path A*, Admissible Heuristics, and Optimalness

Question

Im working on a modified A Star algorithm, that instead of attempting to find the shortest path, it tries to find the longest past, or in my specific case, the highest weighted path.

I have some number of classes, each with a list of unique nodes, with each node having its own value. Im attempting to determine the best possible combination of a node from each class to determine the combination or path that has the greatest weight. To do this, I am viewing these classes as a tree, with each Level having the nodes contained within a single class.

Then I search through this tree using A Star, or more specifically, im searching through my tree based on a search stack. Once a node is explored, its children are inserted in a sorted order based on their weight (plus their ancestors weight) plus the possible future weight (my heuristic). Then the top of the stack, with the highest value is selected to search next.

To do this I have an overestimating heuristic, that is it never underestimates the the optimal solution.

If I am looking for the highest weight and not the lowest weight, is this heuristic admissible, and thus my algorithm optimal?

PS: A FormalIsh defination of the current algorithm.

Let S = {S₁, S₂, ... , S_n}

and each S_i has a set of items and a NULL, which represents an item not chosen from this set.

S_i = {I₁, I₂, ... , I_m, NULL}

Also each item only ever exists in one set, IE S_i U S_j = S_i + S_j

Each Item, I_i has an associated value, V_i.

The problem is to select a maximum of M offers, one from each set, when summed yield the highest value. I call this selection a Path, P_i. A path can be complete, meaning it has a selection from all S, or it can be partial where only x offers are contained within it. Also M

In addition, there exists a function IsCompatable(path) that returns true if a path is compatible. Whether a path is compatible or is completely arbitrary. The Max valued path must be compatible. This is why I can not trivially select the M largest Items from each set.

In addition each set contains a NULL item, so that an item need not be selected from that set.

The Trivial Algorithm would to make a search tree and generate all possible combinations of items in S, with each path to the trees leaves said to be a path.

let G(P) be the current value (the summed value of each item) of the partial path. Let H(P) be an estimation (heuristic) of the value of the future path. H(P) = The Y values from Y items from Y S_i in S. Each item is the item with the maximum value in the S_i where i > len(P). Y = M - the current length of the partial path P.

To Find the path with the greatest value, I keep a sorted Queue of partial paths, sorted on their values + their possible future values, ie G(P_i) + H(P_i). I Initialize this Queue by adding paths contained in S₁.

While the Queue is not empty or a path has not been found:
    p = Pop the path from the top of Q
    if p is Complete:
        A full path has been found
        return p
    find the possible children of p by adding an item to p from the next set.
    for child in Children:
        if IsCompatable(child):
            add child back to Q in sorted order on G(child) + H(child)

There it is, now is my Heuristic admissible?

Answer 1

It seems to me (and correct me if I'm wrong) that a regular A* algorithm would work absolutely fine with your problem. The problem is that you're confused about the word underestimates. When we're searching for the shortest path we want a heuristic that will never lead us down a path that will be longer than what we estimate it to be, in your case you never want to be led down a path that will be less than what you estimate it to be (which you say you have).

A heuristic is a function that gives $h(n) = 0$ at the goal.

An admissible heuristic is one that never overestimates the distance to the goal. In your cause you want the longest path rather than the shortest, so an admissible heuristic never underestimates the distance to the goal.

So if you have a heuristic that gives you at least the correct distance from the current node to the goal node or a larger value and you order your queue by largest $f(n)$ then you have a correct implementation of A*.

On the other hand if your heuristic both may underestimate or overestimate you're aren't guaranteed to find an optimal path.

We can prove the optimality of this easily (this is an adapted proof from Russell and Norvig's Artificial Intelligence A Modern Approach).

Let $G$ be an optimal goal state, with path cost $f^*$. Let $G_2$ be a suboptimal goal state with path cost $g(G_2) < f^*$. Now assume that A* has selected $G_2$ from the queue. Because $G_2$ is a goal state it would terminate the search with a suboptimal solution.

Consider a node $n$ that is a leaf node on an optimal path to $G$. Because $h$ is admissible (never underestimates), we must have

$f^* \leq f(n)$

And if $n$ was not chosen over $G_2$ then

$f(n) \leq f(G_2)$

Combining these we get

$f^* \leq f(G_2)$

Because $G_2$ is a goal state $h(G_2) = 0$ thus $f(G_2) = g(G_2)$. So we have a contradiction that $f^*$ is an optimal longest path and that $G_2$ is suboptimal. Thus A* will never expand a suboptimal solution and is an optimal algorithm.