Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como resolver o problema do par de pontos mais próximo? É possível adotar uma abordagem mais eficiente que a força bruta?

1 Resposta

0 votos
respondida Jun 19 por Peng Yaohao (101 pontos)  
editado Jun 19 por Peng Yaohao

O problema do par mais próximo (closest pair problem) está associado à resolução de uma tarefa bastante simples: a partir de um número \(n\) de pontos \(\in\mathbb{R}^m\), encontrar os pontos com menor distância euclidiana entre eles. Ou seja, deseja-se obter os pontos \(p_1=(x_{11}+x_{21}+...+x_{m1})\) e \(p_2=(x_{12}+x_{22}+...+x_{m2})\), dada pela expressão \(dist_{p_1,p_2}=\sqrt{(x_{11}-x_{12})^2+(x_{21}-x_{22})^2+...+(x_{m1}-x_{m2})^2}\)

Porém, ao tentar resolvê-lo, percebemos que a solução não é tão imediata. Por mais que a expressão a ser calculada é evidente e sem complicações, o número de contas a ser feito cresce bem rapidamente conforme o número \(n\) de pontos a serem testados aumenta. A maneira mais natural de pensar esse problema seria simplesmente comparar todos os pares de pontos possíveis, calculando a distância entre cada um desses pares, e por fim pegar o(s) par(es) com menor distância. No entanto, o problema dessa abordagem está no número de pares testados: \({n\choose 2} =\frac{n!}{(n-2)!\cdot 2!}=\frac{n(n-1)}{2}\).

Testar todos os pares garante que a resposta será encontrada, mas como poderíamos fazer isso de maneira mais eficiente? Um modo possível é particionar o espaço em subconjuntos menores, e aplicar a abordagem "força bruta" dentro de cada um deles, de modo a evitar comparações "irrelevantes" entre pontos distantes. Observe a figura abaixo, que ilustra 15 pontos em \(\mathbb{R}^2\):

A imagem será apresentada aqui.

É fácil notar que o par de pontos mais próximos não deve ser composto por um ponto vermelho e um azul, então não é necessário testá-los entre si, o que diminui significantemente o número de comparações a serem feitas. Essa é a estratégia de "dividir para conquistar": segmentar o problema original em versões menores e de resolução menos custosa. Basicamente, testam-se todos os pares possíveis dentro de cada um dos subconjuntos particionados e destes extrai-se o par mais próximo.

O único cenário que deve ser incorporado para garantir que a resposta seja encontrada é considerar que o par mais próximo pode ser composto por pontos de subconjuntos distintos -- na figura, por exemplo, o caso em que o par próximo é um ponto vermelho e outro preto. Para isso, a cada divisão realizada (ilustrado pelas linhas verticais), verifica-se a existência de pontos cuja primeira coordenada (a que está sendo usada para o particionamento) possui distância \(d\) da linha de divisão, onde \(d\) é a menor distância encontrada até então - ou seja, se para os pontos testados dentro do subconjunto a distância mínima foi de \(5\) unidades, a menor distância de pontos que "cruzam" a fronteira da divisão não pode ser maior que \(5\), pois o par mais próximo certamente não estará nesse cenário, o que dispensa a comparação desses casos. Assim, para cada divisão (as linhas verticais em preto), estabelece-se uma faixa com a distância mínima provisória e testa-se os pontos dentro dessa faixa; caso haja algum par com distância menor que a provisória, guardar esse ponto e a distância entre eles. O processo se repete até testar todos os subconjuntos e todos os "cruzamentos".

Segue implementação em Python:

import numpy as np

### Função que calcula a distância euclidiana entre dois pontos em R^2
def dist(a,b):
    return np.sqrt((a[0]-b[0])**2+(a[1]-b[1])**2)

