This is a computational challenge. I am looking for a clever simplification or heuristic.
Imagine a multi-way tree. Each node has three child branches. Consider them to be decisions; do A, do B, do C. Further imagine you're tracing a path from root to every leaf node, a trajectory.
Example:
Root
| | | | | | | | |
A1, B1, C1 A2, B2, C2 A1, B1, C1
Say you have a tree of $3$ levels. Root is at $0.$ Then number of nodes $3^0 + 3^1 + 3^2 + 3^3 = 1+3+9+27 = 40 = (3^{(n+1)}-1)/2 = (3^4-1)/2.$ On the last level, there are $3^3=27$ or $3^n$ nodes, or more specifically trajectories.
I can't traverse this tree after $n>20$ and I need to explore $n=500$ which is $3^{500}.$ In my domain, I am assigning a cost to each decision (money/points/weights). Now, I am only interested in the top $5$ and bottom $5$ trajectories according to my cost function.
Does anybody think there is a way of finding maximum and minimum of this tree given some cost function without exploring $3^n$ paths? Or knows other ways of reducing the sample space.
Thank you