Projeto e Análise de Algoritmos - Tentativa e erro

Prévia do material em texto

Projeto e Análise de 
Algoritmos
Tentativa e Erro
Professores:
Heitor Liberalino, Dr.
Lima Júnior, Dr.
Paradigmas de Projeto de Algoritmos
 O sucesso de um projeto de algoritmo depende de 
abordagens adequadas pois:
A forma como um algoritmo aborda o problema 
pode levar a um desempenho ineficiente.
 Em certo casos, o algoritmo pode não conseguir 
resolver o problema em tempo viável.
Paradigmas de Projeto de Algoritmos
 Não existe um paradigma que seja “o melhor” 
dentre todos.
Um problema pode ser resolvido de maneira mais 
eficiente adotando-se um paradigma do que outro.
Um paradigma pode levar a um algoritmo O(2n) e 
outro paradigma a um algoritmo O(n3), para a 
resolução de um mesmo problema.
Algoritmos de Tentativa e Erro
 Suponha que se deva tomar uma serie de decisões 
dentre varias possibilidades, onde:
 Não se tem informação suficiente para saber o que escolher;
 Cada decisão leva a um novo conjunto de escolhas;
 Alguma sequência de escolhas (possivelmente mais que uma) 
pode ser a solução para o problema.
 Tentativa e erro e um modo metódico de tentar varias 
sequência de decisões, ate encontrar uma que 
funcione.
Algoritmos de Tentativa e Erro
 É usado quando se quer achar soluções para 
problemas para os quais não se conhece uma regra 
fixa de computação.
 Passos:
 Escolher uma operação plausível;
 Executar a operação com os dados;
 Se a meta não foi alcançada, repetir o processo até que se 
atinja a meta ou se evidencie a insolubilidade do problema.
Recursividade X Tentativa e Erro
 Métodos recursivos podem ser utilizados para resolver 
problemas cuja solução é tentar todas as alternativas 
possíveis.
 Os algoritmos de tentativa e erro buscam decompor o 
processo de resolução em um número finito de subtarefas
parciais para serem exploradas exaustivamente.
Algoritmos de Tentativa e Erro
 A natureza do problema vai definir se uma ramificação 
da árvore não conduz a nenhuma solução:
 Em alguns problemas, o limite primal pode ser utilizado para 
efetuar as podas. Ex.: Caixeiro Viajante.
 Em outros, a violação de restrições pode inutilizar toda uma 
ramificação. Ex.: Coloração de mapas.
 Em outros, a violação de restrições em ramos internos da 
árvore não necessariamente condena todos os nós filhos da 
subárvores. Ex.: Pickup and Delivery Problem.
Algoritmos de Tentativa e Erro
 Muitas vezes, a pesquisa na árvore de soluções cresce 
rapidamente em uma grandeza polinomial.
 Em outras, o crescimento é exponencial.
 Nestes casos, é recomendado o uso de algoritmos aproximados ou 
heurísticas para resolver problemas de médio e grande porte.
 Formulações incorretas podem levar ao crescimento 
exponencial da árvore.
 Problema é simples, mas o algoritmo é complexo!
 Ou pode estar relacionada de fato com a natureza do problema.
Exemplos de Tentativa e Erro:
Problemas de tomada de decisão
Exemplos de Tentativa e Erro
 Exemplo 1: dado um labirinto, encontre um caminho da 
entrada a saída.
 Em cada interseção do labirinto, você tem que decidir se:
 Segue direto;
 Vira à esquerda;
 Vira à direita.
 Hipóteses:
 Você não tem informação suficiente para escolher corretamente;
 Cada escolha leva a outro conjunto de escolhas;
 Uma ou mais sequência de escolhas pode ser a solução.
Exemplos de Tentativa e Erro
 Exemplo 2: você deseja colorir um mapa 
com, no máximo, 4 cores: vermelho, verde, 
azul e branco. Países adjacentes devem ter 
cores diferentes.
 Em cada iteração, você deve decidir que 
