Slide - Seção 1 Heurísticas Construtivas 2020-2

Programa¸c˜ao Linear e Inteira ENP012 Prof. Dr. Alexandre Xavier Martins LASOS - DEENP - ICEA Heur´ısticas Construtivas Se¸c˜ao 1 Heur´ısticas Construtivas 2 / 20 Heur´ısticas Construtivas Heur´ısticas Construtivas Constru¸c˜ao Gulosa ▶ Constroem uma solu¸c˜ao passo a passo, elemento por elemento ▶ O elemento a ser inserido a cada passo ´e aquele considerado ’melhor’ segundo o crit´erio adotado 3 / 20 Heur´ısticas Construtivas PROCEDIMENTO ConstGulosa(P) In´ıcio 1 Inicialize o conjunto C de candidatos; 2 S ← {∅}; 3 Fa¸ca 4 c ← Melhor componente do conjunto C; 5 S ← S ⊕ c; 6 Atualize C; 7 Enquanto S n˜ao estiver completa 8 Retorne S; Fim 4 / 20 Heur´ısticas Construtivas ´Arvores geradoras de custo m´ınimo (MST) O problema da ´arvore geradora m´ınima consiste em encontrar, dado um grafo com arestas ponderadas, uma estrutura de conex˜ao (´arvore) em que todos os n´os (geradora) se conectem (direta ou indiretamente) uns aos outros. Essa estrutura deve possuir o menor peso poss´ıvel. 5 / 20 Heur´ısticas Construtivas ´Arvores geradoras de custo m´ınimo (MST) 6 / 20 Heur´ısticas Construtivas ´Arvores geradoras de custo m´ınimo (MST) Kruskal Dado um grafo formado pelo conjunto de n´os N e o conjunto de arestas E, fa¸ca, at´e que tenhamos formado uma ´arvore geradora: ▶ Escolher, do conjunto de arestas E, aquela que possua o menor peso. ▶ Se a inclus˜ao desta aresta na solu¸c˜ao n˜ao formar um ciclo, incluimos a aresta. ▶ Caso contr´ario, descartamos a aresta e a retiramos de E. 7 / 20 Heur´ısticas Construtivas ´Arvores geradoras de custo m´ınimo (MST) Prim Dado um grafo formado pelo conjunto de n´os N e o conjunto de arestas E, escolha um n´o qualquer do grafo e coloque na ´arvore T. Repita os seguintes passos at´e que T seja uma ´arvore geradora: ▶ Escolher o n´o que est´a mais pr´oximo da ´arvore T, ou seja, o n´o que est´a ligado a um n´o de T pela aresta de menor valor. ▶ Adicionar este n´o a T. (podemos parar de adicionar quando tivermos adicionado todos os n´os do grafo). 8 / 20 Heur´ısticas Construtivas Heur´ıstica de constru¸c˜ao gulosa Exemplo Objeto 1 2 3 4 5 6 7 8 Benef´ıcio 4 3 2 6 2 3 5 4 Peso 5 4 3 9 4 2 6 7 Capacidade da mochila b = 20 Heur´ıstica Gulosa 1 Inserir na mochila os objetos de maior benef´ıcio at´e que n˜ao seja mais poss´ıvel inserir elementos 9 / 20 Heur´ısticas Construtivas Heur´ıstica de constru¸c˜ao gulosa Exemplo Objeto 1 2 3 4 5 6 7 8 Benef´ıcio 4 3 2 6 2 3 5 4 Peso 5 4 3 9 4 2 6 7 Capacidade da mochila b = 20 Passo 1 Insere o objeto 4 com benef´ıcio 6 FO = 6 Peso atual = 9 Objeto 1 2 3 4 5 6 7 8 Solu¸c˜ao 0 0 0 1 0 0 0 0 10 / 20 Heur´ısticas Construtivas Heur´ıstica de constru¸c˜ao gulosa Exemplo Objeto 1 2 3 4 5 6 7 8 Benef´ıcio 4 3 2 6 2 3 5 4 Peso 5 4 3 9 4 2 6 7 Capacidade da mochila b = 20 Passo 2 Insere o objeto 7 com benef´ıcio 5 FO = 11 Peso atual = 15 Objeto 1 2 3 4 5 6 7 8 Solu¸c˜ao 0 0 0 1 0 0 1 0 11 / 20 Heur´ısticas Construtivas Heur´ıstica de constru¸c˜ao gulosa Exemplo Objeto 1 2 3 4 5 6 7 8 Benef´ıcio 4 3 2 6 2 3 5 4 Peso 5 4 3 9 4 2 6 7 Capacidade da mochila b = 20 Passo 3 Repare que agora o objeto 8 n˜ao ´e op¸c˜ao Insere o objeto 1 com benef´ıcio 4 FO = 15 Peso atual = 20 Objeto 1 2 3 4 5 6 7 8 Solu¸c˜ao 1 0 0 1 0 0 1 0 12 / 20 Heur´ısticas Construtivas Exerc´ıcio Objeto 1 2 3 4 5 6 7 8 Benef´ıcio 4 3 2 6 2 3 5 4 Peso 5 4 3 9 4 2 6 7 Capacidade da mochila b = 20 1 - Inserir na mochila itens de menor peso 2 - Inserir na mochila itens de maior custo benef´ıcio (Beneficioi/Pesoi) 13 / 20 Heur´ısticas Construtivas Problema do Caixeiro Viajante 14 / 20 Heur´ısticas Construtivas Problema do Caixeiro Viajante Heur´ıstica do Vizinho Mais Pr´oximo A partir de uma cidade inicial, escolher a cidade mais pr´oxima desde que n˜ao se forme um subciclo. 15 / 20 Heur´ısticas Construtivas Problema do Caixeiro Viajante Heur´ıstica da Inser¸c˜ao Mais Barata A partir de um subciclo inicial, formado por um par de cidades, testar a inser¸c˜ao que ir´a gerar a inser¸c˜ao mais barata. Finaliza quando todos os n´os foram inclu´ıdos. 16 / 20 Heur´ısticas Construtivas Problemas da Gera¸c˜ao gulosa ▶ Gera uma ´unica solu¸c˜ao ▶ Vis˜ao m´ıope 17 / 20 Heur´ısticas Construtivas Problema de Designa¸c˜ao N pessoas devem fazer N tarefas distintas, sendo que cada pessoa apresenta uma habilidade para realizar cada uma das tarefas. Cada tarefa ´e realizada por uma ´unica pessoa e cada pessoa realiza uma ´unica tarefa. Pessoa/Tarefa T1 T2 T3 P1 12 9 18 P2 11 4 7 P3 6 5 9 18 / 20 Heur´ısticas Construtivas Constru¸c˜ao aleat´oria ▶ Constroem uma solu¸c˜ao passo a passo, elemento por elemento ▶ O elemento a ser inserido a cada passo ´e escolhido aleatoriamente ▶ ´E importante criar mecanismos para que o m´etodo n˜ao repita elementos invi´aveis 19 / 20 Heur´ısticas Construtivas Constru¸c˜ao parcialmente aleat´oria ▶ Constroem uma solu¸c˜ao passo a passo, elemento por elemento ▶ O elemento a ser inserido a cada passo ´e escolhido aleatoriamente dentro de um conjunto restrito de candidatos ▶ Os candidatos dessa lista restrita s˜ao escolhidos de maneira gulosa 20 / 20