Faz escolhas localmente ótimas na esperança de ótimo global.
Algoritmos usados para encontrar soluções aproximadas em problemas de otimização. Aplicáveis a problemas NP-difíceis, já que estes problemas não podem ser resolvidos em tempo polinomial.
Explora soluções parciais e retrocede quando uma escolha é inviável.
Explora o espaço de soluções podando ramos que não melhoram a melhor solução.
é um caso onde um algoritmo ou software compensa o aumento no consumo de memória levando menos tempo.
semelhante à divisão e conquista, exceto que, em vez de particionar um problema em vários subproblemas de tamanho menor, usamos alguma técnica para reduzir nosso problema em um único problema menor que o original
Divide o problema, resolve subproblemas e combina as soluções.
Esta técnica consiste em dividir um problema maior recursivamente em problemas menores até que o problema possa ser resolvido diretamente.
consiste em construir uma solução através de uma sequência de passos, cada um expandindo uma solução parcialmente construída até o momento, até uma solução completa para o problema ser obtida
Enumera sistematicamente todas as soluções candidatas.
é um método para resolver um problema através de uma travessia completa (ou parcial) no espaço de busca do problema para se obter uma solução.
Resolve subproblemas sobrepostos armazenando resultados intermediários.
reduzir o tempo de execução de um programa utilizando soluções ótimas a partir de subproblemas previamente calculados.
Consiste em uma enumeração sistemática de todos os candidatos à solução, com eliminação de uma candidata parcial quando uma destas duas situações for detectada.
Transforma um problema em outro já conhecido para reutilizar soluções.
Consiste em resolver problemas transformando-o em uma instância mais simples (mais conveniente) do mesmo problema (alteração da instância);
Tipo de algoritmo que representa um refinamento da busca por força bruta, em que múltiplas soluções podem ser eliminadas sem serem explicitamente examinadas.