cor pinta um pais, dadas as cores já 
atribuídas aos vizinhos
 Você não tem informação suficiente para 
escolher as cores;
 Cada escolha leva a outro conjunto de 
escolhas;
 Uma ou mais sequência de passos pode ser 
a solução.
Exemplos de Tentativa e 
Erro
 Exemplo 3: Passeio do Cavalo 
no Xadrez
 Tabuleiro com n x n posições: 
cavalo se movimenta segundo 
regras do xadrez.
 Problema: partindo da posição 
(x0; y0), encontrar, se existir, um 
passeio do cavalo que visita todos 
os pontos do tabuleiro uma única 
vez.
Exemplo de Tentativa e Erro:
Problemas de Satisfação de 
Restrições (PSR)
Algoritmos de Tentativa e Erro
 Existe um framework (uma generalização) para resolução de 
problemas quaisquer com restrições. 
 A classe se chama: Problemas de Satisfação de Restrições
(PSR)
 Um PSR é definido por:
 um conjunto de variáveis de decisão {x1, x2, x3, ..., xn};
 um conjunto de restrições {c1, c2, c3, ..., cm};
 um domínio não vazio de valores possíveis Di, para cada variável, 
com i =1, ..., n; 
 Cada variável pode assumir pelo menos um valor.
Algoritmos de Tentativa e Erro
 Um estado do problema é definido por uma atribuição de valores 
a no mínimo uma variável de decisão.
 Exemplosde estados:
 x1 = 3, x2 = ?, x3 = 6, x4 = 10;
 x1 = ?, x2 = ?, x3 = ?, x4 = 15;
 x1 = 3, x2 = 58, x3 = 6, x4 = 10.
 Uma atribuição que não viola nenhuma restrição é chamada 
consistente.
 Temos uma solução ao PSR quando todas as variáveis possuem 
valores dentro de seus domínios e nenhuma restrição é violada.
 Alguns PSR exigem que a solução maximize ou minimize 
uma função objetivo.
 Problemas de otimização.
 Em outros, é necessário apenas que encontremos uma 
atribuição completa que não viole restrições.
 Geralmente problemas mais restritos;
 Também podem ser modelados como problemas de otimização.
 A técnica mais utilizada é a de penalização da f.o. quando restrições são 
violadas.
Algoritmos de Tentativa e Erro
Exemplo de PSR:
Coloração de mapas
Problema de Colorir um Mapa
 Variáveis : AO, TN, Q, NGS, V, AM e T 
 Domínio : Di = {Vermelho, Verde, Azul}
 Restrição : regiões adjacentes deverão receber cores diferentes
Australia 
Ocidental
Territorio 
do Norte
Australia 
Meridional
Nova Gales 
do Sul
Problema de Colorir um Mapa
 Restrições : regiões vizinhas devem ter cores distintas
 AO ≠ AM, TN ≠ AM, Q ≠ AM, NGS ≠ AM, V ≠ AM, AO ≠ TN, TN ≠ Q, Q ≠ 
NGS, NGS ≠ V
 Exemplo : combinações permissíveis para AO e TN
 {(vermelho, verde), (vermelho, azul), (verde, vermelho), (verde, 
azul), (azul, vermelho), (azul, verde)}
 Ou simplesmente AO ≠ TN
Grafo de Restrições de um PSR
 Obs.: Tasmânia é um subproblema independente;
 Como identificar que existem problemas independentes?
 Componentes fortemente conectados...
Australia 
Ocidental
Territorio 
do Norte
Australia 
Meridional
Nova Gales do 
Sul
Variável
Restrição
Problema de Colorir um Mapa
As soluções são completas e constituídas de atribuições válidas
Ex.: AO = Vermelho, TN = Verde, Q = Vermelho, NGS = Verde, 
V = Vermelho, AM = Azul, T = Verde
Exemplo de Árvore de Busca do 
problema de coloração de mapas
Variáveis de PSRs
 Variáveis Discretas.
Domínios Finitos:
Ex.: PSRs Booleanos.
 inclusive Satisfabilidade Booleana (SAT).
 Problema NP-Completo.
Domínios Infinitos:
Ex.: Que envolvem Inteiros, strings, etc.
Variáveis de PSRs
 Variáveis Contínuas.
 Ex.: Que envolvem reais.
 Exemplo de problema:
 Resolve restrições lineares em tempo polinomial por métodos 
de Programação Linear (simplex, pontos interiores).
Tipos de Restrições
 Unária
 Ex.: MG ≠ verde
 Binária
 Ex.: MG ≠ SP
 Ordem Maior (três ou mais variáveis)
 Preferenciais (Problemas de Otimização)
 Ex.: Vermelho é melhor do que verde, isto é, há uma função de 
custo nas atribuições (função objetivo).
Exemplos de PSRs do Mundo Real
 Problemas de Alocação
 Ex.: Qual será a sala de PAA no semestre que vem?
 Problemas de Oferta de Disciplinas
 Ex.:Que matéria será oferecida no PPgCC?
 Configurações de Hardware
 Layout;
 Agendamento para entregas
 Um motoboy vai fazer entregas pela cidade:
 Qual é a ordem para a entrega que minimiza a distância total percorrida?
Relacionado ao Framework do PSR
 Estado Inicial:
 Atribuição vazia (raiz da árvore de busca): { }
 Função Sucessor:
 Atribui um valor a uma variável não atribuída, desde que ela 
não entre em conflito com atribuições já realizadas.
 Teste de Meta:
 Atingiu a atribuição completa;
 Depende da natureza do problema.
Pilha de Execução
 Toda solução deve ser uma atribuição completa.
 Logo, a busca está na profundidade n se existem n variáveis.
 Não há problemas com o crescimento da pilha de 
execução, se for utilizado uma adaptação da busca 
em profundidade para resolver os PSRs.
 A não ser que haja uma quantidade exponencial de variáveis 
de decisão;
 Neste caso, o problema se torna intratável por 
computadores atuais.
Pilha de Execução
Um ponto importante é:
o caminho pelo qual a solução é alcançada é 
irrelevante.
Percebe-se isso na implementação do caixeiro 
viajante:
através da poda “inteligente” que exige a 
ocorrência do consumidor x antes do y, por 
exemplo.
Busca com Retrocesso para PSRs
 Algoritmo de Tentativa e Erro:
 Backtracking (busca com retrocesso).
 Refinamento da busca por força bruta;
 Existem frameworks que trabalham com qualquer problema de satisfação de 
restrições (PSR).
 PSR:
 Não se pode explorar informações específicas do domínio;
 Diferentemente do backtracking padrão;
 Escolha para exploração:
 Variável mais restrita;
 É uma heurística que tenta privilegiar caminhos mais promissores, escolhendo as 
variáveis com o menor número de valores legais.
Busca com Retrocesso para PSRs
 Algo terrível pode acontecer ao gerar a árvore de busca 
de PSRs:
 Suponhamos n variáveis de decisão;
 E d valores que podem ser atribuídos a cada variável (domínio);
 O fator de ramificação na raiz é n.d, pois qualquer valor de d pode 
ser atribuído a qualquer uma das n variáveis;
 No próximo nível, o fator de ramificação é (n-1).d;
 Assim, geramos uma árvore com n!.dn folhas, embora existam 
“apenas” dn atribuições completas possíveis;
Busca com Retrocesso para PSRs
 A formulação de problema está correta, mas é ingênua... 
 Por quê?
Busca com Retrocesso para PSRs
 Porque...
 ...ela ignora a propriedade comum a todos os PSRs: a 
comutatividade.
 Um problema é comutativo se a ordem de aplicação nas atribuições 
não possui nenhum efeito sobre o resultado;
 Com esta consideração, nosso número de atribuições passa a ser dn.
 Apesar de representar um número astronômico para alguns 
