Docsity
Docsity

Prepare-se para as provas
Prepare-se para as provas

Estude fácil! Tem muito documento disponível na Docsity


Ganhe pontos para baixar
Ganhe pontos para baixar

Ganhe pontos ajudando outros esrudantes ou compre um plano Premium


Guias e Dicas
Guias e Dicas

Melhoria do Backtracking com Função de Pode e Aplicação em Otimização, Notas de estudo de Engenharia Telemática

Este documento aborda a melhoria do algoritmo de backtracking com uma função de pode mais eficiente, aplicada em problemas específicos de otimização, como a atribuição de tarefas a agentes. O exemplo ilustrado utiliza a técnica de branch and bound (b&b) para minimizar o custo total de executar as tarefas, demonstrando como calcular previsões e utilizar a função de poda para reduzir o número de nós considerados.

Tipologia: Notas de estudo

2010

Compartilhado em 27/11/2010

samuel-santos-22
samuel-santos-22 🇧🇷

4.6

(41)

262 documentos

1 / 58

Documentos relacionados


Pré-visualização parcial do texto

Baixe Melhoria do Backtracking com Função de Pode e Aplicação em Otimização e outras Notas de estudo em PDF para Engenharia Telemática, somente na Docsity! Análise e Técnicas de Algoritmos Branch and Bound Tiago Massoni Jorge Figueiredo Melhora backtracking com função de pode mais eficiente Branch and Bound (divide e limita) Apenas problemas de otimização exemplo: atribuição de tarefas 1 2 3 4 A 11 12 18 40 B 14 15 13 22 C 11 17 19 23 D 17 14 20 28 exemplo: atribuição de tarefas Problema: atribuir tarefas aos agentes para minimizar o custo total de executar as n tarefas 1 2 3 4 A 11 12 18 40 B 14 15 13 22 C 11 17 19 23 D 17 14 20 28 exemplo: atribuição de tarefas Problema: atribuir tarefas aos agentes para minimizar o custo total de executar as n tarefas 1 2 3 4 A 11 12 18 40 B 14 15 13 22 C 11 17 19 23 D 17 14 20 28 usando B&B •Definição da função de “poda” –Limites inferiores e superiores (chute) –solução ótima inicial –Superior: menor das diagonais 1 2 3 4 A 11 12 18 40 B 14 15 13 22 C 11 17 19 23 D 17 14 20 28 73 usando B&B •Definição da função de “poda” –Limites inferiores e superiores (chute) –solução ótima inicial –Superior: menor das diagonais 1 2 3 4 A 11 12 18 40 B 14 15 13 22 C 11 17 19 23 D 17 14 20 28 73 87 usando B&B •Definição da função de “poda” –Limites inferiores e superiores (chute) –solução ótima inicial –Superior: menor das diagonais 1 2 3 4 A 11 12 18 40 B 14 15 13 22 C 11 17 19 23 D 17 14 20 28 73 87 [73] calculando a previsão 1 2 3 4 A 11 12 18 40 B 14 15 13 22 C 11 17 19 23 D 17 14 20 28 [73] previsão = atribuição atual + menores custos das próximas tarefas (ok se repetir agentes) primeiro caso (A -> 1): A → 1 A → 2 A → 3 A → 4 calculando a previsão 1 2 3 4 A 11 12 18 40 B 14 15 13 22 C 11 17 19 23 D 17 14 20 28 [73] 60 previsão = atribuição atual + menores custos das próximas tarefas (ok se repetir agentes) primeiro caso (A -> 1): 11(escolha) + 14(menor p/ 2) + 13(menor p/ 3) + 22(menor p/ 4) = 60 A → 1 A → 2 A → 3 A → 4 calculando a previsão 1 2 3 4 A 11 12 18 40 B 14 15 13 22 C 11 17 19 23 D 17 14 20 28 [73] 60 65 58 78 previsão = atribuição atual + menores custos das próximas tarefas (ok se repetir agentes) primeiro caso (A -> 1): 11(escolha) + 14(menor p/ 2) + 13(menor p/ 3) + 22(menor p/ 4) = 60 A → 1 A → 2 A → 3 A → 4 usando B&B 1 2 3 4 A 11 12 18 40 B 14 15 13 22 C 11 17 19 23 D 17 14 20 28 [73] A → 1 A → 2 A → 3 A → 4 60 65 58 78 Oportunismo: poderíamos começar por aqui... BFS (revisão) navega na ordem em que os nós são criados usa uma fila L M O P G Q H JI K FED B C A N BFS (busca por largura) para os cálculos BFS (revisão) navega na ordem em que os nós são criados usa uma fila L M O P G Q H JI K FED B C A N BFS (busca por largura) para os cálculos usando B&B 1 2 3 4 A 11 12 18 40 B 14 15 13 22 C 11 17 19 23 D 17 14 20 28 60 65 58 78 A → 2; B → 1 A → 2; B → 3 A → 2; B → 4 68 59 64 Pela fila de prioridade A → 1 A → 2 A → 3 A → 4 [73] usando B&B 1 2 3 4 A 11 12 18 40 B 14 15 13 22 C 11 17 19 23 D 17 14 20 28 A → 2; B → 3; c → 1; d → 4 A → 2; B → 3; c → 4; d → 1 65 64 A → 1 A → 2 A → 3 A → 4 60 65 58 78 A → 2; B → 1 A → 2; B → 3 A → 2; B → 4 68 59 64 [73] usando B&B 1 2 3 4 A 11 12 18 40 B 14 15 13 22 C 11 17 19 23 D 17 14 20 28 [64] A → 1 A → 2 A → 3 A → 4 60 65 58 78 A → 2; B → 1 A → 2; B → 3 A → 2; B → 4 68 59 64 A → 2; B → 3; c → 1; d → 4 A → 2; B → 3; c → 4; d → 1 65 64 Branch and bound com estas informações podemos comparar o valor limite do nó com o valor da melhor solução até agora se o valor do limite não for melhor, o nó é não promissor e pode ser “podado” nenhuma solução que o inclua levará a uma solução ótima critério de poda do algoritmo 19 Eficiência de BnB Fator que afeta a eficiência tempo para gerar a próxima previsão tempo de execução da função de poda Uma boa função de poda reduz substancialmente o número de nodos considerados tradeoff: boa função de poda VS tempo de avaliá-la Limitações do B&B mais complexo BFS não traz solução recursiva simples análise do algoritmo próxima do impossível depende dos valores da instância da entrada 21 Mochila com B&B cada nó contém o valor atual na mochila, peso atual da mochila além do máximo potencial da mochila nó promissor: máximo valor potencial é maior que o melhor valor armazenado solução ótima inicial: $0 e vai melhorando... Calculando valor máximo inicial i vi si visi l $45 3 $15 2 830 5 $ 6 3 $45 9 $5 4 $10 5 $2 Calculando valor máximo inicial Ptotal = pesoAtual + peso dos objetos que podem ser colocados ainda $0 $” i vi Si visi l $45 3 $15 y) 830 5 $ 6 3 $45 9 $5 4 $10 5 $2 Calculando valor máximo inicial 26 $0 0 $?? Ptotal
=
pesoAtual
+
peso
dos
objetos
que
podem
ser
colocados
ainda Ptotal
=
0
+
s1
+
s2
=
0
+
3
+
5
=
8
(soma
itens
até
que
não
estoure) Vpot
=
valorAtual
+
valor
dos
objetos
colocados
inteiros
+
(W‐Ptotal)
*
 (valor
por
kilo
parcial
do
próximo
objeto) Vpot
=
0
+
v1
+
v2
+
(W
‐
Ptotal)
*
(v3/s3)
=
 











