Find the minimum path in a tree with multivalued nodes
My math classes are far behind and I am currently struggling to find a decent solution to the problem I am facing: I have a tree in which the nodes are actions and are "weighted" according to several criteria: cost of the specified action, time required resources, violation, etc.
And I want to find a path in this tree that minimizes both cost and time, like breaking AND cost and time, etc. My problem is that I have no idea how to do this other than by using the global cost function F (cost, time, resources, etc.) and apply the normal 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 "summation" as I wasn't sure if this is really a path, but essentially, this is what I do: calculating the total cost for each "path" or "branch" that goes from that top node. to one of the sheets and selects a "path" or "branch", which minimizes the cost. The problem is that each node has a weight depending on the time needed, financial costs, resource use, etc.
So it seems inevitable to have to come up with a formula, as Stefan says, that will reduce all of these parameters to one global cost per node, which I can then sum across the nodes as I navigate the tree, and choose a path that minimizes the total cost.
So, I think my question is, is there a methodology out there for choosing this feature?
Thanks for your responses and comments, this is getting a little clearer in my head now.
source to share
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 have in mind? If you minimize the first x and then y, you get (1, 4). If you minimize the first y and then x, you will find (2, 3).
Unless you select the global cost function F (x, y) as in your observation, I don't see any meaning of "both". (Anyway, once F is chosen, there may still be multiple minimum points.) By the way, in my opinion, the linear combination (positive factors a, b, c, understood as "weights") are not "unprofessional" at all. at least if you don't know what might be a more appropriate cost function.
Edit:
So it seems inevitable to have to come up with a formula, as Stefan says, that will reduce all of these parameters to one global cost per node, which I can then sum across the nodes as I navigate the tree, and choose a path that minimizes the total cost.
Attention. Indeed, this strategy makes sense only if F is linear. Of course, costs, 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 if it is not linear. (for example, F (cost (node1 → node2)) = F (cost (node1) + cost (node2))! = F (cost (node1)) + F (cost (node2)).)
If you choose a non-linear global cost function, the correct strategy is to compute for each node the total cost, total time, total resources from root to that node, and compute (then collapse) F for terminal nodes only.
source to share
Arriving with F is the most important thing. If I can give you 6 and 5 times or 5 times and 6 costs, which do you prefer? Your cost function should take this into account. Unfortunately, there is no algorithm to solve this problem. I denied this a week before I sat down and wrote an F for an optimization app I was working on. In the worst case, leave parameters for the user to tinker with.
source to share
Why doesn't a regular graph search algorithm like A * work?
For the path cost function, you can use the running sum of the relevant criteria. Distance to the target is more difficult ...
This can be the distance to the nearest leaf, pre-calculated for all or some of the nodes, although it sounds awfully expensive. Depending on your tree structure, you can come up with a cheaper underestimate - if it's perfectly balanced, for example, it's trivial.
source to share