Calcular distancia minima entre varios pontos (abordagem divide and conquer) - C - Portugal-a-Programar
Calcular distancia minima entre varios pontos (abordagem divide and conquer)
By DavidLuiz, February 28, 2009 in C
1. Calcular distancia minima entre varios pontos (abordagem divide and conquer)
Dada uma sequência de pontos num plano, representados pelas coordenadas x e y, encontrar os dois pontos mais próximos entre si.
1. Ordenar os pontos ao longo da coordenada x.
2. Dividir o conjunto de pontos em dois subconjuntos de igual cardinalidade por uma linha
vertical x = xmed
3. Resolver o problema recursivamente segundo o conjunto esquerdo e direito de pontos. Isto
irá resultar em distâncias mínimas dEmin e dDmin, respectivamente para o subconjunto
4. Encontrar ainda a distância mínima dEDmin entre os pares de pontos em que um ponto está
no conjunto esquerdo e o outro no conjunto direito.
5. O resultado final será o valor mínimo entre dEmin, dDmin e dEDmin.
Basicamente é este o problema, não consigo perceber como fazer isto. Fiz uma parte de código em que calculo a dEmin e a dDmin (ate ao ponto 3) mas não consigo perceber como fazer a dDEm (ponto 4)
Alguém me pode dar uma dica?!
O problema não é claro no ponto 3.
Que distancias são essas... distancia de um ponto até onde?
Bem pelo que entendo, é que tem-se de comparar a distancia entre cada par de pontos pertencentes ao mesmo subconjunto...e verificar qual é a distancia mínima desse subconjunto (esquerdo ou direito).
Não pode ser isso. Se for isso o problema fica logo resolvido no ponto 2, é só pegares na distancia mais pequena e pronto, é a tua resposta.
Não digas isto ao teu professor desta forma que eles normalmente levam isso a peito, pergunta-lhe con jeitinho mas esse enunciado não é conciso.
És obrigado a usar o algoritmo com abordagem divide and conquer para este problema?
Quando resolvi este problema achei esta abordagem complicada de implementar, aprendi outro com a mesma complexidade O(N log N) - ver as distancias entre todos os pontos é O(N^2) - mas mais simples. Vou ver se encontro os pdfs onde aprendi isso.
Se tiver mesmo que ser essa abordagem, vê isto ou isto.
Sobre as distâncias, a ideia é dividir o conjunto de pontos em 2, calcular a distância minima "dEmin" entre os pontos do lado esquerdo ( X < Xmed ), a distância minima "dDmed" entre os pontos do lado direito e ver qual é a menor. Contudo existe o problema quando a solução é ligar um ponto da parte esquerda com a parte direita. Esta parte é a parte complicada que eu não tentei fazer.
PS: este post tava melhor enquadrado na Algoritmia e Lógica.
edit: um dos links por onde aprendi foi este ("Closest pair"). Mas tem uma explicação muito breve.
edit2: esqueci-me de dizer que Xmed é a mediana das coordenadas X dos pontos, por isso, convém ordená-los como diz o passo 1.
Fica resolvido no ponto 2? Como?
Realmente também não percebo muito bem esse enunciado...
Em abordagem "brute force" terias que calcular a distância entre todos os pontos, ou seja, (n*(n+1))/2 distâncias.
Com esta abordagem tens que calcular a distância entre todos os pontos da metade esquerda ((n/2)*(n/2 + 1)) /2 distâncias e entre todos os pontos da metade direita. Ao todo, (n/2) * (n/2 + 1) distâncias. Feito isto, tens uma dEmin e dDmin, se dCmin=min(dEmin,dDmin), basta-te pegar nos pontos à esquerda tais que xmed-x<dCmin e para cada um desses pontos P, considerar os pontos tais que x-x.P<dCmin, e calcular essas distâncias. Enfim... Parece que estou só a inventar coisas que não vêm nesse enunciado... lol
E a solução não parece ser significativamente melhor que brute force...
Queria dizer no ponto 3 e não no 2.
Não ficava logo resolvido de facto porque podiam existir pares de pontos con distancias ainda menore pertencendo um a cada subconjunto.
Mas tipo, se se divide o conjunto em dois e depois se calculam as combinações todas possíveis de distancias de cada metade, não é precisa recursividade para nada uma vez que todos os cálculos já foram feitos.
De qualquer das formas, o problema não tem os dados todos necessários para a sua resolução. Nomeadamente aquelas distancias DEmin ou lá o que é, só o autor do enunciado tem condições para seber o que são.
dEDmin é, como está indicado no enunciado, (em linguagem matemática)
DEmin: para todo o ponto E tal que E.x<xmed para todo o ponto D tal que D.x>xmed distância_euclidiana(E,D)<=dEDmin
A questão aqui é: que simplificações é que nos permite o cálculo prévio de dEmin e dDmin, para achar o valor de dEDmin?
Não são calculadas as combinações todas entre os pontos de cada metade. Isso de facto não faria sentido. Nos links que dei têm a explicação da complexidade do algoritmo.
A base é teres um conjunto com 2 pontos. Neste caso a distância mínima é simplesmente a distância entre os 2 pontos.
Quando isto não acontece, tens de dividir o conjunto em 2 como foi dito e o problema está em combinar pontos das 2 metades que podem dar a solução óptima. Assim, o truque para manter o algoritmo muito rápido é considerar apenas alguns dos pontos próximos da linha vertical (x = Xmed) com que dividimos o conjunto de pontos ( se d = min( dEmin , dDmin ), apenas se consideram os pontos com coordenadas ]Xmed-d , Xmed+d[ ).
Deve-se perceber melhor com a explicação com figura do 2º link que dei.
Aqui está explicado de forma razoável o algoritmo que aprendi para este problema.
Ah! Não tinha interpretado bem o "calcular recursivamente" as distâncias. Portanto a divisão inicial entre conjunto esquerdo e direito é só a primeira de uma série de divisões recursivas, é isso?
Exacto. Só pára quando tens 2 ou 3 pontos no conjunto.
Não vejo isso indicado em lado nenhum nem tão pouco percebo a tua explicação.
Acho que é isto que disseste ou quiseste dizer:
distancia mínima entre dois pontos pertencentes um a cada conjunto
é isso n é?
No entanto 'DEmin' não significa coisa nenhuma. É esse o problema do enunciado. Não é dido o que é isso do DEmin.
Eu estou a perceber o que vocês estão a fazer, mas daí a ser isso que o enunciado diz vai muita adivinhação ( profésô chibanga )
Um enunciado destes tem que ser matematicamente rigoroso, caso contrário falha por completo o seu objectivo didático, que é o que se está aqui a passar.
Eu não considero isto propriamente um enunciado, é simplesmente uma tradução do pseudo-código do algoritmo que está na wikipedia ("planar case") e semelhante ao pseudo-código referido nos links que dei (não sei se os viste).
Eu já conhecia o algoritmo (apesar de ter preferido aprender e implementar outro), e não fiz nenhuma adivinhação