### Versão força bruta
def bruto(x):
    n=len(x)
    ponto1=[] # lista que recebe os pontos do par mais próximo
    ponto2=[]
    distmin=10000000000000 # inicializar com distância muito grande
    for i in range(0,n-1): # comparar todos os pares possíveis
        for j in range(i+1,n):
            if dist(x[i],x[j])<distmin: # se a distância do par testado for menor que o provisório, armazenar o par e a distância
                ponto1=list(x[i])
                ponto2=list(x[j])
                distmin=dist(x[i],x[j])
            elif dist(x[i],x[j])==distmin: # em caso de empate, adicionar pontos às listas; distância permanece a mesma
                ponto1.append(list(x[i]))
                ponto2.append(list(x[j]))
    return(ponto1,ponto2,distmin) # retorna os pontos e a distância entre eles

### Versão dividir e conquistar
def pardiv(x,partes):
    n=len(x)
    beg=min(x)[0] # menor valor da primeira coordenada
    end=max(x)[0] # maior valor da primeira coordenada
    ampl=float(end-beg) # diferença entre menor e maior valores
    ponto1=[] # lista que recebe os pontos do par mais próximo
    ponto2=[]
    distmin=10000000000000 # inicializar com distância muito grande
    for i in range(1,partes+1): # particionamento; 'partes' = número de subconjuntos
        end=min(x)[0]+(i*ampl/partes) # dividir a amplitude em subconjuntos igualmente espaçados
        part=[]
        for j in range(0,n): # define cada subconjunto 'part'
            if beg<=x[j][0]<=end:
                part.append(x[j])
        if bruto(part)[2]<distmin: # dentro de cada 'part', proceder por força bruta
            ponto1=bruto(part)[0]
            ponto2=bruto(part)[1]
            distmin=bruto(part)[2]
        cross=[]
        for k in range(0,n): # 'cruzamentos': a partir da divisão anterior, fazer força bruta para todos os pontos com distância menor que 'distmin' na primeira coordenada
            if end-distmin<=x[k][0]<=end+distmin:
                cross.append(x[k])
        if bruto(cross)[2]<distmin:
            ponto1=bruto(cross)[0]
            ponto2=bruto(cross)[1]
            distmin=bruto(cross)[2]
        beg=end # ir para o próximo subconjunto, repetir até chegar ao fim dos dados
    return(ponto1,ponto2,distmin)

Para efeito de comparação, o teste abaixo foi realizado com \(10000\) pontos em \(\mathbb{R}^2\) com cada uma das coordenadas variando entre \(-100\) e \(100\). A versão "força bruta" levou \(494.37\) segundos para fornecer a resposta correta, enquanto que a versão "dividir e conquistar" levou apenas \(25.64\) segundos, um tempo significantemente menor.

import random
import timeit

test=[None]*10000 # 10000 pontos aleatórios em R^2
for i in range(0,len(test)):
    test[i]=(random.uniform(-100,100),random.uniform(-100,100))

start=timeit.default_timer()
bruto(test)
stop=timeit.default_timer()
print stop-start # tempo de processamento força bruta

start=timeit.default_timer()
pardiv(test,30) # resolve dividindo os dados em 30 pedaços
stop=timeit.default_timer()
print stop-start # tempo de processamento dividir e conquistar

O caso de pontos em \(\mathbb{R}^2\) foi utilizado para ilustrar o problema dada a praticidade de sua interpretação geométrica, mas pode ser estendido para o caso em que há \(n\) pontos em \(\mathbb{R}^m\), com \(n,m\in\mathbb{N}\) quaisquer, bastando ajustar o cálculo da distância euclidiana e o número de pontos a serem armazenados.

comentou Jul 5 por Caue (226 pontos)  
Está ótima a solução. Como sugestão, seria legal apresentar ao final uma imagem mostrando os pontos e a menor distância.
Uma dica: quando precisar de um número grande para comparação, pode usar o math.inf.
comentou Jul 7 por JoaoMaria (71 pontos)  
a solução do exercício está excelente. Muito bem explicada! No código, chamou-me a atenção a preocupação com detalhe.  A possibilidade de haver mais de um par de pontos com a distância mínima. Parabéns pela visão ampla do problema. Esse detalhe não transparece no enunciado.
Sugiro que faça referência nas explicações a esse fato que está expressado no código
...