problemas, a complexidade foi reduzida bruscamente.
Busca com Retrocesso para PSRs
 A expressão Busca com Retrocesso é utilizada para 
indicar uma busca em profundidade que:
 escolhe valores para uma variável de cada vez e que;
 efetua um retrocesso quando uma variável não tem 
valores válidos restantes para serem atribuídos.
 Quando resolvemos o Caixeiro Viajante com 
Tentativa e erro, temos informações específicas do 
domínio.
Busca com Retrocesso para PSRs
A proposta para o PSRs é em sentido 
oposto:
Resolver qualquer PSRs sem utilizar 
NENHUMA informação útil do domínio;
Está relacionado com o uso de ferramentas 
específicas ou gerais.
Busca com Retrocesso para PSRs
 Métodos de propósito geral podem obter ganhos em 
velocidade através dos seguintes questionamentos:
 Que variável deve ser atribuída em seguida, e em que 
ordem seus valores devem ser experimentados?
 Quais são as implicações das atribuições atuais para as 
outras variáveis ainda não atribuídas?
 Quando um caminho falha, a busca pode evitar a 
repetição da falha em caminhos subsequentes?
Que variável será atribuída a seguir?
 A variável mais restringida (unária)
 Escolha a variável com o menor número de valores legais 
(Minimum Remaining Values)
Em que ordem seus valores serão 
experimentados?
 O valor com menos restrições
 Escolha o valor que provoque o menor número de restrições 
possíveis nas variáveis restantes.
Pergunta-se:
 É possível eliminar subárvores que já possuem 
ramificações sem nenhuma atribuição legal para 
alguma variável ainda não atribuída?
 É possível prever falhas futuras?
Verificação Prévia
(Forward-Checking)
Especialização do Backtracking
 Forward-checking (Verificação Prévia)
 Em um PSR, uma maneira de utilizar melhor as restrições 
durante a busca é a chamada verificação prévia (forward-
checking);
 Sempre que uma variável X é atribuída, este processo 
examina cada variável não atribuída Y que está conectada a 
X por uma restrição;
 A partir daí, é excluído do domínio de Y, qualquer valor que 
esteja inconsistente com o valor escolhido para X.
Especialização do Backtracking
adição do forward-checking
As variáveis não possuem nenhuma atribuição. Todas possuem no domínio Verde, 
Vermelho e Azul como possibilidades
AO TN Q NGS V AM T
AO
AO TN Q NGS V AM T
A heurística da variável menos 
restringida não possui escolha no 
início da busca, pois todas as 
variáveis possuem 3 opções de 
cores.
Supõe-se que AO recebe a cor 
vermelha a princípio no 
backtraking.
Especialização do Backtracking
adição do forward-checking
Especialização do Backtracking
adição do forward-checking
AO assumindo a cor vermelha, a 
política Forward-checking já anula 
possíveis conflitos com as variáveis 
vizinhas (lembrando que a 
vizinhança é definida pela 
restrição binária).
AO
AO TN Q NGS V AM T
Especialização do Backtracking
adição do forward-checking
Assume-se que a próxima variável a ser 
fixada no backtracking é o Estado Q.
Neste instante, o sistema já elimina do 
domínio das variáveis vizinhas a cor 
Verde: de NGS, AM e TN.
AO
Q
AO TN Q NGS V AM T
Especialização do Backtracking
adição do forward-checking
Supõe-se que na próxima escolha do 
backtracking seja fixada a variável 
V com a cor azul.
Neste ponto, já será removida a cor 
azul do domínio de NGS e de AM.
AO
Q
V
AO TN Q NGS V AM T
Especialização do Backtracking
adição do forward-checking
AM não possui mais valores 
possíveis no domínio.
No backtracking padrão este 
problema apenas seria 
identificado quando a busca 
selecionasse AM para atribuição e 
para todas, aconteceria choque de 
valores com seus vizinhos.
AO
Q
V
AO TN Q NGS V AM T
Especialização do Backtracking
adição do forward-checking
A checagem para frente (forward-
checking) também age neste 
instante, eliminando o ramo de 
busca, já que este é inviável por 
enumeração implícita. O 
backtracking pode desempilhar e 
continuar sua força bruta.
AO
Q
V
AO TN Q NGS V AM T
Propagação de Restrições
(Constraint propagation)
Propagação de Restrições (Constraint
propagation)
 Embora detecte muitas 
inconsistências, o forward-
checking não detecta todas elas.
 Por exemplo:
 Quando AO for VERMELHO e Q for 
VERDE, tanto TN como AM serão 
forçados a serem AZUIS;
 Mas NT e AM são adjacentes. Então, 
como ambos podem ser azuis?
Propagação de restrições
 Foi o que aconteceu na 
segunda atribuição do 
exemplo anterior.
 O ramo já estava condenado.
 Apenas com forward-checking
ele não poderia ser eliminado, 
pois todas as variáveis ainda 
possuíam valores legais.
AO
Q
AO TN Q NGS V AM T
Propagação de restrições
 O forward-checking
não detecta este 
fato como uma 
inconsistência, 
porquenão realiza 
o exame a uma 
distância 
suficientemente 
longa à frente.
AO
Q
AO TN Q NGS V AM T
Propagação de restrições
 É necessário propagar esta informação a 
partir de AO e Q sobre TN e AM.
 Como foi feito no forward-checking.
 Em seguida sobre a restrição entre TN e AM 
para detectar a inconsistência.
AO
Q
Propagação de restrições
Mas devemos fazer de modo 
rápido.
 É inútil reduzir a quantidade 
de busca se é gasto mais 
tempo propagando restrições 
do que fazendo uma busca 
simples.
Ai entra a pergunta: até 
quando propagar?
AO
Q
Propagação de restrições
 A ideia de consistência de 
arco fornece uma noção 
substancialmente mais 
forte do que o forward-
checking.
 Aqui o termo arco se 
refere a um arco 
orientado no grafo de 
restrições.
 Como o arco de AM para 
NGS
AO
Q
AO TN Q NGS V AM T
Propagação de restrições
 Analisando o arco (AM, 
NGS):
 O arco é consistente, se para 
TODO valor x de AM, existe 
um valor y de NGS 
consistente com x;
 AM = AZUL, existe pelo menos 
uma atribuição de NGS 
válida: NGS=VERMELHO;
 Portanto, o arco é 
consistente.
AO
Q
AO TN Q NGS V AM T
Propagação de restrições
 Analisando o arco em sentido 
contrário: (NGS, AM):
 O arco é inconsistente;
 Quando NGS=AZUL, não existe 
atribuição válida para AM;
 Para tornar o arco consistente, 
basta eliminar a cor AZUL do 
domínio de NGS.
AO
Q
AO TN Q NGS V AM T
Propagação de restrições
 Em um processo semelhante, 
podemos propagar a restrição do 
arco (TN, AM):
 Domínio(TN)= {AZUL}
 Domínio(AM) = {AZUL}
 Logo, AZUL deve ser eliminado do 
domínio de TN, o que deixa o 
domínio vazio.
 Desde modo, a aplicação da 
propagação de restrições via 
consistência de arcos detectou 
uma inconsistência que não é 
detectada pelo forward-checking.
AO
Q
AO TN Q NGS V AM T
Propagação de restrições
 A verificação de consistência de arco pode ser 
aplicada como uma etapa de propagação.
O processo deve ser aplicado repetidamente até 
não restar mais nenhuma inconsistência.
 Isso porque, sempre que um valor é excluído do 
domínio de alguma variável, para remover uma 
inconsistência de arco, pode surgir uma nova 
inconsistência de arco em arcos que apontam para 
esta variável.
Propagação de restrições
 Embora o processo seja bastante dispendioso 
(se comparado ao forward-checking), em 
geral o custo extra é compensador.
 Fica a pergunta:
o que vai determinar se é ou não é 
interessante efetuar a propagação de 
restrições via consistência de arcos?