Escolhendo um subconjunto para maximizar a distância mínima entre pontos

Eu tenho um conjunto de pontos $C$ e tenho a distância entre cada ponto . Essas distâncias são euclidianas, mas os pontos estão realmente em um espaço de feição. $D(P_i,P_j)$

Dos pontos eu quero escolher um subconjunto de pontos. Chame esse subconjunto de . Quero escolher este subconjunto de modo a maximizar a distância mínima entre todos os pontos no novo conjunto . $C$ $n$ $s$ $s$

max_{\begin{matrix} s \subset C \\ | s | = n \end{matrix}} (min_{\begin{matrix} Eu, j \in s \\ Eu \neq j \end{matrix}} D (P_{Eu}, 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)$

No momento, estou usando alpinismo para resolver esse problema. Entendo que o recozimento simulado pode dar uma solução melhor.

Existe uma solução conhecida para esse tipo de problema? Ou esse problema pode ser reformulado para outro problema que é facilmente resolvido?

optimization user1389800
fonte

Estou interessado em um problema semelhante. Com base nos meus resultados de pesquisa até agora, é comparável ao problema de dispersão-p no local da instalação, para o qual este é um bom artigo de revisão.

XTZ

Você sabe qual é o nome desse problema?

Dandelion

Respostas:

A versão do problema de decisão desse problema de otimização é:

Dado um limite , você deseja saber se é possível encontrar um subconjunto de pontos, de modo que cada par de pontos no subconjunto esteja pelo menos unidades distantes. $t$ $n$ $t$

Obviamente, se você puder resolver o problema de decisão, podemos resolver seu problema de otimização (por pesquisa binária no limite ). $t$

Agora, esse problema de decisão é o problema de encontrar um conjunto independente em um gráfico euclidiano, onde os pontos têm uma aresta entre eles se estiverem à distância distante. Uma abordagem seria examinar algoritmos de aproximação padrão para conjuntos independentes. $x,y$ $\le t$

Melhor ainda, você pode procurar algoritmos para conjuntos independentes em gráficos de interseção geométrica . Considere um conjunto de discos, onde cada disco tem diâmetro e é centrado em um dos pontos no seu conjunto . Agora podemos formar um gráfico de interseção geométrica, onde existe um vértice para cada disco e uma aresta entre dois vértices se os discos correspondentes se cruzarem. O problema de encontrar um conjunto independente nesse tipo de gráfico foi estudado e existem algoritmos de aproximação para esse problema que você pode tentar usar. $t$ $C$

Se você deseja exatamente o ideal, em vez de uma aproximação, pode usar qualquer um dos "grandes martelos" padrão, como um solucionador SAT ou um solucionador ILP. Existe uma maneira simples de formular o problema de conjunto independente como uma instância SAT e, em seguida, você pode aplicar um solucionador SAT a ele para descobrir se existe um subconjunto de pontos que estão todos unidades de uma a outra. $n$ $\ge t$

DW
fonte