Elegir un subconjunto para maximizar la distancia mínima entre puntos

Tengo un conjunto de puntos , y tengo la distancia entre cada punto . Estas distancias son euclidianas, pero los puntos están realmente en un espacio de características. $C$ $D(P_i,P_j)$

De los puntos quiero elegir un subconjunto de puntos. Llame a este subconjunto . Quiero elegir este subconjunto para maximizar la distancia mínima entre todos los puntos en el nuevo conjunto . $C$ $n$ $s$ $s$

max_{\begin{matrix} s \subset C \\ | s | = n \end{matrix}} (min_{\begin{matrix} i, j \in s \\ i \neq j \end{matrix}} D (P_{i}, P_{j}))

$\max_{\substack{s \subset C \\ |s| = n}} \left( \min_{\substack{i,j \in s \\ i \neq j} } D \left( P_i, P_j \right) \right)$

En este momento estoy usando la escalada para resolver este problema. Entiendo que el recocido simulado puede dar una mejor solución.

¿Existe una solución conocida para este tipo de problema? ¿O puede este problema reformularse en otro problema que se resuelva fácilmente?

optimization usuario1389800
fuente

Estoy interesado en un problema similar. Según mis resultados de búsqueda hasta ahora, es comparable al problema de dispersión p en el problema de ubicación de la instalación para el cual este es un buen artículo de revisión.

XTZ

¿Sabes cómo se llama este problema?

Diente de león el

Respuestas:

La versión del problema de decisión de este problema de optimización es:

Dado un umbral , desea saber si es posible encontrar un subconjunto de puntos de manera que cada par de puntos en el subconjunto estén separados por al menos unidades. $t$ $n$ $t$

Por supuesto, si puede resolver el problema de decisión, podemos resolver su problema de optimización (mediante búsqueda binaria en el umbral ). $t$

Ahora, este problema de decisión es el problema de encontrar un conjunto independiente en un gráfico euclidiano, donde los puntos tienen un borde entre ellos si están a distancia separados. Un enfoque sería mirar los algoritmos de aproximación estándar para un conjunto independiente. $x,y$ $\le t$

Aún mejor, puede ver algoritmos para conjuntos independientes en gráficos de intersección geométrica . Considere un conjunto de discos, donde cada disco tiene un diámetro y se centra en uno de los puntos en su conjunto . Ahora podemos formar un gráfico de intersección geométrica, donde hay un vértice para cada disco y un borde entre dos vértices si sus discos correspondientes se cruzan. Se ha estudiado el problema de encontrar un conjunto independiente en este tipo de gráfico y existen algoritmos de aproximación para este problema que podría intentar usar. $t$ $C$

Si desea el óptimo exacto en lugar de una aproximación, puede usar cualquiera de los "grandes martillos" estándar, como un solucionador SAT o un solucionador ILP. Hay una manera directa de formular el problema de conjunto independiente como una instancia de SAT, y luego puede aplicar un solucionador de SAT para determinar si existe un subconjunto de puntos que están todos unidades separados entre sí. $n$ $\ge t$

DW
fuente