Please enable JavaScript.

Coggle requires JavaScript to display documents.

M16 - Coggle Diagram

- - - - Aproximação: Desenvolver algoritmos que fornecem soluções boas, mas não necessariamente ótimas, em um tempo razoável.
      - Heurísticas: Métodos que exploram o conhecimento específico do problema para encontrar soluções práticas rapidamente.
      - Métodos exatos para instâncias pequenas: Usar algoritmos exatos que são eficientes apenas para instâncias pequenas do problema.
      - Backtracking: Técnica que envolve explorar todas as soluções possíveis, retornando (backtracking) quando uma solução inviável é encontrada.
      - Branch-and-Bound: Estratégia que divide o problema em subproblemas menores e usa limites para eliminar subproblemas que não podem levar a uma solução melhor do que a já conhecida.
- - - - Exploração sistemática: Testa todas as possibilidades para garantir que nenhuma solução seja omitida.
      - Uso de recursão: Muitas vezes implementado de forma recursiva, onde cada chamada recursiva representa uma escolha ou passo na construção da solução.
      - Pruning: Descartar soluções parciais que não podem levar a uma solução completa, economizando tempo e esforço computacional.
      - Aplicações: Problemas como o Sudoku, labirintos, quebra-cabeças de palavras, e a geração de permutações e combinações.
- - - - Branching (Ramificação): Dividir o problema em subproblemas menores que são mais fáceis de resolver.
      - Bounding (Limitação): Calcular um limite superior e inferior para o valor da função objetivo dentro de cada subproblema.
      - Fathoming (Eliminação): Descartar subproblemas que não podem melhorar a solução conhecida atualmente.
    - - Eficiência: Reduz a quantidade de trabalho ao evitar a exploração de subproblemas não promissores.
      - Estratégias de escolha: Pode usar diversas estratégias para escolher qual subproblema explorar a seguir, como a busca em profundidade ou largura.
      - Aplicações: Usado em problemas como o caixeiro-viajante, programação linear inteira, e outros problemas de otimização combinatória.