Reordenamiento de una secuencia de puntos

Question

Dada una secuencia finita de puntos $\{\boldsymbol{\alpha}_k\}_{k=1}^m$, aquí $\boldsymbol{\alpha}_k\in \mathbb{R}^n$. Mi pregunta es:

¿Cómo encontrar una reordenación de $\{\boldsymbol{\alpha}_k\}_{k=1}^m$ tal que $$\sum\limits_{k=1}^m|\boldsymbol{\alpha}_{\tau_k}-\boldsymbol{\alpha}_k|$$ alcance a MÁX. Aquí $\{\boldsymbol{\alpha}_{\tau_k}\}_{k=1}^m$ es la reordenación y $|\boldsymbol{\alpha}_{\tau_k}-\boldsymbol{\alpha}_k|$ significa la distancia euclidiana entre $\boldsymbol{\alpha}_{\tau_k}$ y $\boldsymbol{\alpha}_k$?

Por favor, proporcione un algoritmo con la menor complejidad temporal posible.

Answer 1

Esto es esencialmente equivalente a resolver el problema del camino más largo (con la métrica euclidiana), que es NP-duro. Por lo tanto, es casi seguro que no se puede encontrar un algoritmo eficiente.