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

12

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(PEu,Pj)

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 .n s sCnss

maxsC|s|=n(minEu,jsEujD(PEu,Pj))

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?

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:

7

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.tnt

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,yt

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.CtC

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.tnt

DW
fonte