Exemplos de algoritmos recursivos sofisticados

14

Eu estava explicando o famoso algoritmo determinístico de seleção em tempo linear ( algoritmo de mediana de medianas) a um amigo.

A recursão neste algoritmo (embora seja muito simples) é bastante sofisticada. Existem duas chamadas recursivas, cada uma com parâmetros diferentes.

Eu estava tentando encontrar outros exemplos de algoritmos recursivos tão interessantes, mas não consegui encontrar nenhum. Todos os algoritmos recursivos que eu pude apresentar são simples recursões de cauda ou simples divisão e conquista (onde as duas chamadas são "as mesmas").

Você pode dar alguns exemplos de recursão sofisticada?

algorithms recursion elektronaj
fonte

Atravessar um labirinto ou, geralmente, um gráfico com uma pesquisa de largura é um exemplo simples de uma recursão interessante.

utdiscant, acho que o BFS não se qualifica para a minha pergunta, pois pode ser fácil e naturalmente implementado usando uma fila e um loop while.

31712 elektronaj

Que tal voltar atrás na solução de quebra-cabeças e análise? E os algoritmos de classificação e desagregação também têm recursões fora do padrão.

uli

Algoritmos de memorização ?

Kaveh

2

@vzn: Uma fila não pode substituir uma pilha. BFS é um caso especial.

Raphael

15

Minha recorrência favorita aparece em algoritmos sensíveis à saída para calcular cascos convexos, primeiro por Kirkpatrick e Seidel , mas depois repetidos por outros. Seja o tempo para calcular o casco convexo de pontos no plano, quando o casco convexo tiver vértices. (O valor de não é conhecido antecipadamente, além do limite trivial .) O algoritmo de Kirkpatrick e Seidel produz a recorrência que e e $T(n,h)$ $n$ $h$ $h$ $h\le n$

