Fundamentos teóricos de Dividir e Conquistar

22

Quando se trata do design de algoritmos, geralmente se emprega as seguintes técnicas:

  • Programaçao dinamica
  • A estratégia gananciosa
  • Dividir e conquistar

Enquanto para os dois primeiros métodos, existem fundamentos teóricos bem conhecidos, a saber, o Princípio de Optimalidade de Bellman e a teoria matróide (resp. Greedoide), não consegui encontrar uma estrutura geral para algoritmos baseados em D&C.

Em primeiro lugar, estou ciente de algo que nós (ou melhor, o prof) introduzimos em uma classe de programação funcional, chamada "esqueleto algorítmico", que surgiu no contexto de combinadores. Como exemplo, demos um esqueleto para os algoritmos de D&C da seguinte maneira:

Definição : Seja conjuntos não vazios. Chamamos os elementos de soluções , e os elementos de (ou seja, os subconjuntos de ) são chamados de problemas . Então, um esqueleto de D & C é uma tupla de quatro , onde:S P : = P ( A ) A ( P β , β , D , C )A,SS P:=P(A)A(Pβ,β,D,C)

  • Pβ é um predicado sobre o conjunto de problemas e dizemos que um problema é básico se mantiver.pPβ(p)
  • β é um mapeamento que designa uma solução para cada problema básico.PβS
  • D é um mapeamento que divide cada problema em um conjunto de subproblemas.PP(P)
  • C é um mapeamento que une as soluções (dependendo do tipo de um "problema de pivô") dos subproblemas para produzir uma solução.P×P(S)S

Então, para um determinado esqueleto e um problema , a seguinte função genérica calcula uma solução (no formato formal sentido) para :p f s : P S ps=(Pβ,β,D,C)pfs:PSp

fs(p)={β(p)if p is basicC(p,f(D(p)))otherwise

onde na segunda linha usamos a notação para os subconjuntos do codomain de um mapeamento .X ff(X):={f(x):xX}Xf

No entanto, não examinamos mais as propriedades "estruturais" subjacentes dos problemas que podem ser formuladas dessa maneira (como eu disse, era uma classe de programação funcional e esse era apenas um pequeno exemplo). Infelizmente, não consegui encontrar mais referências sobre essa mesma abordagem. Portanto, não acho que as definições acima sejam bastante padrão. Se alguém reconhecer o que afirmei acima, ficaria feliz com os artigos relacionados.

Em segundo lugar, para a estratégia gananciosa, temos o famoso resultado de que um problema é corretamente resolvido pelo algoritmo ganancioso geral, se e somente se suas soluções constituírem um matróide ponderado. Existem resultados semelhantes para os algoritmos de D&C (não necessariamente com base no método descrito acima)?

Cornelius Brand
fonte

Respostas:

5

Um tratamento formal (parecido com o modelo proposto na pergunta) do sujeito usando o que é chamado de pseudo-morfismos (ou seja, funções que são quase morfismos, com alguns pré e pós-computação realizados), bem como considerações de complexidade análise e implementação paralela de tais algoritmos são fornecidas em:

Um modelo algébrico para dividir e conquistar e seu paralelismo por Zhijing G. Mou e Paul Hudak (em The Journal of Supercomputing , Volume 2, Edição 3, pp. 257-278, novembro de 1988)

Cornelius Brand
fonte
1

Não estou ciente de algo tão concreto quanto os Princípios de Optimalidade de Bellman para os algoritmos de Divisão e Conquista. No entanto, o fundamento subjacente de dividir e conquistar parece-me uma definição recursiva (ou indutiva) da entrada do problema e, em seguida, um meio de combinar soluções para o problema em soluções maiores. O principal insight aqui é pensar nas entradas do problema de forma recursiva e alavancá-la nos algoritmos D&C recursivos.

Tome mergesort como um exemplo. Vamos começar com a entrada, uma matriz de elementos. Pode-se definir recursivamente a estrutura da matriz da seguinte maneira:n

  • Para , a matriz está vazia.n=0
  • Para , a matriz é um elemento singletonn=1
  • Para , a matriz é a concatenação de uma matriz de tamanho ( esquerda ) e tamanho ( direita )n>1n2n2

Em seguida, abordamos o algoritmo mergesort, mapeando a classificação para essa estrutura. Os casos base, em que são trivialmente classificados. O caso recursivo começa classificando recursivamente onde os dados são recursivos , ou seja, esquerdo e direito . Em seguida, encontramos essencialmente um substituto para concatenar , que acaba sendo mesclado . Observe que basicamente pegamos a estrutura recursiva dos dados e a mapeamos para uma solução recursiva. n1

É importante observar que isso não leva necessariamente ao que você espera dos algoritmos de D&C. Poderíamos definir a estrutura da matriz da seguinte maneira:

  • Para , a matriz está vazia.n=0
  • Para , a matriz é um único elemento concatenado para uma matriz de tamanho . n - 1n>0n1

Seguindo a mesma estratégia que usamos para mesclar aqui, leva à classificação de inserção recursiva. Assim, normalmente desenvolvemos definições recursivas que envolvem vários elementos recursivos, ou seja, cortamos o conjunto de dados pela metade ou por terceiro.

Agora, existe o Teorema Mestre para a análise de algoritmos de D&C e isso lança alguma luz sobre as expectativas de eficiência dos subcomponentes de um algoritmo de D&C com uma eficiência geral específica do tempo de execução.

Logan Mayfield
fonte
Os exemplos que você dá se encaixam no contexto geral que eu dou na minha pergunta (e, de fato, pode ser útil que você dê uma aplicação concreta). No entanto, minha pergunta era se existe um critério (como BOP ou estrutura matróide) para que os problemas sejam solucionáveis ​​por algoritmos que se encaixam nesse padrão.
Cornelius Brand