SCC-211 - Cap­tulo 11 Programa§£o Din¢ .Paradigmas de Resolu§£o de Problemas Programa§£o

  • View
    216

  • Download
    0

Embed Size (px)

Text of SCC-211 - Cap­tulo 11 Programa§£o Din¢ .Paradigmas de Resolu§£o de...

  • Paradigmas de Resoluo de ProblemasProgramao Dinmica

    SCC-211 - Captulo 11Programao Dinmica

    Joo Lus Garcia Rosa1

    1Departamento de Cincias de ComputaoInstituto de Cincias Matemticas e de Computao

    Universidade de So Paulo - So Carloshttp://www.icmc.usp.br/~joaoluis

    2011

    Joo Lus G. Rosa c 2011 - SCC-211: XI. Programao Dinmica 1/53

    http://www.icmc.usp.br/~joaoluis

  • Paradigmas de Resoluo de ProblemasProgramao Dinmica

    Sumrio

    1 Paradigmas de Resoluo de ProblemasBusca Completa (backtracking)Algoritmos diviso-e-conquistaAlgoritmos gulosos

    2 Programao DinmicaPDExemplo

    Joo Lus G. Rosa c 2011 - SCC-211: XI. Programao Dinmica 2/53

  • Paradigmas de Resoluo de ProblemasProgramao Dinmica

    Busca Completa (backtracking)Algoritmos diviso-e-conquistaAlgoritmos gulosos

    Os quatro paradigmas

    Os quatro paradigmas de resoluo de problemas maiscomumente usados em competies de programaoso [3]:

    1 Busca Completa (backtracking)2 Diviso e Conquista3 Busca Gulosa4 Programao Dinmica

    Joo Lus G. Rosa c 2011 - SCC-211: XI. Programao Dinmica 3/53

  • Paradigmas de Resoluo de ProblemasProgramao Dinmica

    Busca Completa (backtracking)Algoritmos diviso-e-conquistaAlgoritmos gulosos

    Sumrio

    1 Paradigmas de Resoluo de ProblemasBusca Completa (backtracking)Algoritmos diviso-e-conquistaAlgoritmos gulosos

    2 Programao DinmicaPDExemplo

    Joo Lus G. Rosa c 2011 - SCC-211: XI. Programao Dinmica 4/53

  • Paradigmas de Resoluo de ProblemasProgramao Dinmica

    Busca Completa (backtracking)Algoritmos diviso-e-conquistaAlgoritmos gulosos

    Algoritmos tentativa-e-erro

    Um algoritmo tentativa-e-erro aquele que testaexaustivamente todas as solues possveis de umproblema, de modo a obter a desejada,As solues so testadas indiscriminadamente:

    No utiliza critrios para eliminar outras solues que nopodero ser melhores que a obtida no estgio considerado.

    As solues so enumeradas de modo semelhante aopercurso em uma rvore que possua todas as solues,Muitas vezes a rvore de solues cresceexponencialmente [8]!

    Joo Lus G. Rosa c 2011 - SCC-211: XI. Programao Dinmica 5/53

  • Paradigmas de Resoluo de ProblemasProgramao Dinmica

    Busca Completa (backtracking)Algoritmos diviso-e-conquistaAlgoritmos gulosos

    Algoritmos tentativa-e-erro [8]

    Algoritmos tentativa e erro no seguem regra fixa decomputao:

    Passos em direo soluo final so tentados eregistrados,Caso esses passos tomados no levem soluo final,eles podem ser retirados e apagados do registro.

    Quando a pesquisa na rvore de solues crescerapidamente necessrio usar algoritmos aproximados ouheursticas que no garantem a soluo tima mas sorpidas.

    Joo Lus G. Rosa c 2011 - SCC-211: XI. Programao Dinmica 6/53

  • Paradigmas de Resoluo de ProblemasProgramao Dinmica

    Busca Completa (backtracking)Algoritmos diviso-e-conquistaAlgoritmos gulosos

    Algoritmos tentativa-e-erro

    Exerccio:Qual o menor caminho da cidade a at a c?

    Joo Lus G. Rosa c 2011 - SCC-211: XI. Programao Dinmica 7/53

  • Paradigmas de Resoluo de ProblemasProgramao Dinmica

    Busca Completa (backtracking)Algoritmos diviso-e-conquistaAlgoritmos gulosos

    Algoritmos tentativa-e-erro

    Exerccio:TODOS os caminhos so enumerados:

    a b c: 21a b d c: 32a b f d c: 51

    Joo Lus G. Rosa c 2011 - SCC-211: XI. Programao Dinmica 8/53

  • Paradigmas de Resoluo de ProblemasProgramao Dinmica

    Busca Completa (backtracking)Algoritmos diviso-e-conquistaAlgoritmos gulosos

    Sumrio

    1 Paradigmas de Resoluo de ProblemasBusca Completa (backtracking)Algoritmos diviso-e-conquistaAlgoritmos gulosos

    2 Programao DinmicaPDExemplo

    Joo Lus G. Rosa c 2011 - SCC-211: XI. Programao Dinmica 9/53

  • Paradigmas de Resoluo de ProblemasProgramao Dinmica

    Busca Completa (backtracking)Algoritmos diviso-e-conquistaAlgoritmos gulosos

    Algoritmos diviso-e-conquista

    O paradigma diviso-e-conquista consiste em:1 Dividir o problema a ser resolvido em subproblemas

    menores e independentes;2 Encontrar solues para as partes;3 Combinar as solues obtidas em uma soluo global.

    Os algoritmos utilizam recurso para dividir e combinar.Processo recursivo :

    dada uma entrada, se ela suficientemente simples,obtm-se diretamente uma sada correspondente;caso contrrio, ela decomposta em entradas maissimples, para as quais se aplica o mesmo processo,obtendo sadas correspondentes que so entocombinadas em uma sada para a entrada original.

    Joo Lus G. Rosa c 2011 - SCC-211: XI. Programao Dinmica 10/53

  • Paradigmas de Resoluo de ProblemasProgramao Dinmica

    Busca Completa (backtracking)Algoritmos diviso-e-conquistaAlgoritmos gulosos

    Algoritmos diviso-e-conquista [8]

    Exemplo: encontrar o maior e o menor elemento de umvetor de inteiros, A[1..n],n 1:

    void MaxMin4 (int Linf, int Lsup, int *Max, int *Min){int Max1, Max2, Min1, Min2, Meio;if (Lsup - Linf Max2) *Max = Max1; else *Max = Max2;if (Min1 < Min2) *Min = Min1; else *Min = Min2; }

    }

    Cada chamada de MaxMin4 atribui Max e Min o maior eo menor elemento em A[Linf ], A[Linf + 1], ..., A[Lsup].

    Joo Lus G. Rosa c 2011 - SCC-211: XI. Programao Dinmica 11/53

  • Paradigmas de Resoluo de ProblemasProgramao Dinmica

    Busca Completa (backtracking)Algoritmos diviso-e-conquistaAlgoritmos gulosos

    Diviso-e-conquista: anlise do exemplo [8]

    Seja f (n) o nmero de comparaes entre os elementosde A, se A contiver n elementos,

    f (n) ={

    1 para n 2f (bn/2c) + f (dn/2e) + 2 para n > 2

    Quando n = 2i para algum inteiro positivo i :

    f (n) = 2f (n/2) + 22f (n/2) = 4f (n/4) + 2 24f (n/4) = 8f (n/8) + 2 2 2

    ......

    2i2f (n/2i2) = 2i1f (n/2i1) + 2i1

    Joo Lus G. Rosa c 2011 - SCC-211: XI. Programao Dinmica 12/53

  • Paradigmas de Resoluo de ProblemasProgramao Dinmica

    Busca Completa (backtracking)Algoritmos diviso-e-conquistaAlgoritmos gulosos

    Diviso-e-conquista: anlise do exemplo [8]

    Adicionando lado a lado, obtm-se:

    f (n) = 2i1f (n/2i1) +i1

    k=1 2k

    = 2i1f (2) + 2i 2= 2i1 + 2i 2= 3n2 2

    Logo, f (n) = 3n/2 2 para o melhor caso, pior caso ecaso mdio (soluo tima).

    Joo Lus G. Rosa c 2011 - SCC-211: XI. Programao Dinmica 13/53

  • Paradigmas de Resoluo de ProblemasProgramao Dinmica

    Busca Completa (backtracking)Algoritmos diviso-e-conquistaAlgoritmos gulosos

    Algoritmos diviso-e-conquista

    Exemplos de algoritmos:Busca binria;SelectionSort, MergeSorte, Quicksort;Maior elemento de uma sequncia;Fibonacci recursivo.

    Joo Lus G. Rosa c 2011 - SCC-211: XI. Programao Dinmica 14/53

  • Paradigmas de Resoluo de ProblemasProgramao Dinmica

    Busca Completa (backtracking)Algoritmos diviso-e-conquistaAlgoritmos gulosos

    Sumrio

    1 Paradigmas de Resoluo de ProblemasBusca Completa (backtracking)Algoritmos diviso-e-conquistaAlgoritmos gulosos

    2 Programao DinmicaPDExemplo

    Joo Lus G. Rosa c 2011 - SCC-211: XI. Programao Dinmica 15/53

  • Paradigmas de Resoluo de ProblemasProgramao Dinmica

    Busca Completa (backtracking)Algoritmos diviso-e-conquistaAlgoritmos gulosos

    Algoritmos gulosos

    So tipicamente usados para resolver problemas deotimizao,Por exemplo, o algoritmo para encontrar o caminho maiscurto entre duas cidades:

    Um algoritmo guloso escolhe a estrada que parece maispromissora no instante atual e nunca muda essa deciso,independentemente do que possa acontecer depois.

    A cada iterao:seleciona um elemento conforme uma funo gulosa,marca-o para no consider-lo novamente nos prximosestgios,atualiza a entrada,examina o elemento selecionado quanto sua viabilidade,decide a sua participao ou no na soluo.

    Joo Lus G. Rosa c 2011 - SCC-211: XI. Programao Dinmica 16/53

  • Paradigmas de Resoluo de ProblemasProgramao Dinmica

    Busca Completa (backtracking)Algoritmos diviso-e-conquistaAlgoritmos gulosos

    Algoritmos gulosos

    Algoritmo guloso genrico:C: conjunto de candidatos;S: conjunto soluo.

    S = Enquanto (C 6= ) e (S no tem soluo)

    x = seleciona(C)C = C {x}Se (S + {x} vivel) ento S = S + {x}

    Se (S tem soluo) ento retorna SSeno no existe soluo

    Joo Lus G. Rosa c 2011 - SCC-211: XI. Programao Dinmica 17/53

  • Paradigmas de Resoluo de ProblemasProgramao Dinmica

    Busca Completa (backtracking)Algoritmos diviso-e-conquistaAlgoritmos gulosos

    Caractersticas dos Algoritmos Gulosos [8]

    Para construir a soluo tima existe um conjunto ou listade candidatos,So acumulados um conjunto de candidatos consideradose escolhidos, e o outro de candidatos considerados erejeitados,Existe uma funo que verifica se um conjunto particularde candidatos produz uma soluo (sem considerarotimalidade no momento),Outra funo verifica se um conjunto de candidatos vivel (tambm sem se preocupar com a otimalidade),Uma funo de seleo indica a qualquer momento quaisdos candidatos restantes o mais promissor,Uma funo objetivo fornece o valor da soluoencontrada, como o comprimento do caminho construdo(no aparece de forma explcita no algoritmo guloso).

    Joo Lus G. Rosa c 2011 - SCC-211: XI. Programao Dinmica 18/53

  • Paradigmas de Resoluo de ProblemasProgramao Dinmica

    Busca Completa (backtracking)Algoritmos diviso-e-conquistaAlgoritmos gulosos

    Caractersticas da Implementao de Algoritmos Gulosos [8]

    Quando funciona corretamente, a primeira soluoencontrada sempre tima,A funo de seleo geralmente relacionada com afuno objetivo,Se o objetivo :

    maximizar provavelmente escolher o candidatorestante que proporcione o maior ganho individual,minimizar ento ser escolhido o candidato restante demenor cust