So my initial question is more related to coding, but I decided to ask here because I feel there must be some established algorithm to do this. This question is heavily simplified just to be clear.
Lets say I have a set of 3D coordinates ( X,Y,Z) where Z is an indication of height.It is possible to fit all coordinates in a 100X100 2D table ( so 10,000 coordinates lets say) where each position in the table is corresponding to its X,Y values:
(1,1,67) (1,2,17) (1,3,52)...
(2,1,14) (2,2,91) (2,3,109)...
.
.
.
now lets say I start at a random coordinate, and I wish to to find a route with n steps, such that the sum of all of its Z values is the maximum possible given that n. A step could be made along one of 4 vectors ( up/down/left/right ) so 4 options are possible at each step. The final destination does not matter- only the path of selected coordinates for the route - so its ok to finish on either coordinate ( without repetition - so no coordinate could be selected twice).
Is there an algorithm which can take a matrix/coordinate set and could spit out n coordinates which take me along the most elevated path ( without brute of course- because it would just be impossible for even a relatively small n).
I think of it generally as a route to navigate a 3D non continuous surface (made of steps with Z height), by using the most elevated steps, so that there is a minimal travel on the Z vector.
I hope my question was clear, cheers.
You can solve this via integer linear programming as follows. Let $N_{i,j}$ be the set of neighbors of cell $(i,j)$. Let binary decision variable $w_{i,j,k}$ indicate whether cell $(i,j)$ is visited at step $k\in\{0,\dots,n\}$. Let $(i_0,j_0)$ be the fixed starting cell for $k=0$. The problem is to maximize $\sum_{i,j,k} Z_{i,j} w_{i,j,k}$ subject to: \begin{align} \sum_{i,j} w_{i,j,k} &= 1 &&\text{for all $k$}\\ \sum_k w_{i,j,k} &\le 1 &&\text{for all $i,j$}\\ w_{i,j,k} &\le \sum_{(i',j')\in N_{i,j}} w_{i',j',k+1} &&\text{for $k<n$}\\ w_{i_0,j_0,0} &= 1 \end{align} The first constraint forces exactly one cell to be visited at each step. The second constraint forces each cell to be visited at most once. The third constraint forces each subsequent step to visit a neighbor of the current cell. The fourth constraint forces the path to start at cell $(i_0,j_0)$.