Existe algum algoritmo para solucionar o seguinte problema:
- Dado um conjunto de pontos no R² e tomando um ponto k, determinar os n vizinhos mais próximos de k.
Stack Overflow em Português é um site de perguntas e respostas para programadores profissionais e entusiastas. Leva apenas um minuto para se inscrever.
Inscreva-se para participar desta comunidadeExiste algum algoritmo para solucionar o seguinte problema:
Sim, existem alguns.
A possibilidade mais simples e direta é você calcular as distâncias de k a cada um dos pontos no conjunto, ordenar esses valores em ordem crescente, e então escolher os pontos com as n menores distâncias. A complexidade desse algoritmo é linear (O(n)) apenas nos cálculos de distância, e na prática vai depender do método de ordenação utilizado (se você utilizar Quicksort, por exemplo, vai ser O(n*log(n)) no caso médio). Ou seja, essa abordagem tem um desempenho bem razoável.
Ainda assim, a escolha do método de cálculo de distância também vai influenciar. A distância Euclidiana, que nada mais é do o cálculo da equação de Pitágoras no triângulo formado com um ponto qualquer, o ponto k e a origem, produz a distância real e direta entre os dois pontos. Mas ela requer o cálculo de uma raiz quadrada, cujo processamento é bastante custoso. Uma alternativa que pode ser útil dependendo do domínio de aplicação é utilizar a distância de Manhattan (também chamada de Geometria ou Métrica do Táxi). Essa distância tem esse nome porque simula o trajeto que um táxi faria ao se deslocar entre os dois pontos nos quarteirões da cidade de Manhattan. Para ter essa distância, basta somar as diferenças absolutas entre os valores dos eixos x e y nos dois pontos. O resultado é maior do que a distância real, mas em muitos casos pode servir como uma boa aproximação a um custo computacional consideravelmente menor.
Por exemplo, o código de ilustração que eu preparei em Python produz o seguinte resultado para a busca dos 4 pontos mais próximos de um k aleatório, dentre um conjunto de 10 pontos (também aleatórios):
(em azul estão os pontos do conjunto de base, em vermelho o ponto k e em verde os 4 pontos do conjunto de base que estão mais próximos de k)
Como pode-se perceber, o resultado nesse caso foi o mesmo. Mas vale lembrar que a distância de Manhattan pode errar, uma vez que ela não produz a distância real, mas sim uma estimativa. Por exemplo, observe o ponto circundado em vermelho no resultado deste outro teste:
Ele é um dos erros entre outros. Ainda assim, essa opção é bem útil em diversas situações (em jogos, por exemplo, quando se precisa decidir com quais outros objetos a nave do jogador colidiu e o desempenho a cada quadro é mais importante do que a precisão). A saída de texto do programa de exemplo também imprime o tempo que levou cada execução. Por mais que tenha erros, a execução com a distância de Manhattan foi praticamente imediata enquanto que a execução com a distância Euclidiana levou 0.015 segundos a mais nesse exemplo:
Tempo de execução do teste1: 0.0156 segundos
Tempo de execução do teste2: 0.0000 segundos
Essa diferença é maior conforme cresce o número de pontos.
Se os pontos do conjunto não mudam com frequência (imagine uma situação do mundo real como, por exemplo, um cenário em que os pontos representam as latitudes/longitudes das lojas de uma rede de supermercados e o ponto k é o cliente tentando encontrar as lojas mais próximas de sua casa), uma solução melhor seria você pré-processar os dados para construir alguma estrutura auxiliar que tornasse essa decisão mais rápida.
Uma estrutura famosa (e que lhe foi sugerida indiretamente pelo colega Haroldo) é a QuadTree. Uma QuadTree é uma árvore em que cada nó desde a raiz tem exatamente quatro nós filhos. No caso do seu problema, você pode considerar todo o plano onde estão os pontos como o primeiro nível dessa árvore, de forma que todos os pontos estão associados à raiz dela. Em seguida você divide esse plano em 4 regiões (iguais se considerar os mesmos limites para ambos os eixos) e associa a esses nós apenas os pontos que se encontram neles. Então, para cada uma dessas 4 regiões, você redivide novamente em mais quatro e associa aos seus nós filhos os pontos a que pertencem. E continua esse processo recursivamente até você chegar a um nível de profundidade em que cada ponto esteja associado exclusivamente a um nó.
Uma vez com essa estrutura montada, ela é útil porque você pode reduzir os pontos para comparação utilizando a região em que k se encontra. Basicamente você procura na árvore (complexidade O(log(n)), melhor do que a solução anterior que é O(n*log(n))) descendo nas sub-regiões que contém k, e somente faz o cálculo padrão de distância quando o número de itens na região for insuficiente (for menor do que n).
Claro que se você tiver que construir essa árvore a cada execução o desempenho vai ser muito pior. Mas, como eu disse, se os pontos não mudam, uma vez com a árvore construída uma nova busca (de n pontos mais próximos de um novo k) é muitíssimo mais rápida.
O código de ilustração que eu produzi conta com uma implementação bem simples de uma QuadTree (há bibliotecas com implementações melhores). Veja um exemplo de resultados para um número bem maior de pontos:
E a saída com os tempos:
Tempo de execução do teste1: 0.1563 segundos
Tempo de execução do teste2: 0.0938 segundos
Tempo de execução do teste3: 0.0469 segundos (com criação da QuadTree: 0.2656 segundos)
Observa-se que:
Certamente há outras estruturas que podem ser igualmente úteis, se os pontos forem fixos. Por exemplo, você também pode construir um Diagrama de Voronoy a partir dos pontos. Então, a célula onde k estiver certamente contém o ponto mais próximo (algo obtido imediatamente! isto é, com complexidade O(1)). Então, basta ir obtendo as células adjacentes até montar n células. Os pontos "semente" dessas células são os pontos mais próximos de k. Se as células vizinhas a uma dada célula forem armazenadas em uma estrutura de árvore (na verdade um grafo, ligando as células umas às outras conforme sua vizinhança), você também obtém uma complexidade de O(log(n)), tão boa quanto o uso da QuadTree.
Eis o código que eu produzi (em Python, porque é mais fácil). Espero que seja útil. :)
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from numpy.random import rand
import numpy as np
import matplotlib.pyplot as plt
import time
from enum import Enum
###########################################
# Enumeração que representa os tipos de cálculo
# de distância disponíveis para ser utilizados
# na função simples.
###########################################
class Distancia(Enum):
Euclidiana = 1
Manhattan = 2
###########################################
# Função de proximidade "simples".
# Calcula as distâncias entre todos os pontos
# e o ponto k, ordena e escolhe os n mais
# próximos.
# Parâmetros:
# bX Lista/array com as coordenadas em x dos pontos de base.
# bY Lista/array com as coordenadas em y dos pontos de base.
# kX Coordenada em x do ponto k.
# kY Coordenada em y do ponto k.
# n Número desejado de pontos mais próximos do ponto k.
# tpDist Tipo de cálculo de distância.
# Retorno:
# pX Lista/array com as coordenadas em x dos n pontos
# mais próximos do ponto k.
# pY Lista/array com as coordenadas em y dos n pontos
# mais próximos do ponto k.
###########################################
def nProxSimples(bX, bY, kX, kY, n, tpDist):
# Calcula as distâncias e armazena em um dicionário
# (acessível pela distância)
distancias = {}
for i in range(len(bX)):
if tpDist == Distancia.Manhattan:
distancia, = np.abs(bX[i] - kX) + np.abs(bY[i] - kY)
else:
distancia, = np.sqrt(np.power(bX[i] - kX, 2) + np.power(bY[i] - kY, 2))
distancias[distancia] = [bX[i], bY[i]]
# Organiza as distâncias em ordem crescente
ordenadas = sorted(distancias)
# Então, devolve os pontos nas n primeiras entradas
# da lista ordenada (pegando as coordenadas do dicionário)
pX = []
pY = []
n = np.min([n, len(bX)])
for i in range(n):
coords = distancias[ordenadas[i]]
pX.append(coords[0])
pY.append(coords[1])
return pX, pY
###########################################
# Classe que representa uma região retangular
# do plano de dados. Utilizada na construção
# das QuadTrees.
###########################################
class Regiao:
# Construtor da classe
def __init__(self, x, y, largura, altura):
self.x = x
self.y = y
self.largura = largura
self.altura = altura
# Verifica se o ponto dado está contido ou não
# nesta região
def contem(self, kX, kY):
if kX >= self.x and kX <= self.x + self.largura and kY >= self.y and kY <= self.y + self.altura:
return True
else:
return False
# Retorna uma string com a representação do conteúdo
# da região
def texto(self):
return 'x: {:.2f} y: {:.2f} largura: {:.2f} altura: {:.2f}'. format(self.x, self.y, self.largura, self.altura)
###########################################
# Função recursiva de criação de uma
# QuadTree com os pontos de base dados.
# Parâmetros:
# bX Lista/array com as coordenadas em x dos pontos de base.
# bY Lista/array com as coordenadas em y dos pontos de base.
# reg Instância de objeto Regiao com a região em que os pontos
# se encontram nesse nível.
# nivel Número com o nível do nó raiz para a QuadTree.
# titulo String com o título do gráfico
# Retorno:
# qtree Estrutura da QuadTree criada para os dados. Essa estrutura
# usa um dicionário, em que o campo 'filhos' contém as
# nós dos níveis inferiores, o campo 'regiao' contém
# os limites da região em que os pontos se encontram, e
# o campo 'pontos' contém as coordenadas x e y dos pontos naquela
# região.
###########################################
def montaQuadtree(bX, bY, reg = None, nivel = None):
# A região padrão é toda a área de dados
if reg is None:
reg = Regiao(0, 0, 1, 1)
# O nível padrão é 0 (raiz)
if nivel is None:
nivel = 0
# Se só há um ponto, retorna imediatamente um nó sem filhos
if len(bX) <= 1:
no = {'nivel': nivel, 'regiao': reg, 'pontos': (bX, bY), 'filhos': []}
return no
# Calcula os meios da região atual (de forma a
# subdividí-la em 4 novas regiões)
meioX = reg.largura / 2 + reg.x
meioY = reg.altura / 2 + reg.y
# Separa os pontos entre localizados em cada sub-região
# (numeradas em sentido horário a partir da sub-região
# superior esquerda):
# +---+---+
# | 1 | 2 |
# +---+---+
# | 4 | 3 |
# +---+---+
bX1 = []
bX2 = []
bX3 = []
bX4 = []
bY1 = []
bY2 = []
bY3 = []
bY4 = []
for i in range(len(bX)):
x = bX[i]
y = bY[i]
if x <= meioX and y <= meioY:
bX1.append(x)
bY1.append(y)
elif x > meioX and y <= meioY:
bX2.append(x)
bY2.append(y)
elif x > meioX and y > meioY:
bX3.append(x)
bY3.append(y)
else:
bX4.append(x)
bY4.append(y)
# Chama recursivamente a função para montar as árvores seguintes,
# automaticamente subdividindo os pontos em regiões
qt1 = montaQuadtree(bX1, bY1, Regiao(reg.x, reg.y, reg.largura / 2, reg.altura / 2), nivel + 1)
qt2 = montaQuadtree(bX2, bY2, Regiao(meioX, reg.y, reg.largura / 2, reg.altura / 2), nivel + 1)
qt3 = montaQuadtree(bX3, bY3, Regiao(meioX, meioY, reg.largura / 2, reg.altura / 2), nivel + 1)
qt4 = montaQuadtree(bX4, bY4, Regiao(reg.x, meioY, reg.largura / 2, reg.altura / 2), nivel + 1)
# Cria um nó do nível atual com as raízes das árvores calculadas
# nos nós filhos
qtree = {'nivel': nivel, 'regiao': reg, 'pontos': (bX, bY), 'filhos': [qt1, qt2, qt3, qt4]}
return qtree
###########################################
# Função de proximidade baseada em uma QuadTree.
# Parâmetros:
# qtree QuadTree com os pontos organizados em regiões.
# kX Coordenada em x do ponto k.
# kY Coordenada em y do ponto k.
# Retorno:
# pX Lista/array com as coordenadas em x dos n pontos
# mais próximos do ponto k.
# pY Lista/array com as coordenadas em y dos n pontos
# mais próximos do ponto k.
###########################################
def nProxQuadtree(qtree, kX, kY, n):
pontos = qtree['pontos']
if len(pontos) > 0:
pX = pontos[0]
pY = pontos[1]
else:
pX = []
pY = []
# Se chegou em um nível cuja quantidade de
# pontos é menor ou igual a n, então devolve
# esses pontos pois eles certamente estão entre
# os mais próximos de k
if len(pX) <= n:
return pX, pY
# Caso contrário, avalia as sub-regiões filhas.
# Na região filha onde se encontra k, obtém os pontos
# mais próximos recursivamente.
pX = []
pY = []
filhos = qtree['filhos']
for filho in qtree['filhos']:
if filho['regiao'].contem(kX, kY):
pX, pY = nProxQuadtree(filho, kX, kY, n)
# Se os pontos obtidos da região filha já são suficientes,
# retorna-os
if len(pX) == n:
return pX, pY
# Senão, não tem jeito: é necessário calcular as distâncias
# manualmente para cada sub-região
pX = []
pY = []
for filho in qtree['filhos']:
pontos = filho['pontos']
if len(pontos) > 0:
pX = pX + pontos[0]
pY = pY + pontos[1]
return nProxSimples(pX, pY, kX, kY, n, Distancia.Euclidiana)
###########################################
# Função auxiliar de impressão do conteúdo
# de uma QuadTree e dos pontos alocados nos
# níveis.
# Parâmetros:
# bX Lista/array com as coordenadas em x dos pontos de base.
# bY Lista/array com as coordenadas em y dos pontos de base.
# reg Instância de objeto Regiao com a região em que os pontos
# se encontram nesse nível.
# nivel Número com o nível do nó raiz para a QuadTree.
# titulo String com o título do gráfico
# Retorno:
# qtree Estrutura da QuadTree criada para os dados. Essa estrutura
# usa um dicionário, em que o campo 'filhos' contém as
# nós dos níveis inferiores.
###########################################
def imprimeQuadtree(qtree):
s = ' ' * qtree['nivel']
print('{:s}Nivel: {:d}'.format(s, qtree['nivel']))
print('{:s}Região: {:s}'.format(s, qtree['regiao'].texto()))
if(len(qtree['pontos']) > 0):
bX = qtree['pontos'][0]
bY = qtree['pontos'][1]
print('{:s}Pontos: {:s}'.format(s, ', '.join(['({:.2f},{:.2f})'.format(x, y) for x, y in zip(bX, bY)])))
if len(qtree['filhos']) > 0:
print('{:s}Filho(s):'.format(s))
for filho in qtree['filhos']:
imprimeQuadtree(filho)
###########################################
# Função de criação de um gráfico com os
# dados processados.
# Parâmetros:
# figNum Número da figura a ser criada com o gráfico.
# bX Lista/array com as coordenadas em x dos pontos de base.
# bY Lista/array com as coordenadas em y dos pontos de base.
# kX Coordenada em x do ponto k.
# kY Coordenada em y do ponto k.
# pX Lista/array com as coordenadas em x dos n pontos mais
# próximos de k.
# pY Lista/array com as coordenadas em y dos n pontos mais
# mais próximos do ponto k.
# titulo String com o título do gráfico
###########################################
def criaGrafico(figNum, bX, bY, kX, kY, pX, pY, titulo):
# Cria uma nova figura
plt.figure(figNum)
plt.title(titulo)
plt.xlim(0.0, 1.0)
plt.ylim(0.0, 1.0)
# Plota os pontos de base
plt.scatter(bX, bY, color='blue', marker='.')
# Plota o o ponto k
plt.scatter(kX, kY, color='red', marker='o')
# Plota os pontos mais próximos
plt.scatter(pX, pY, color='green', marker='.')
###########################################
# Função principal
###########################################
def main():
# Número total de pontos (base)
tam = 10000
# Número desejado de pontos mais próximos
n = 1000
# Gera os pontos de base, aleatoriamente
bX, bY = rand(2, tam)
# Gera o ponto k, também aleatoriamente
kX, kY = rand(2, 1)
# Teste 1: função mais simples e distância euclidiana
inicio = time.time()
rX, rY = nProxSimples(bX, bY, kX, kY, n, Distancia.Euclidiana)
fim = time.time()
duracao = fim - inicio
titulo = 'Teste 1: função simples e distância euclidiana\n(tam: {:d}, n: {:d})'.format(tam, n)
criaGrafico(1, bX, bY, kX, kY, rX, rY, titulo)
print('Tempo de execução do teste1: {:.4f} segundos'.format(duracao))
# Teste 2: função mais simples e distância de Manhattan
inicio = time.time()
rX, rY = nProxSimples(bX, bY, kX, kY, n, Distancia.Manhattan)
fim = time.time()
duracao = fim - inicio
titulo = 'Teste 2: função simples e distância de Manhattan\n(tam: {:d}, n: {:d})'.format(tam, n)
criaGrafico(2, bX, bY, kX, kY, rX, rY, titulo)
print('Tempo de execução do teste2: {:.4f} segundos'.format(duracao))
# Teste 3: função com QuadTree
inicio = time.time()
qtree = montaQuadtree(bX, bY)
fim = time.time()
duracao1 = fim - inicio
inicio = time.time()
rX, rY = nProxQuadtree(qtree, kX, kY, n)
fim = time.time()
duracao = fim - inicio
titulo = 'Teste 3: função com QuadTree\n(tam: {:d}, n: {:d})'.format(tam, n)
criaGrafico(3, bX, bY, kX, kY, rX, rY, titulo)
print('Tempo de execução do teste3: {:.4f} segundos (com criação da QuadTree: {:.4f} segundos)'.format(duracao, duracao + duracao1))
# Função de teste. Tire o comentário se desejar.
#imprimeQuadtree(qtree)
# Mostra os gráficos criados
plt.show()
# verificação do namespace para invocar 'main'
if __name__ == '__main__':
main()