T (n, h) = {\begin{cases} O (n) & if n \leq 3 or h \leq 3 \\ T (n_{1}, h_{1}) + T (n_{2}, h_{2}) + O (n) & otherwise \end{cases}

$T(n,h) = \begin{cases} O(n) & \text{if }n \le 3 \text{ or } h \le 3 \\ T(n_1, h_1) + T(n_2, h_2) + O(n) & \text{otherwise} \end{cases}$

n_{1}, n_{2} \leq 3 n / 4

$n_1, n_2 \le 3n/4$

n_{1} + n_{2} = n

$n_1 + n_2 = n$

h_{1} + h_{2} = h

$h_1 + h_2 = h$ .

A solução é . Isso é um pouco surpreendente, pois não é o parâmetro que está sendo dividido igualmente. Mas, de fato, o pior caso de recorrência ocorre quando e são aproximadamente ; se de alguma forma magicamente for sempre constante, a solução seria . $T(n,h) = O(n\log h)$ $h$ $h_1$ $h_2$ $h/2$ $h_1$ $T(n,h) = O(n)$

Eu usei uma variante dessa recorrência em um dos meus primeiros trabalhos de topologia computacional : onde e . Novamente, a solução é , e o pior caso ocorre quando e são sempre divididos igualmente.

T (n, g) = {\begin{cases} O (n) & if n \leq 3 or g = 0 \\ T (n_{1}, g_{1}) + T (n_{2}, g_{2}) + O (min {n_{1}, n_{2}}) & otherwise \end{cases}

$T(n,g) = \begin{cases} O(n) & \text{if }n \le 3 \text{ or } g = 0\\ T(n_1, g_1) + T(n_2, g_2) + O(\min\{n_1, n_2\}) & \text{otherwise} \end{cases}$

n_{1} + n_{2} = n

$n_1 + n_2 = n$

g_{1} + g_{2} = g

$g_1 + g_2 = g$

O (n \log g)

$O(n\log g)$

n

$n$

g

$g$

JeffE
fonte

Eu tenho problemas com a condição "se ou "; o que significa aqui? Existem constantes delimitadoras globalmente que e precisam ser reduzidas para terminar no caso de uma (e os autores não se dão ao trabalho de fornecer). Porque se eu o ler literalmente (ou seja, interpretar da mesma maneira que na mesma linha), o caso dois nunca ou sempre acontece (nem tenho certeza). Abuso de notação levado longe demais, imho.

n = O (1)

$n=O(1)$

h = O (1)

$h=O(1)$

O

$O$

n

$n$

h

$h$

O (1)

$O(1)$

O (n)

$O(n)$

Raphael

1

Desculpe, editei minha resposta para esclarecer. significava "sua constante favorita". Eu usei na minha revisão, mas Teriam funcionado da mesma forma.

O (1)

$O(1)$

3

$3$

10^{10^{100}!}

$10^{10^{100}!}$

jeffe

Como você desenhou esses diagramas nos documentos de topologia computacional?

User119264

12

A recursão que usei no meu artigo "Um algoritmo de tempo linear para calcular o diagrama de Voronoi de um polígono convexo" por Aggarwal et al também é bastante complicada.

Aqui está uma descrição do algoritmo de nosso artigo. Caso não esteja claro a partir da descrição, na etapa 3, os pontos vermelhos serão particionados em pontos vermelhos e granados. Os passos 1, 3 e 6 são todos de tempo linear. Também sabemos que se é o número total de pontos, , e para alguns . $n$ $|\mathrm{B}| \geq \alpha n$ $|\mathrm{R}| \geq \beta n$ $|\mathrm{C}| \geq \gamma n$ $\alpha, \beta, \gamma > 0$

Vou deixar você descobrir por que todo o algoritmo leva tempo linear.

Particione os pontos originais nos conjuntos azul e vermelho B e R.

Calcule recursivamente o casco convexo dos pontos azuis.

Usando a estrutura do casco azul, selecione os pontos carmesim C.

Adicione os pontos carmesim ao casco azul, um de cada vez.

Calcule recursivamente o casco convexo dos pontos G. da granada

Mesclar este casco granada com o casco azul expandido da etapa 4.

O que torna o algoritmo linear é a capacidade de adicionar uma fração fixa dos pontos vermelhos ao casco azul a um custo constante por ponto. Os pontos adicionados são os pontos carmesim.

A recursão é, portanto, onde você não conheceemas é garantido que .

T (n) = T (| B |) + T (| G |) + O (n)

$T(n) = T(|B|) + T(|G|) + O(n)$

| B |

$|B|$

| G |

$|G|$

| B | + | G | \leq (1 - γ) n

$|B| + |G| \leq (1-\gamma) n$

Peter Shor
fonte

7

Há uma variação na recorrência da descoberta mediana que vem da pesquisa por intervalo com semiplanos. A recorrência em si é da forma

T (n) = T (n / 2) + T (n / 4) + c n

$T(n) = T(n/2) + T(n/4) + cn$ que é semelhante à recorrência da mediana. Para mais informações, veja as notas da aula de Jeff Erickson e, em particular, a Seção 4.

Suresh
fonte

1

A minha resposta aqui ( cs.stackexchange.com/questions/332/... ) passa a ter exatamente o mesmo de recorrência para o seu tempo de execução :)

Alex ten Brink

6

Existem vários algoritmos recursivos interessantes [1], [2] usados na previsão da estrutura secundária do RNA. Deixada por conta própria, uma cadeia de RNA formará pares de bases consigo mesma; um exemplo relativamente simples de [3] calcula o número máximo de bases aninhadas e emparelhadas que uma sequência de RNA formará consigo mesma:

$M(i,j)=\underset{i\leq k < j - L_{min}}{max} \begin{cases} M(i,k-1)+ M(k+1, j-1)+1 \\M(i, j-1) \end{cases}$

Dobragem ideal por computador de grandes seqüências de RNA usando termodinâmica e informações auxiliares por M. Zuker, P. Stiegler (1981)
Um algoritmo de programação dinâmica para previsão de estrutura de RNA incluindo pseudo-nós por E. Rivas, SR Eddy (1999)
Algoritmo rápido para prever a estrutura secundária do RNA de fita simples por R. Nussinov, AB Jacobson (1980)

rphv
fonte

Uma proposta relacionada aqui é bastante complexa, pois apresenta três recursões mutuamente dependentes (programação dinâmica).

Raphael

4

Eu ainda não entendo o que você quer dizer com "recursão sofisticada". Por exemplo, a etapa de recursão no algoritmo FFT é sofisticada!

Mas se você deseja procurar recursões mais complicadas , recursões mútuas podem ser uma resposta possível. A recursão mútua é útil ao trabalhar com linguagens de programação funcionais . A recursão mútua é a característica principal dos analisadores de descida recursiva .

Dai
fonte

Bem, a recursão na FFT (forma mais simples de Cooley-Tukey) é dividir e conquistar "padrão". Isso é aparente pela sua complexidade O (nlogn). As 2 chamadas recursivas (1 para o par, 1 para as chances) são um pouco "iguais".

Elektronaj

3

Em cima da minha cabeça, a função McCarthy 91

F(N) = 
    n - 100    if n > 100
    F(F(n+11)) if n <= 100

e a função Ackermann

A(m, n) = 
    n + 1             if m = 0
    A(m-1, 1)         if m > 0 and n = 0
    A(m-1, A(m, n-1)) if m > 0 and n > 0

pode contar como funções incomuns, embora de brinquedo, recursivas.

hugomg
fonte

Exemplos de algoritmos recursivos sofisticados

Respostas: