Find minimal path in a tree with multivalued nodes

Question

Hi

My math classes are far behind, and I'm currently struggling to find a decent solution to a problem I'm having: I have a tree, in which nodes are actions, and are "weighted" according to multiple criteria : the cost of said action, the time it will take, the necessary resources, the disturbance, etc...

And I want to to find in this tree the path that minimizes both the cost AND the time for example, or the disturbance AND cost AND time, etc. My problem is that I have no idea on how to do it, except by coming up with a global cost function F(cost, time, resources,...), and apply a regular tree traversal algorithm using the result from F(...) as my only weight. But then, how do I come up with F ? Something like "F(cost, time, resources) = a * cost + b * time + c * resources" feels very "unprofessional"...

Edit:

I wanted to avoid the word "summing" as I wasn't sure it was really the way to go, but in essence, that's what I'm doing: computing a total cost for each "path" or "branch" that goes from that top node, to one of the leafs, and choosing the "path" or "branch" that minimizes the cost. The problem being that each node has a weight based on the time necessary, on financial cost, on resource usage, etc.

So it seems inevitable to have to come up with a formula, as Stephan says, that will reduce all these parameters to one global cost, per node, which I can then sum across nodes as I travel down the tree, and pick the path that minimizes the total cost.

So I guess my question really is, it there a methodology to choose that function ?

Thanks for your answers and comments, it's starting to be a bit more clear in my head now.

Answer 1

Coming up with F is the most important thing. If I can give you 6 cost and 5 time or 5 time and 6 cost, which do you prefer? Your cost function needs to take that into consideration. There's no algorithm that's going to solve that problem for you, unfortunately. I denied that for a week before I sat down and wrote F for an optimization application I was working on. Worst case, leave parameters for the user to tinker with.

Answer 2

Why wouldn't a normal graph search algorithm like A* work?

For the path-cost function, you could use the running sum of the relevant criteria. The distance to the goal is more difficult...

It could be the distance to the nearest leaf, pre-computed for all or some nodes, although that sounds awfully expensive. Depending on the structure of your tree, you could come up with a cheaper under-estimate - if it's perfectly balanced, for example, it's trivial.

Answer 3

Let's say we have four pairs (x, y) like (1, 4), (1, 5), (2, 3), (3, 3). Now you want to minimize "both x and y". What do you mean? If you minimize first x and then y you end up with (1, 4). If you minimize first y and then x you find (2, 3).

Unless you choose a global cost function F(x, y), like in your observation, I can't see any meaning of "both". (Anyway, once F is chosen, there may still be multiple minimum points.) By the way, in my opinion a linear combination (the positive multipliers a,b,c being understood as "weights") is not "unprofessional" at all, at least if you have no idea of what a more suitable cost function could be.

Edit:

So it seems inevitable to have to come up with a formula, as Stephan says, that will reduce all these parameters to one global cost, per node, which I can then sum across nodes as I travel down the tree, and pick the path that minimizes the total cost.

Caution. Indeed this strategy makes sense only if F is linear. Surely cost, time, resources etc. are additive functions, in the sense that time(node1 -> node2 -> node3) = time(node1) + time(node2) + time(node3), but in general this is not the case for F, unless it is linear. (i.e. F(cost(node1 -> node2)) = F(cost(node1) + cost(node2)) != F(cost(node1)) + F(cost(node2)). )

If you choose a nonlinear global cost function, the right strategy is to compute, for each node, the total cost, total time, total resources from the root to that node, and compute (then minimize) F only for the terminal nodes.