EP6
EP6 - Par Mais Próximo
Objetivos
Neste ponto você já sabe mais sobre análise de consumo de tempo do que sabia no início do semestre. Você viu funções como merge_sort()
e quick_sort()
que são exemplos clássicos, especialmente o primeiro, da estratégia de Divisão e Conquista. Neste exercício programa você comprovará o poder dessa estratégia solucionando um problema geométrico.
Problema
No problema do par mais próximo (closest pair problem), queremos encontrar dois pontos de uma coleção dada tais que a distância entre eles seja a menor possível. Uma aplicação prática deste problema, na sua versão cinética, é em controle de tráfego aéreo: os dois aviões que estão em maior perigo de colisão são aqueles que estão mais próximos.
Problema do par mais próximo. Dada uma lista de pontos do plano, encontrar dois pontos (distintos) da lista tais que a distância entre eles seja a menor possível.
Os pontos dados podem estar em um espaço de dimensão arbitrária, mas neste EP discutiremos o caso em que os pontos estão no plano e a distância entre eles é a euclidiana. Assim, se p0=[x0, y0]
e p1=[x1, y1]
são (as coordenadas de) dois pontos do plano, a distância entre eles, denotada por distancia(p0, p1)
, é o número √(
x
1
−
x
0
)
2
+
(
y
1
−
y
0
)
2
.
Cada ponto será representado por uma lista [x,y]
onde x
é a sua abscissa e y
é a sua ordenada.
Solução à la MAC0110
A primeira ideia para a resolução do problema do par mais próximo é simplesmente calcularmos a distância entre cada par de pontos, enquanto mantemos a menor distância encontrada até o momento. No EP6 essa ideia será implementada na função mac0110()
.
Solução à la MAC0122
Como você viu com as funções quadráticas para ordenação de listas buble_sort()
, selecao()
, insercao()
, quando o tamanho da entrada é dobrado, o consumo de tempo é aumentado por um fator de quatro. Por outro lado, também é verdade que se o tamanho da entrada é dividido pela metade o consumo de tempo diminui por um fator de quatro. A divisão da entrada na metade é a chave da eficiência da estratégia de Divisão e Conquista para o problema do par mais próximo.
Neste EP você implementará uma função mac0122()
que é muito semelhante ao merge_sort()
. Essa função, que passamos a descrever, corresponde a uma pequena simplificação do algoritmo desenvolvido por M.I. Shamos and D. Hoey em 1975.
A função mac0122()
recebe uma lista de pontos ordenados da esquerda para a direita. Com isso, temos uma representação dos pontos ordenados em relação às suas coordenadas x
(= abscissas). Isso significa, que a função exige um pré-processamento dos pontos.
Como o merge_sort()
a função mac0122()
é recursiva e além de uma lista de pontos lista_pontos
recebe dois inteiros p0
e p1
. A função deve retornar um float
d
e uma lista [p0,p1]
com um par de pontos que são a solução do problema do para mais próximo para a lista_pontos[p:r]
:
d
é a menor distância entre dois pontos emlista_pontos[p:r]
ep0
ep1
são pontos emlista_pontos[p:r]
que estão a distânciad
.
Na base da recursão, se a lista tem poucos pontos, o problema é resolvido diretamente. Caso contrário, a ideia é, em cada nível da recursão, executar as três fases a seguir.
Dividir
De maneira idêntica a função merge_sort()
, calcule o índice q do ponto central da lista.
Conquistar
determine, recursivamente, a menor distância d_esq
entre um par de pontos [p0_esq,p1_esq]
da esquerda e a menor distância d_dir
entre um par de pontos [p0_dir,p1_dir]
de dois pontos da direita.
Combinar
Retorne o mínimo entre d_esq
, d_dir
e a menor distância d_faixa
entre um ponto da esquerda e um ponto da direita e o correspondente par de pontos.
A fase combinar é o coração da função mac0122()
, da mesma forma que a função intercale()
é o coração do merge_sort()
. Essa fase é essencialmente implementada no EP através da função para_mais_proximo_faixa()
. Uma implementação ingênua dessa função calcularia a distância entre cada ponto de lista_pontos[p:q]
e cada ponto de lista_pontos[q:r]
a fim de determinar a menor dessas distância d_faixa
e o correspondente par de pontos [p0_faixa,p1_faixa]
.
A observação chave aqui é que não é necessário que a função par_mais_proximo_faixa()
calcule a distância entre pontos que estão sabidamente a uma distância maior que d = min(d_esq,d_dir)
. Assim, basta par_mais_proximo_faixa()
calcular a distância entre os pontos em lista_pontos[p,q]
e lista_pontos[q,r]
que estão a uma distância menor que d
da reta vertical x=lista_pontos[q][0]
. Chamaremos essa região de faixa de largura d
em relação a q
Finalmente, em cada nível da recursão, após par_mais_proximo_faixa()
ter feito o seu serviço, mac0122()
tem em mãos d_esq
, d_faixa
e d_dir
, e os respectivos pares. A última tarefa que mac0122()
deve então fazer é retornar a menor dentre essas três e o par de pontos correspondente.
O que você deve fazer
Neste EP6 você implementará quatro funções. São elas
distancia()
;mac0110()
;par_mais_proximo_faixa()
; emac0122()
.
A função main()
está completamente implementada. As especificações dessas funções estão no arquivo esqueleto_ep6.py
.
Exemplos de execução do programa
O que aparece em vermelho foi digitado pelo usuário.
Exemplo 0
no. de pontos >>> 128
semente >>> 0
função ('0' para mac0110, '1' para mac0122) >>> 0
gere_pontos(): gerando 128 pontos ...
gere_pontos(): pontos gerados.
Resultado:
par mais próximo = [[623, 689], [621, 686]]
menor distância = 3.61
tempo de execução = 0.01s
executar animação ('s' para sim, 'n' para não) >>> n
Fui!
Exemplo 1
no. de pontos >>> 256
semente >>> 0
função ('0' para mac0110, '1' para mac0122) >>> 0
gere_pontos(): gerando 256 pontos ...
gere_pontos(): pontos gerados.
Resultado:
par mais próximo = [[623, 689], [621, 686]]
menor distância = 3.61
tempo de execução = 0.04s
executar animação ('s' para sim, 'n' para não) >>> n
Fui!
Exemplo 2
no. de pontos >>> 512
semente >>> 0
função ('0' para mac0110, '1' para mac0122) >>> 0
gere_pontos(): gerando 512 pontos ...
gere_pontos(): pontos gerados.
Resultado:
par mais próximo = [[-404, 420], [-405, 423]]
menor distância = 3.16
tempo de execução = 0.15s
executar animação ('s' para sim, 'n' para não) >>> n
Fui!
Exemplo 3
no. de pontos >>> 1024
semente >>> 0
função ('0' para mac0110, '1' para mac0122) >>> 0
gere_pontos(): gerando 1024 pontos ...
gere_pontos(): pontos gerados.
Resultado:
par mais próximo = [[-960, 459], [-962, 459]]
menor distância = 2.00
tempo de execução = 0.57s
executar animação ('s' para sim, 'n' para não) >>> n
Fui!
Exemplo 4
no. de pontos >>> 128
semente >>> 0
função ('0' para mac0110, '1' para mac0122) >>> 1
gere_pontos(): gerando 128 pontos ...
gere_pontos(): pontos gerados.
execute(): pontos sendo ordenados em relação a coordenada x...
execute(): pontos ordenados.
Resultado:
par mais próximo = [[621, 686], [623, 689]]
menor distância = 3.61
tempo de execução = 0.00s
executar animação ('s' para sim, 'n' para não) >>> n
Fui!
Exemplo 5
no. de pontos >>> 256
semente >>> 0
função ('0' para mac0110, '1' para mac0122) >>> 1
gere_pontos(): gerando 256 pontos ...
gere_pontos(): pontos gerados.
execute(): pontos sendo ordenados em relação a coordenada x...
execute(): pontos ordenados.
Resultado:
par mais próximo = [[621, 686], [623, 689]]
menor distância = 3.61
tempo de execução = 0.00s
executar animação ('s' para sim, 'n' para não) >>> n
Fui!
Exemplo 6
no. de pontos >>> 512
semente >>> 0
função ('0' para mac0110, '1' para mac0122) >>> 1
gere_pontos(): gerando 512 pontos ...
gere_pontos(): pontos gerados.
execute(): pontos sendo ordenados em relação a coordenada x...
execute(): pontos ordenados.
Resultado:
par mais próximo = [[-405, 423], [-404, 420]]
menor distância = 3.16
tempo de execução = 0.01s
executar animação ('s' para sim, 'n' para não) >>> n
Fui!
Exemplo 7
no. de pontos >>> 1024
semente >>> 0
função ('0' para mac0110, '1' para mac0122) >>> 1
gere_pontos(): gerando 1024 pontos ...
gere_pontos(): pontos gerados.
execute(): pontos sendo ordenados em relação a coordenada x...
execute(): pontos ordenados.
Resultado:
par mais próximo = [[-962, 459], [-960, 459]]
menor distância = 2.00
tempo de execução = 0.02s
executar animação ('s' para sim, 'n' para não) >>> n
Fui!
Roteiro
-
Faça o download dos arquivos
esqueleto_ep6.py
.util.py
econsole.py
. -
Mude o nome do arquivo
esqueleto_ep6.py
paraNUSP_ep6.py
, onde oNUSP
é o seu número USP. -
Abra o esqueleto no Spyder ou em qualquer outro editor ou ambiente apropriado para desenvolver programas em Python. Esse será o único arquivo que você deve editar.
-
Leia e preencha o cabeçalho com o seu nome, nusp, etc. Não modifique o resto do cabeçalho.
-
Execute o arquivo para ver se está tudo ok. O programa deve imprimir:
no. de pontos >>> 128 semente >>> 0 função ('0' para mac0110, '1' para mac0122) >>> 0 gere_pontos(): gerando 128 pontos ... gere_pontos(): pontos gerados. Vixe! Ainda não fiz a função mac0110(). Resultado: par mais próximo = [] menor distância = None tempo de execução = 0.00s executar animação ('s' para sim, 'n' para não) >>> n Fui!
-
Antes de escrever cada função, leia atentamente a especificação da função e os exemplos.
-
Teste cada função separadamente das demais usando o console do Spyder (= Python Shell ou IPython). Você também pode usar para os testes um terminal.
-
Teste o EP6 completo, chamando agora a função
main()
, inclusive com outros exemplos além dos fornecidos. -
Após testar o seu programa com vários exemplos, entregue o arquivo
NUSP_ep6.py
. -
Não deixe de seguir as Instruções para entrega de EPs.
Entrega
A primeira entrega deve ser feita até o dia 06/10 (até 23h55m).
O EP receberá comentários no dia 07/10.
Uma nova versão poderá ser entregue até o dia 09/10 10/10 (até 23h55m).
- 27 setembro 2016, 12:27 PM
- 4 outubro 2016, 10:51 AM
- 27 setembro 2016, 12:22 PM