I have a special kind of decision graph, where Multiple decisions must be made in combination, to accomplish the path. Not sure if Multiobjective or Combinational is the right term here, let me know if there is a better one.
Picture better then words:
We have:
- Joining Nodes (e.g. "Start") which joins decisions or costs nodes together - meaning solution path MUST cover all edges of joining nodes.
- Decision Nodes (e.g. D1,D2,...) and Decision Edges (aka "local solution" - e.g. D1-1, D1-2,...) each solution path may cover only one of the edge of a decision.
- Costs Nodes - (e.g. 3,7,5...) that have cost/reward applied to the Paths that cover it. Technically any node even decision or joining can have costs associated. COSTS MAY BE NEGATIVE.
- Solution Path - goes from a starting node and must cover all edges of connected joining nodes and only one edge of each decision node it meets
Green is the cheapest Path for this example (D1-2,D2-1,D3-1) that you can calculate yourself empirically or combining all possible combinations and sorting by total costs. Total costs of Green path is $5.
Constraints:
- Costs may be negative - in this case it's a reward.
- Cycles are possible - they must be resolved as invalid path.
- Decisions are NOT binary
Goal:
Find the best (BigO runTime) algorithm to find cheapest path covering this kind of graphs (without iterating all possible combinations and calculating its costs)? Pseudo code would help. Also what is the name of such type of decision graph?