Optimizando una ruta en una superficie 3D

Question

Entonces, mi pregunta inicial está más relacionada con la codificación, pero decidí preguntar aquí porque siento que debe haber algún algoritmo establecido para hacer esto. Esta pregunta está simplificada en gran medida solo para ser clara.

Supongamos que tengo un conjunto de coordenadas 3D (X, Y, Z) donde Z es una indicación de altura. Es posible ajustar todas las coordenadas en una tabla 2D de 100X100 (así que digamos 10,000 coordenadas) donde cada posición en la tabla corresponde a sus valores X, Y:

(1,1,67) (1,2,17) (1,3,52)...
(2,1,14) (2,2,91) (2,3,109)...
.
.
.

Ahora supongamos que empiezo en una coordenada aleatoria, y deseo encontrar una ruta con n pasos, de manera que la suma de todos sus valores de Z sea la máxima posible dada esa n. Un paso se podría dar a lo largo de uno de 4 vectores (arriba/abajo/izquierda/derecha) así que 4 opciones son posibles en cada paso. El destino final no importa, solo la ruta de coordenadas seleccionadas para la ruta - así que está bien terminar en cualquier coordenada (sin repetición - así que ninguna coordenada podría ser seleccionada dos veces).

¿Existe un algoritmo que pueda tomar una matriz/conjunto de coordenadas y podría devolver n coordenadas que me lleven por el camino más elevado (sin fuerza bruta, por supuesto, porque sería simplemente imposible incluso para un n relativamente pequeño)?

Lo pienso en general como una ruta para navegar un superficie 3D no continua (hecha de pasos con altura Z), utilizando los pasos más elevados, de manera que haya un mínimo recorrido en el vector Z.

Espero que mi pregunta haya sido clara, saludos.

Answer 1

Puedes resolver esto a través de la programación lineal entera de la siguiente manera. Deja que $N_{i,j}$ sea el conjunto de vecinos de la celda $(i,j)$. Deja que la variable de decisión binaria $w_{i,j,k}$ indique si la celda $(i,j)$ es visitada en el paso $k\in\{0,\dots,n\}$. Deja que $(i_0,j_0)$ sea la celda de inicio fija para $k=0$. El problema es maximizar $\sum_{i,j,k} Z_{i,j} w_{i,j,k}$ sujeto a: \begin{align} \sum_{i,j} w_{i,j,k} &= 1 &&\text{para todo $k$}\\ \sum_k w_{i,j,k} &\le 1 &&\text{para todo $i,j$}\\ w_{i,j,k} &\le \sum_{(i',j')\in N_{i,j}} w_{i',j',k+1} &&\text{para $k La primera restricción obliga a que exactamente una celda sea visitada en cada paso. La segunda restricción obliga a que cada celda sea visitada a lo sumo una vez. La tercera restricción obliga a que cada paso subsiguiente visite un vecino de la celda actual. La cuarta restricción obliga a que el camino empiece en la celda $(i_0,j_0)$.