0
+
$45
+
$30
+
(16
‐
8)
*
($5)
=
 











$75
+
$40
=
$115 27 $0 0 $?? árvore de branch and bounds considera COM OBJETO i e SEM OBJETO i com i sem i Encontrar a solução ótima usando B&B Mochila B&B 28 $0 0k $115 Mochila B&B 28 $0 0k $115 com 1 $45 3k $115 sem 1 $0 0k $79 busca em largura priorizada Mochila B&B 28 $0 0k $115 com 1 $45 3k $115 sem 1 $0 0k $79 $75 8k $115 com 2 busca em largura priorizada Mochila B&B 28 $0 0k $115 com 1 $45 3k $115 sem 1 $0 0k $79 $75 8k $115 com 2 busca em largura priorizada sem 2 $45 3k $98 Mochila B&B 28 $0 0k $115 com 1 $45 3k $115 sem 1 $0 0k $79 $75 8k $115 com 2 busca em largura priorizada sem 2 $45 3k $98 $120 17k $0 com 3 sem 3 $75 8k $85 $85 13k $0 com 4 Mochila B&B 28 $0 0k $115 com 1 $45 3k $115 sem 1 $0 0k $79 $75 8k $115 com 2 busca em largura priorizada sem 2 $45 3k $98 $120 17k $0 com 3 sem 3 $75 8k $85 $85 13k $0 com 4 sem 4 $75 8k $0 Mochila B&B 28 $0 0k $115 com 1 $45 3k $115 sem 1 $0 0k $79 $75 8k $115 com 2 busca em largura priorizada sem 2 $45 3k $98 $120 17k $0 com 3 sem 3 $75 8k $85 $85 13k $0 com 4 sem 4 $75 8k $0 $45 3k $55 sem 3 Mochila B&B 28 $0 0k $115 com 1 $45 3k $115 sem 1 $0 0k $79 $75 8k $115 com 2 busca em largura priorizada sem 2 $45 3k $98 $120 17k $0 com 3 sem 3 $75 8k $85 $85 13k $0 com 4 sem 4 $75 8k $0 $45 3k $55 sem 3 com 3 $90 12k $98 $100 17k $0 com 4 sem 4 $90 12k $0 Mochila B&B 28 $0 0k $115 com 1 $45 3k $115 sem 1 $0 0k $79 $75 8k $115 com 2 busca em largura priorizada sem 2 $45 3k $98 $120 17k $0 com 3 sem 3 $75 8k $85 $85 13k $0 com 4 sem 4 $75 8k $0 $45 3k $55 sem 3 com 3 $90 12k $98 $100 17k $0 com 4 sem 4 $90 12k $0 Mochila B&B 28 $0 0k $115 com 1 $45 3k $115 sem 1 $0 0k $79 $75 8k $115 com 2 busca em largura priorizada sem 2 $45 3k $98 $120 17k $0 com 3 sem 3 $75 8k $85 $85 13k $0 com 4 sem 4 $75 8k $0 $45 3k $55 sem 3 com 3 $90 12k $98 $100 17k $0 com 4 sem 4 $90 12k $0 SOLUÇÃO ÓTIMA
Docsity logo



Copyright © 2024 Ladybird Srl - Via Leonardo da Vinci 16, 10126, Torino, Italy - VAT 10816460017 - All rights reserved