Problema da menor distância entre pontos

Problema da menor distância entre pontos

¹Departmento de Ciência da Computação – Universidade Federal de Ouro Preto (UFOP) – Campus Morros do Cruzeiro – Ouro Preto, MG – Brasil

Resumo. Este artigo trata do problema da menor distância entre pontos, analisando a implementação dos métodos de Força Bruta e Divisão e Conquista para solução deste. Além da descrição dos códigos feitos traz a analise de complexidade e resultados obtidos em testes realizados.
1. Introdução
O Problema da menor distancia entre pontos pertencente aos primeiros problemas geométricos que foram tratados na origem do estudo de complexidade computacional. O problema consiste em encontrar, em um conjunto n de pontos, os dois mais próximos entre si. Encontrar o valor mínimo ou máximo de uma função é um problema bastante utilizado em diversas áreas como por exemplo calcular o restaurante mais próximo de uma determinada localidade. Em geral, este valor é chamado de "ótimo", pois corresponde ao melhor dentre todos os possíveis num espaço de soluções viáveis. Para se calcular a menor distância em um conjunto de n pontos, todos os pontos devem ser comparados uns com os outros, tornando a complexidade do algoritmo de ordem quadrática, o que torna a solução do problema inviável para n muito grande. A solução ate hoje mais eficiente para resolução deste problema, usa a ideia de divisão e conquista que torna a complexidade do algoritmo na ordem de nlogn.

2. Materiais e Métodos
Para realizar a analise do problema, foram implementados dois métodos. O primeiro deles foi a Força Bruta, que realiza todas as comparações possíveis pata encontrar a menor distancia existente, o que torna a solução inviável para valores muito alto. O segundo método implementado foi o de Divisão e Conquista, que como o próprio nome diz, ele divide o problema em subproblemas, resolve-os separadamente e depois combina-os. Isso evita algumas comparações desnecessárias e torna o algoritmo mais eficiente para