• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

DavidLuiz

Calcular distancia minima entre varios pontos (abordagem divide and conquer)

Calcular distancia minima entre varios pontos (abordagem divide and conquer)   4 membros votaram

  1. 1. Calcular distancia minima entre varios pontos (abordagem divide and conquer)

    • distancia entre pontos
      2
    • distancia minima
      2

Please inicie sessão ou registe-se para votar.

13 mensagens neste tópico

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

esquerdo e direito

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?!

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O problema não é claro no ponto 3.

Que distancias são essas... distancia de um ponto até onde?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

pedro

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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 :D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora