E03 Limiar de conexidade geométrica
INTRODUÇÃO
Estude inicialmente o Web Exercise 45 (Gridding) de S&W: https://algs4.cs.princeton.edu/13stacks/. Não deixe de estudar a solução Grid.java fornecida pelos autores.
Observação. A versão de Grid.java dos autores tem um pequeno erro. A versão abaixo corrige tal erro.
Uma variante de Grid.java é GridDeluxe.java (abaixo), que tem uma saída gráfica. Note que GridDeluxe.java recebe, na entrada padrão, uma lista de pontos como entrada. Instâncias para GridDeluxe.java podem ser geradas usando-se RandomPoints.java. Por exemplo, você pode fazer
$ java-algs4 RandomPoints 10000 323 | java-algs4 GridDeluxe .01
$ java-algs4 RandomPoints 10000 323 | java-algs4 GridDeluxe .015
As imagens nas janelas produzidas pelos exemplos acima estão abaixo (image1.png e image2.png).
Damos agora algumas definições para enunciarmos nosso problema. Suponha que $X$ seja uma coleção de pontos no quadrado unitário. Seja $d$ um número real dado. Dizemos que dois pontos são $d$-próximos se a distância entre eles é menor ou igual a $d$. Dizemos que dois pontos $p$ e $q$ de $X$ estão $d$-conectados se existe uma sequência de pontos de $X$ tais que $x_0 = p$, $x_l = q$ e $x_{i-1}$ e $x_i$ são $d$-próximos para todo $0 < i\leq l$. Vamos dizer que $X$ é $d$-conexo se quaisquer dois pontos $p$ e $q$ de $X$ estão $d$-conectados.
Observação. Note que $X$ é $d$-conexo se e só se o grafo que obtemos ao executar GridDeluxe.java com parâmetro $d$ e entrada $X$ é conexo.
Problema do Limiar de Conexidade (PLC). Dado $X$, encontrar o menor $d$ tal que $X$ é $d$-conexo.
Neste exercício, você deve escrever um programa, chamado Threshold.java, que recebe $X$ como entrada e resolve o PLC para $X$.
DETALHES DE IMPLEMENTAÇÃO
Intervalo-resposta
Naturalmente, a resposta do PLC é um número real, de forma que teremos de lidar com aproximações. Seu programa Threshold.java deve devolver um intervalo $[d_1, d_2]$ dos números reais onde a resposta está. O intervalo não pode ser maior que $10^{-9}$, isto é, queremos que $d_2-d_1\leq 10^{-9}$.
Seu programa Threshold.java deve receber a entrada $X$ na entrada padrão. Assim, supondo que o arquivo entrada.txt contém $X$, para resolver o PLC com entrada $X$, seu programa será executado da seguinte forma:
$ java-algs4 Threshold < entrada.txt
A saída deve dar um intervalo onde a resposta se encontra:
$ java-algs4 Threshold < entrada.txt
Connectivity threshold in [0.23872863702383906, 0.2387286376823836]
(O arquivo entrada.txt usado no exemplo acima está abaixo; entrada.txt tem $30$ pontos.) Para encontrar o intervalo resposta, use o método da bisseção. Veja
https://en.wikipedia.org/wiki/Bisection_method
Note que o limiar de conexidade está sempre entre $0$ e $\sqrt 2$.
Saída gráfica
Além de dar o intervalo-resposta na saída padrão, como no exemplo acima, Threshold.java, quando chamado com um argumento de linha de comando adicional, deve ter uma saída gráfica como GridDeluxe.java. Por exemplo, ao fazer
$ java-algs4 Threshold - < entrada.txt
seu programa deve gerar uma janela gráfica.
Suponha que, na entrada entrada.txt, Threshold.java disse que o limiar de conexidade está entre $d_0$ e $d_1$. A imagem que Threshold.java produz deve ser a mesma que GridDeluxe.java produz com a entrada entrada.txt e parâmetro de distância $d_1$, a menos do fato que as arestas de comprimento no intervalo semi-aberto $(d_0, d_1]$ devem ser vermelhas. Por exemplo, a chamada acima produziu uma janela com a imagem em image_30.png abaixo.
Observação. Ao usar bisseção para encontrar o intervalo-resposta, se $X$ tiver pelo menos dois pontos, é natural o limiar de conexidade não ser $d_0$. Assim, nesse caso, sempre haverá pelo menos uma aresta vermelha e as arestas vermelhas têm a seguinte propriedade: sua remoção desconecta o grafo na imagem.
DESEMPENHO
Alguns exemplos de execução são dados abaixo. Alguns comentários sobre a ordem de grandeza do tempo de execução de Threshold.java (minha versão, no meu laptop) são também dados abaixo. Seu programa deve ter tempo de execução basicamente comparável (isto é não pode ser substancialmente mais demorado).
EXEMPLOS DE EXECUÇÃO
Abaixo encontram-se arquivos gerados pelos exemplos a seguir. Note que, devido a erros de arredondamento, suas execuções podem ter saídas levemente diferentes.
$ java-algs4 RandomPoints 500 323 | time java-algs4 Threshold
Connectivity threshold in [0.087407511458129, 0.08740751211667351]
0.62 real 0.85 user 0.09 sys
$ java-algs4 RandomPoints 1000 323 | time java-algs4 Threshold
Connectivity threshold in [0.05258146845917851, 0.05258146911772301]
0.72 real 1.05 user 0.09 sys
$ java-algs4 RandomPoints 5000 323 | time java-algs4 Threshold
Connectivity threshold in [0.022126151773939434, 0.02212615243248394]
2.16 real 3.00 user 0.16 sys
$ java-algs4 RandomPoints 10000 323 | time java-algs4 Threshold
Connectivity threshold in [0.017839457056535644, 0.01783945771508015]
5.29 real 6.46 user 0.20 sys
$ java-algs4 RandomPoints 20000 323 | time java-algs4 Threshold
Connectivity threshold in [0.014392878104677532, 0.01439287876322204]
18.12 real 19.56 user 0.27 sys
$ java-algs4 RandomPoints 30000 323 | time java-algs4 Threshold
Connectivity threshold in [0.010431961404105749, 0.010431962062650256]
61.10 real 60.75 user 0.78 sys
Os tempos de execução variam de menos de 1 segundo a 1 minuto.
As imagens produzidas nas seis chamadas acima também são dadas abaixo.
OBSERVAÇÕES
Para manipular intervalos, você deve usar a classe Interval1D.java de S&W. Nesse exercício, é natural usar o tipo-de-dado union-find. Use, origatoriamente, a implementação UF.java de S&W.
- 23. April 2021, 10:06
- 23. April 2021, 10:06
- 23. April 2021, 10:06
- 23. April 2021, 10:06
- 23. April 2021, 10:06
- 23. April 2021, 10:06
- 23. April 2021, 10:06
- 23. April 2021, 10:06
- 23. April 2021, 10:06
- 23. April 2021, 10:06
- 23. April 2021, 10:06
- 23. April 2021, 10:06
- 23. April 2021, 10:06