Aluno: Marcelo Kawata
1. Introdução
1.1. Algoritmos
Aleatórios
2. Construção Incremental Aleatória
2.1. Problema
do Par Mais Próximo
Algoritmo Incremental Aleatório
Análise do algoritmo
Estrutura de Dados
Teorema 2,1
2.2. Um
outro exemplo: Interseção de Hiperplanos
3. Referências
Este trabalho é uma pequena introdução à Construção Incremental Aleatória, uma técnica muito utilizada para resolução de problemas em Geometria Computacional. É uma variação da construção incremental (algoritmos incrementais) vistos em aula. Antes, teremos uma breve explanação sobre algoritmos aleatórios, para depois estudar dois problemas: o Par-Mais-Próximo e Interseção de Hiperplanos.
A utilização de algoritmos aleatórios foi introduzida em 1976, em trabalhos independentes, por Rabin e por Solovay e Strassen. Atualmente, estes algoritmos (que podem tanto ser seqüenciais ou paralelos) são aplicados para obtenção de soluções eficientes em diversos problemas computacionais.
As duas principais vantagens apresentadas pelos algoritmos aleatórios, segundo Rajasekaran e Sen [1], são sua simplicidade e eficiência. Grande parte dos algoritmos aleatórios encontrados na literatura são simples e de fácil compreensão, se comparados com os algoritmos determinísticos mais eficientes para resolver o mesmo problema.
Em boa parte dos casos, os algoritmos aleatórios também são mais rápidos que os determinísticos correspondentes, de acordo com Karger [2]. Quando não são melhores, algumas idéias de randomização podem ser aplicadas para obtenção de algoritmos eficientes.
Os algoritmos aleatórios não necessariamente utilizam números aleatórios, como pode-se imaginar, mas sim tomam decisões aleatórias durante a execução, ou escolhem de forma aleatória um elemento da entrada em cada iteração, visando ganhar o tempo que muitos algoritmos determinísticos gastam com o pré-processamento (como ordenação das entradas).
Veremos na Seção 2 uma aplicação desta técnica em Geometria Computacional, a construção incremental aleatória, baseada no trabalho de Surender Baswana [3].
Algoritmos incrementais, como os vistos em aula, utilizam a técnica de construção incremental, que consiste em resolver os problemas de uma maneira incremental. Um exemplo típico de algoritmo incremental é o insertion sort, onde inicialmente temos um conjunto vazio e adicionamos elementos sucessivamente neste conjunto, sempre mantendo em cada iteração a ordem (crescente ou decrescente) entre os elementos inseridos. De uma forma geral, um algoritmo incremental trabalha da seguinte maneira:
Sejam i1, i2, ... , in, os n elementos da entrada e o objetivo é computar uma função f({i1, i2, ... , in}). Começamos com um conjunto vazio S e f(f ), adicionamos elementos sucessivamente em S e mantemos f(S) a cada iteração do algoritmo. Então, teremos um total de n iterações no algoritmo e ao final obtemos a solução S para o problema.
A complexidade de tempo de um algoritmo incremental depende do tempo gasto em cada iteração de execução do mesmo. Em algumas instâncias (conjunto de entrada) de um problema a ser resolvido, pode ocorrer que a cada iteração, o tempo gasto seja muito alto, levando o algoritmo ao pior caso de tempo. Nestes casos, é vantajoso incrementar o conjunto S tomando-se elementos aleatoriamente.
A construção incremental aleatória (ou RIC - Randomized
Incremental Construction) é a técnica na qual adicionamos elementos ao
conjunto S aleatoriamente, com o objetivo de obter um limite para o tempo
do cálculo de f(S) em cada iteração. Veremos a seguir um
exemplo da aplicação da RIC, o Problema do Para Mais-Próximo em E2,
extraída do trabalho de Surender Baswana [3]..
Este problema foi resolvido na disciplina através de algoritmos determinísticos. Teremos agora a aplicação da construção incremental aleatória para a resolução deste problema.
Problema do Par-Mais-Próximo: Dado um conjunto P com n pontos em duas dimensões, o objetivo é encontrar o par de pontos mais próximos entre si deste conjunto.
Para resolver o problema através de um algoritmo incremental, iniciamos com um conjunto de pontos S vazio, e incrementando este conjunto através de inclusões sucessivas de um ponto a cada iteração. O algoritmo incremental terá então n iterações, onde no final da i-ésima iteração teremos o conjunto Si contendo i pontos. Na iteração i+1 devemos adicionar o ponto pi+1 e calcular a distância di+1. Observe que se a menor distância d', entre pi+1 e os pontos de Si é menor que a distância di, então di+1 := d', senão di+1 := di. Como em todos os algoritmos incrementais, o tempo necessário para o cálculo de di+1 dado di determina a complexidade de tempo do algoritmo. Entretanto, precisamos de uma estrutura de dados que auxilie no cálculo do vizinho mais próximo de pi+1 de modo eficiente (melhor que o método de força bruta de tempo q(i) para calcular a distância entre pi+1 e todos os i pontos do conjunto Si). Devemos então utilizar uma estrutura de dados D que possui a seguinte funcionalidade:
No final desta seção, veremos como projetar a estrutura de dados D. Agora veremos o algoritmo incremental aleatório para a obtenção da distância d do par-mais-próximo de um conjunto P:
Algoritmo: Par-Mais-Próximo Incremental Aleatório
Entrada: um conjunto de P com n pontos em E2
Saída: a distância entre o par-mais-próximo de pontos de P
while (i < n) do
begin
Passo 1: encontre a célula da grade que contém ponto pi+1, usando D(Si).
Passo 2: procure o ponto p Î Si mais próximo de pi+1, e seja d' a distância entre p e pi+1.
Passo 3: if (d' > di)
then Insira pi+1 em Si
else {
di+1¬d'
Construa D(Si+1, di+1)
}
end
A (i+1)-ésima iteração do algoritmo acima, que consiste no inclusão de pi+1
e cálculo de di+1 pode ser visualizada na figura abaixo:
Análise do Algoritmo Incremental Aleatório:
Agora analisaremos a complexidade de tempo dos três passos da (i+1)-ésima iteração do algoritmo, utilizando a estrutura D(Si).
Passo 1: a localização da célula c, que contém o ponto pi+1, pode ser executada em O(log i) passos, utilizando-se D(Si)
Passo 2: Para encontrar o ponto de Si mais próximo de pi+1, precisamos encontrar a distância entre pi+1 e cada ponto da célula c e das células vizinhas a c. Desta forma, temos um total de 9 céluas (c e suas vizinhas) e no máximo 36 pontos (4 pontos por célula), todas potenciais candidatas a serem o ponto mais próximo de pi+1. Assim, o Passo 2 envolve a localização das nove células vizinhas a c (o que requer O(log n) passos por célula) e calcular a distância entre pi+1 e um número constante de pontos (no máximo 36). Usando D(Si), podemos executar o Passo 2 em tempo O(log i).
Passo 3: O bloco if requer tempo O(log i). O bloco else é a operação mais complexa pois consiste na construção de D(Si+1, di+1). Devido à funcionalidade da estrutura D (descrita anteriormente), este passo pode ser executado em tempo O((i+1) log(i+1))
Complexidade do Algoritmo:
Observe que permutamos os n pontos dados (com cada permutação igualmente possíveis). O tempo de execução na (i+1)-ésima iteração é portanto uma variável aleatória. Pela análise dos três passos do algoritmo, notamos que Passo1 e Passo 2 são executados em toda iteração a um custo de tempo c1 log i, onde c1 é uma constante. Se a inclusão do ponto pi+1 diminui a distância do par-mais-próximo, um custo adicional c1i log i é necessário para a construção de D(Si+1, di+1), caso contrário, o custo adicional é O(log i).
Desta forma, o tempo necessário na i-ésima iteração pode ser expressa como:
T(i) = c1 log i + Prob[di+1< di] . c2(i + 1) log (i + 1) (1)
onde, c1 e c2 são constantes e Prob[di+1< di] é a probabilidade de di+1< di.
Devemos agora calcular Prob[di+1< di]. Para isso, particionamos n! permutações em grupos g1, g2,..., gL tais que o conjunto dos primeiros i + 1 pontos em todas as permutações pertencentes a um grupo sejam idênticos. Utilizaremos o símbolo p para denotar uma permutação. Podemos escrever a seguinte equação:
Prob[di+1< di] = Sgk Prob[primeira p Î gk] . Prob[di+1< di | p Îgk] (2)
Agora limitaremos Prob[di+1< di | p Îgk]. Seja Ci+1 o conjunto de i + 1 pontos que define o grupo de permutações gi.
Se há apenas um par-mais-próximo em Ci+1, então di+1< di ocorre apenas se um dos pontos que definem o único par-mais-próximo aparece na (i + 1)-ésima posição. A probabilidade deste evento ocorrer dado um gk particular é igual a 2 / (i + 1).
Prob[di+1< di | p Î gk] <= 2 / (i + 1)
E, pela equação (2), segue que:
Prob[di+1< di] <= 2 / (i + 1) (3)
Das equações (3) e (1), concluímos que o tempo gasto na (i + 1)-ésima iteração é:
T(i + 1) = c1 log i + [2 / (i + 1)] . c2(i + 1) log (i + 1) = O( log (i + 1) )
A complexidade de tempo total do algoritmo é a soma das variáveis aleatórias T(i) para 1 < i < n. Logo, podemos concluir que a complexidade de tempo do algoritmo é O(n log n). Note que este tempo é o mesmo do algoritmo de divisão e conquista visto em aula (algoritmo determinístico ótimo).
Considere um conjunto Si de i pontos em 2-dimensões, cuja distância do par-mais-próximo de pontos seja igual a di. Para cada ponto p Î Si, calculamos o intervalo na abscissa (eixo x) referente à sua coordenada x. Associamos um ponto (x1, y1) ao intervalo [(j di, (j + 1) di)] no eixo x tal que j di <= x1 < di (j + 1). Identificamos então cada ponto por este intervalo. Podemos construir agora uma árvore T com intervalos para o conjunto dos x-intervalos associados aos pontos. Podemos observar que cada folha é associada a um intervalo de tamanho di. Armazenamos os pontos do conjunto Si nas folhas desta árvore (a inserção de cada ponto requer que seja percorrido o caminho da raiz de T até uma folha, o que determina um custo de O(log i) por ponto). Todos os pontos pertencentes aos mesmo x-intervalo estarão na mesma folha. Seja sL Î Si um conjunto de pontos pertencente à folha L. Nós construímos uma árvore similar de intervalos para a ordenada y para os pontos de sL. Então a estrutura de dados D(Si) é uma árvore de intervalos para a direção x, cujas folhas têm cada uma árvore de intervalos para a direção y. Desta forma, temos a estrutura da grade virtual mencionada anteriormente.
A partir da descrição da estrutura de dados, torna-se evidente que o tempo necessário para a construção de D(Si) é O(i log i), pois o armazenamento de cada ponto exige que sejam percorridas duas árvores de intervalos, cada uma de tamanho menor ou igual a i. Assim, segue que a localização de uma célula para um novo elemento (assim como para inserção) pode ser executada em tempo O(log i). Desta forma, esta estrutura de dados atende aos requisitos apresentados no início desta seção.
Como conclusão, podemos enunciar o seguinte teorema:
Teorema 2.1: O par mais próximo para um conjunto de n pontos de 2-dimensões pode ser obtido utilizando construção incremental aleatória em complexidade de tempo O(n log n) e espaço linear para armazenamento.
Para resolver este problema, utilizamos a construção incremental aleatória, na qual em cada passo adicionamos em um conjunto S um hiperplano, e então atualizamos a região comum a todos os hiperplanos adicionados a S até o passo atual.
Pela figura acima , podemos observar que a região comum aos hiperplanos pode
ser obtida da seguinte forma: a cada iteração, adicionamos um hiperplano hi+1
ao conjunto S. Se este hiperplano formar um ou mais triângulos com os
hiperplanos que estão na fronteira do polígono que representa a região comum
dos hiperplanos em S, então estes triângulos são adicionado à região de
interseção dos hiperplanos, formando assim um novo polígono.
Ao final, a união de todos os triângulos determinará o região de interseção dos hiperplanos.
[1] Sanguthevar Rajasekaran e Sandeep Sen, Parallel Randomized Algorithms for Selection, Sorting, and Convex Hulls
[2] David Karger, Randomized Algorithms (6.856J) - Course Notes
[3] Surender Baswana, Randomized Incremental Construction: An introduction through examples
[4] Gaurav e Soumyadeb, Random Incremental Construction